Skip to content

Multi variable branching #158

@AntoinePrv

Description

@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

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions