Multi variable branching

[AntoinePrv]

Describe the problem or improvement suggested

Create a new environment for MVB.

Describe the solution you would like

PySCIPOpt solution from @CharJon

def branch_on_disjunction(model: scip.Model, coefficients, variables):
    """Branch on the sum of integer/binary variables.
        Always creates both children and will error out
        if branching would not cut off current solution!
        As nodeselprio and childestimate for 'createChild'
        are unknown, the node-selection-heuristic will be
        quite random.
    """
    assert len(variables) > 0, f"Need at least one variable to branch on"
    assert len(variables) == len(coefficients), f"Need as many coefficients as variables"
    assert all(v.vtype() == 'BINARY' for v in variables), f"Binary only implemented"
    current_values_sum = sum(v.getLPSol() for v in variables)
    assert not model.isFeasIntegral(current_values_sum), f"Sum {current_values_sum} is not fractional"
    floored_bound = math.floor(current_values_sum)
    if len(variables) == 1:
        model.branchVar(variables[0])
    elif floored_bound == 0:
        # trick to allow better bound checking
        child_1 = model.createChild(1, 0)
        for cur_variable in variables:
            model.chgVarUbNode(child_1, cur_variable, 0)
        child_2 = model.createChild(1, 0)
        model.addConsNode(child_2, scip.quicksum(c * v for c, v in zip(coefficients, variables)) >= 1)
    elif floored_bound + 1 == len(variables):
        # trick to allow better bound checking
        child_1 = model.createChild(1, 0)
        model.addConsNode(child_1, scip.quicksum(c * v for c, v in zip(coefficients, variables)) <= floored_bound)
        child_2 = model.createChild(1, 0)
        for cur_variable in variables:
            model.chgVarLbNode(child_2, cur_variable, 1)
    else:
        child_1 = model.createChild(1, 0)
        model.addConsNode(child_1, scip.quicksum(c * v for c, v in zip(coefficients, variables)) <= floored_bound)
        child_2 = model.createChild(1, 0)
        model.addConsNode(child_2, scip.quicksum(c * v for c, v in zip(coefficients, variables)) >= floored_bound + 1)
    return scip.SCIP_RESULT.BRANCHED

Describe alternatives you have considered

Additional context

[AntoinePrv]

So it seems the best approach for us would be to use Generalized Upper Bound (GUB) branching. For integer variables x_i provided by the user, and their LP relaxation value x_lp_i,

• If s := sum(x_lp_i) is fractional, then branch on sum(x_i) <= floor(s) & sum(x_i) >= ceil(s)
• If s := sum(x_lp_i) is integer, then branch on sum(x_i) <= s - 1 & sum(x_i) == s & sum(x_i) >= s+ 1

Some questions (cc @gasse @dchetelat):

• Do we keep the same environment for Branching and MVB? It seems one variable is a special case of MVB.
• What should be the SCIP_RESULT when used in a branching rule? SCIP_BRANCHED?
• What is the action set? Same as in Branching?

[gasse]

I would answer yes to the three questions:

• I would have just one branching environment. Existing code for single-variable branching will not change, so MVB should be backward-compatible with SVB
• SCIP_BRANCHED should be the result if branching occurred yes, see the SCIP doc
• I would say yes, the action set should remain the same for simplicity. The only difference would be that you are now allowed to branch on any subset of the branching candidates, instead of just one.

[AntoinePrv]

One (open ?) question that remain is the value for the estimate and priority parameters of the SCIPcreateChild function.

[AntoinePrv]

I removed BranchingSum and reopened #299 for the current implementation. @gasse do we have more insight on what was wrong with it?

[gasse]

I'm really not sure, no. The code looks right to me, however when using it it would often bring SCIP to inconsistent states, such as unfeasibility or optimality with incorrect optimal values. Probably we are missing some details that SCIP assumes during branching, either explicitely or implicitely in the code.