ISSA .
Original Message:
Sent: Thu March 02, 2023 02:49 PM
From: Paul Rubin
Subject: Using Generic Callback to add Lazy constraints, User cuts and use as an HeuristicCallback
There is a programmatic tactic that would allow you to add the user cuts, but I very much doubt they would behave the way you expect. Let's say the feasible regions are x in X for the master problem and y in Y for the subproblem, and you add a cut a'x + b'y <= c in the master problem. The difficulty here is that the master problem is not going to restrict y to Y. Using your example of y <= x for a user cut in the MP, and assuming x and y are nonnegative, what would stop CPLEX from simply setting y = 0, regardless of whether that would be accepted in the subproblem? So the question is, are you confident that the user cuts would make a meaningful improvement in the MP (and be valid) without the MP knowing anything about the feasible region Y of the subproblem?
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
Original Message:
Sent: Thu March 02, 2023 07:28 AM
From: ISSA .
Subject: Using Generic Callback to add Lazy constraints, User cuts and use as an HeuristicCallback
Hello Paul, thank you (always) for your help.
Yes you understood this correctly. The y variables do not belong to the MP, they only appear in the SP.
Everytime the MP finds a feasible and integer solution, the SP which is an LP is solved once to generate feasibility cuts (takes as input fixed integer x vars) that are added to the MP. In addition violated lazy constraints are also added.
I see now why that would cause an error.
Do you think there's a way to add those user cuts (for fractional x vars) ?
While this can be done by solving a MILP model containing both x and y vars, I can't add anymore my feasibility cuts since the complicated constraints connecting x and y are already in the model, and hence always feasible with respects to those constraints.
I am not sure though how this can be done using the MP and SP models.
Any ideas are much appreciated. Thank you.
------------------------------
ISSA .
Original Message:
Sent: Wed March 01, 2023 06:48 PM
From: Paul Rubin
Subject: Using Generic Callback to add Lazy constraints, User cuts and use as an HeuristicCallback
If I understand this correctly (which is by no means certain), you are trying to add cuts to the master problem that contain variables y that only appear in the subproblem and do not belong to the master problem. That would certainly cause an error.
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
Original Message:
Sent: Wed March 01, 2023 04:50 PM
From: ISSA .
Subject: Using Generic Callback to add Lazy constraints, User cuts and use as an HeuristicCallback
Hello everyone,
I am working on a MILP that is decomposable into a master problem (MP) containing only integer variables (x) and a sub-problem (SP) containing only continuous variables (y). This is known as Benders decomposition.
I start by solving the MP. Then for every incumbent solution (x vars are integer and feasible), the SP is solved to generate feasibility cuts (I am only interested in these cuts).
In addition to the Benders feasibility cuts, I am also interested in adding violated lazy constraints (that are removed initially from the MP and then added only if they are violated by the current incumbent solution, thus containing only integer var), and user cuts to improve the LP relaxation (containing both x and y vars).
Thus, I am trying to use the generic callback to add:
- Lazy constraints and Benders Feasibility cuts in Candidate context.
- User cuts in Relaxation context.
While adding the lazy constraints doesn't pose any problem, I am getting the following error when adding user cuts : ilog.cplex.CpxException: CPLEX Error 1006: Error during callback.
I will try to show how I initialized the callback, and be as simple as possible:
//I initialize the callback taking MP as argument: Callback callback = new Callback(master);
//attach it to the master problem, to generate both lazy and user cuts: master.use(callback, IloCplex.Callback.Context.Id.Candidate | IloCplex.Callback.Context.Id.Relaxation);
public class Callback implements IloCplex.Callback.Function {
public synchronized void invoke(final IloCplex.Callback.Context context){
if(context.inRelaxation()) { //add user cuts
I got the vars values using context.getRelaxationPoint(x), and since the user cuts contain also y var from SP, i got the values of y using Ilocplex.getValue(y)
For instance if the cuts to be added should be y <= x then it is added as following:
expression.addTerm(1, y);
expression.addTerm(-1, x);
IloRange range = master.getCplex.le(expression, 0);
context.addUserCut(range, IloCplex.CutManagement.UseCutForce, false);
I suspect that the error comes from here.
}
if(context.inCandidate()) {
I got the vars values using context.getCandidatePoint(x), and the violated lazy constraints and feasibility cuts are added. }
}
I have a couple of questions regarding this:
- What am I doing wrong ? and How to use both callbacks using the generic callback ?
- Is it possible to use a callback for the SP when it's feasible ?
- I am also interested in using Heuristic Callback to change a fractional solution to an integer one using my own Routine (or change an integer feasible solution with an own one). I know CPXXcallbackpostheursoln and CPXcallbackpostheursoln has to be used. Does anyone has a small example on using these routines ? In which context has to be called (Relaxation context then use the routine) ?
Thank you for your help. It is much appreciated.
------------------------------
ISSA .
------------------------------