Decision Optimization

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
------------------------------

#DecisionOptimization

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
------------------------------

Original Message:
Sent: Wed July 28, 2021 08:11 PM
From: Natanael Ramos
Subject: Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

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
------------------------------

#DecisionOptimization

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
------------------------------

Original Message:
Sent: Thu July 29, 2021 01:54 PM
From: Paul Rubin
Subject: Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

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

Original Message:
Sent: Wed July 28, 2021 08:11 PM
From: Natanael Ramos
Subject: Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

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
------------------------------

#DecisionOptimization

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
------------------------------

Original Message:
Sent: Thu July 29, 2021 06:00 PM
From: Natanael Ramos
Subject: Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

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

Original Message:
Sent: Thu July 29, 2021 01:54 PM
From: Paul Rubin
Subject: Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

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

Original Message:
Sent: Wed July 28, 2021 08:11 PM
From: Natanael Ramos
Subject: Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

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
------------------------------

#DecisionOptimization

Great, thank you for the suggestion Paul!

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

Original Message:
Sent: Thu July 29, 2021 07:51 PM
From: Paul Rubin
Subject: Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

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

Original Message:
Sent: Thu July 29, 2021 06:00 PM
From: Natanael Ramos
Subject: Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

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

Original Message:
Sent: Thu July 29, 2021 01:54 PM
From: Paul Rubin
Subject: Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

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

Original Message:
Sent: Wed July 28, 2021 08:11 PM
From: Natanael Ramos
Subject: Only change bounds on a BranchCallbackI, while maintaining CPLEX's branching decisions

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
------------------------------

#DecisionOptimization