Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Multi variable branching #158

Open
AntoinePrv opened this issue Apr 14, 2021 · 5 comments · Fixed by #181 · May be fixed by #299
Open

Multi variable branching #158

AntoinePrv opened this issue Apr 14, 2021 · 5 comments · Fixed by #181 · May be fixed by #299
Labels
new/dynamics ⚙️ Ecole dynamics (for environments)

Comments

@AntoinePrv
Copy link
Member

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 AntoinePrv added the type/enhancement 🚀 New feature or request label Apr 14, 2021
@AntoinePrv
Copy link
Member Author

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
Copy link
Member

gasse commented Apr 28, 2021

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 AntoinePrv mentioned this issue May 6, 2021
4 tasks
@AntoinePrv
Copy link
Member Author

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

@AntoinePrv AntoinePrv added new/dynamics ⚙️ Ecole dynamics (for environments) and removed type/enhancement 🚀 New feature or request labels Jun 12, 2021
@AntoinePrv AntoinePrv linked a pull request Dec 14, 2021 that will close this issue
4 tasks
@AntoinePrv
Copy link
Member Author

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

@AntoinePrv AntoinePrv linked a pull request Dec 14, 2021 that will close this issue
4 tasks
@gasse
Copy link
Member

gasse commented Dec 20, 2021

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
new/dynamics ⚙️ Ecole dynamics (for environments)
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants