Decision Optimization

Expand all | Collapse all

Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

  • 1.  Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

    Posted Thu July 29, 2021 09:38 AM
    Hello all,

    I wish to accomplish the following task using CPLEX's Branch Callbacks and the Concert API: When CPLEX decides to branch on a given variable xi=1 , I want to define xj=0 for another variable that "conflicts" with xi (or a set of conflicting variables).

    So far, I can copy CPLEX's branching decisions with the getBranch method, then change the bounds and dirs arrays and invoke the makeBranch method to accomplish the aforementioned task.

    Although I can get the job done in this way, I wonder if there is a simpler solution, perhaps only adding a set of constraints xj=0, while maintaining CPLEX's branch decisions. However, I haven't found a way to do this without the initial copy step.

    Any help would be appreciate.

    Best regards.

    ------------------------------
    Natanael Ramos
    ------------------------------


  • 2.  RE: Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

    Posted Thu July 29, 2021 01:54 PM
    I think there is genuine danger that what you are trying to do could lead to an incorrect solution. My assumption is that the logical constraints x[i] == 1 => x[j] == 0 are not already expressed in the model. If they were, the tricky branching would be unnecessary; x[j] == 0 would be enforced by constraints in the child where x[i] == 1. So what you are doing is in effect changing the model on the fly. The danger is that CPLEX might make presolve simplifications or other reductions that are incorrect (and that it would avoid if it knew of the hidden constraints).

    This is similar to the difference between a user cut callback and a lazy constraint callback. Both add constraints on the fly. The difference is that there is an implicit contract when employing a user cut callback that the cuts will not remove any integer-feasible solutions. The lazy constraint callback makes no such promise, and as a result CPLEX alters its behavior when it sees a lazy constraint callback. Using a user cut callback to add constraints that remove integer-feasible solutions is know to result in invalid solutions ("optimal" solutions that are not actually optimal).

    Alternatives to what you are proposing would be to add the logical constraints to the model as ordinary constraints (for instance, in the form x[i] + x[j] <= 1), or possibly as lazy constraints (same idea, but held off to the side in a pool until they are needed), or to use a lazy constraint callback or its generic equivalent (which would add the constraint x[i] + x[j] <= 1 any time CPLEX had a proposed incumbent solution where both x[i] and x[j] were 1).

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 3.  RE: Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

    Posted Thu July 29, 2021 06:00 PM
    Thank you for the very informative answer!

    However, I've failed to give the full context of my problem in my question.

    I'm already adding the conflict constraints in the form xi + xj <= 1 in a lazy fashion. Consequently, CPLEX automatically disables both dual (CPX_PARAM_REDUCE) and presolve (CPX_PARAM_PREREFORM) reductions.

    What I want to accomplish is the following: Given a fractional solution at a node of the BnB tree, when CPLEX decides to branch on xi=1, I want to enforce xj=0 for every xj that conflicts with xi, using the bounds and directions arrays. Note that, since I'm adding the conflict constraints on demand, CPLEX may not be aware of these conflicts at this point, so this is why I want to manually add this information.

    I could add all conflict constraints a priori, but it is a huge set of constraints and I observed that, in practice, I only need ~0.2% of constraints of this set.

    I hope that the situation is clearer now.

    ------------------------------
    Natanael Ramos
    ------------------------------



  • 4.  RE: Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

    Posted Thu July 29, 2021 07:52 PM
    Given that information, I think what you are doing is the best way to accomplish what you want. You could call getBranches, convert each bound change into a constraint (IloRange), add an IloRange for each x[j] == 0 constraint you want to add, turn the ranges into an array and use that version of makeBranch, but I don't see that being any better (and in fact I think it is arguably more work) than what you are doing.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 5.  RE: Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

    Posted Fri July 30, 2021 08:42 AM
    Great, thank you for the suggestion Paul!

    ------------------------------
    Natanael Ramos
    ------------------------------