Originally posted by: UserCplex

Hello,

I am trying to solve an MIP as follows:

(0)Create ORIGINAL LP model of the MIP relaxation. Set INTO_CB = NO;//This indicates whether the separation() routine is called from within a callback or not.

(1)Solve ORIGINAL LP or if branch and bound has started, the current node's LP.

(2)Identify and add violated cuts by calling separation().

    (a)If a violated inequality is found, if INTO_CB == NO, use CPXaddrows() to add cut to LP. Here, I am able to give the cut my user defined name as one of the arguments.

    (b)If a violated inequality is found, if INTO_CB == YES, use CPXcutcallbackadd() to add cut to present node's LP object. Here, I am unable to find give a user defined name as one of the arguments for the function.

    (c)If no violated inequality is found, set INTO_CB == YES. Convert LP to MILP and submit to CPLEX to solve by starting branch and bound.

    (d)Go to Step (1)

    (e)Other exit conditions....

I am debugging an application and I would like to be able to give the added cuts in Step 2b my own user defined names.

That is, within my callback function: int CPXPUBLIC LP::mycutcallback(CPXCENVptr env, void *cbdata,int wherefrom, void *cbhandle, int *useraction_p){ .. }

I have the following to print out the node's LP file in .lp format just after adding the violated cut:

CPXLPptr _lp;

 

Is there a way this can be done so that on reading cback.lp file, I can see my user added cuts with my user specified name? I could not come across any previous thread addressing this. If there is one, I would appreciate any link or any other pointers to get this done.

Thanks in advance.

 

#CPLEXOptimizers
#DecisionOptimization

No, there is no way to do this. Like you noted, the CPXcutcallbackadd() functions takes no arguments to provide names. In the cback.lp file, the cuts you added will have a name that starts with 'u', followed by a number. So you can find which rows are cuts that were added by you but you cannot easily map them back to things in your code.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

Daniel,

I am able to see the 'u' constraints. However, they are not in the same form as the cutval[] array that I populate and pass to the CPXcutcallbackadd() function. That is, the constraint in the .lp file seems to be multiplied by some fraction of the cutval[] entries that I pass via code.

Is this the default behavior? Can the user disable this so that cutval[] entries/coefficients are faithfully replicated in the .lp file?

Also, perhaps related to this is the following paragraph in the CPLEX manual on CPXcutcallbackadd page:

"The cut may be for the original problem if the parameter CPX_PARAM_MIPCBREDLP was set to CPX_OFF before
the call to CPXmipopt that calls the callback. In this case, the parameter CPX_PARAM_PRELINEAR should also
be set to CPX_OFF (zero). Otherwise, the cut is used on the presolved problem."

Could you please clarify what this means?

Thanks.

#CPLEXOptimizers
#DecisionOptimization

About CPX_PARAM_MIPCBREDLP:

If that parameter is on (the default) then the callback is invoked in context of the presolved model. That is, the cut you provide must be for the presolved model (which may be very different from the model you passed to CPXmipopt()).

If that parameter is off then the callback is invoked in context of the original model, the one you passed into CPXmipopt(). In that case CPLEX will first transform your cut to the presolved model (this is known as "crushing") and then add it to the nodelp. In some cases crushing may fail if CPLEX performed non-linear reductions during presolve, hence you should CPX_PARAM_PRELINEAR to 0 to avoid this.

I'll ask one of the cut experts to answer your question about the cut coefficients.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

Suppose the "original model", the one submitted to CPXmipopt() is:

Min cx

s.t. Ax = b

x >=0, integer

Suppose number of x variables is n

If I understand correctly, CPLEX internally converts this to a different but equivalent presolved model:

Min dy

s.t. Ey = f

y >= 0, integer

Number of y variables need not be n.

Now, the user has to convert the LP model to the "original model" by using functions:

int status = CPXchgctype(env, lp, n, indices, ctype);//ctype is 'I' denoting conversion of the n continuous x variables to integer variables

status = CPXchgprobtype(env, lp, CPXPROB_MILP);

The callbacks I have are setup thus:

After the above, I call CPXmipopt()

My cut separation function separate() creates cuts for the original model, i.e., in terms of the x variables and they are called by the callback functions during branch and bound of CPXmipopt(). Within both the user cut and the lazy cut functions, I access the x variables of the original model by 

status = CPXgetcallbacknodex(env, cbdata, wherefrom, cutinfo->x, 0, cutinfo->numcols - 1);

and then pass cutinfo->x as one argument to separate() function.

If the two parameter setting lines are commented out as above, and if I understood your response correctly, CPLEX should thrown an error since the CPX_PARAM_MIPCBREDLP 

parameter is on by default and the cut must have been in terms of the presolved model's variables. Am I right? Yet, CPLEX works just fine with my user defined cuts in terms of the x variables whether the parameters are On or Off. In both cases (whether the lines are commented out or not), CPLEX gets me the same optimal solution with exactly the same performance metrics (running time, number of branch and bound nodes).

#CPLEXOptimizers
#DecisionOptimization

Sorry, I am confused by your post. It is unclear to me why you think the user has to call CPXchgctype() or CPXchgprobtype(). That is not necessary.

Whether CPLEX raises an error in case CPX_PARAM_MIPCBREDLP=CPX_ON (the default) for your code depends on two things

1. Did presolve actually remove any columns? If not then the number of columns in original and presolved model are the same and CPLEX has no way to detect that your cuts are specified in terms of a different model.

2. How do you initialize cutinfo->numcols? Is this the number of columns in the original model or do you get this for example as the number of columns from the nodelp?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

The CPXchgctype() and CPXchgprobtype() are there since initially my x variables are continuous and I run my separation routines (via separate() function) on this initial LP. Then, when I no longer discover any more violated cuts, I convert the problem to integer by calling the above functions. They may not be needed if the user initially itself creates the IP directly.

 

>How do you initialize cutinfo->numcols? Is this the number of columns in the original model or do you get this for example as the number of columns from the nodelp?

This is the number of columns in the original model.

> Did presolve actually remove any columns? If not then the number of columns in original and presolved model are the same and CPLEX has no way to detect that your cuts are specified in terms of a different model.

Is there a way to check whether presolve removed any columns? Is there a way to get the presolve processed LP at each node?

You had earlier said:

>If that parameter is on (the default) then the callback is invoked in context of the presolved model. That is, the cut you provide must be for the presolved model (which may be very different from the model you passed to CPXmipopt()).

I guess my lingering question is the following: what does "the cut you provide must be for the presolved model" mean?

For e.g., if I am solving a capacitated vehicle routing problem, with assignment constraints and no subtour breaking constraints (in variables x_ij) initially, then if my separation routine identifies violated subtour breaking constraints in the current LP fractional solution (variables x_ij) at some node of the branch and bound tree, the cut I provide to CPLEX to add will only be in terms of this original model, i.e., variables x_{ij} right? Suppose there is a subtour 1->2->3->1 in the current LP solution at some node with each respective x_ij = 1, then my cut will be x_12 + x_13 + x_23 <= 2. This constraint is violated since the left hand side evaluates to 3 in the current LP solution of the original model.

 

What does "presolved model" here mean and how does the user have access to this? Is the presolved model also in terms of the x_ij variables with the same interpretation as the original model?

 

#CPLEXOptimizers
#DecisionOptimization

If your separation routine relies on the structure of the original model in any way, then you basically have no choice but to set CPX_PARAM_MIPCBREDLP=CPX_OFF and CPX_PARAM_REDUCE=0. As far as I understand, you are in this situation (and 99% of the users are, unless the develop completely generic cuts). Any structure present in the original model is potentially gone after presolve.

 

The "presolved model" is the model after presolve. Presolve is an operation that attempts to simplify the problem as much as possible. For example, it will try to tighten bounds on variables, remove redundant variables, remove redundant constraints, aggregate variables etc. This may change the problem significantly and variables may have a different meaning than they did before. CPLEX internally maintains information to map solutions and constraints between the presolved and the original problem. This is accessible but I don't think you need access in your situation.
 

The presolved model is what CPLEX actually solves. If CPX_PARAM_MIPCBREDLP is on, then any solution returned by CPXcallbackgetnodex() is in terms of the presolved model and any cut submitted via CPXcutcallbackadd() must be in terms of the presolved model. This means, that cuts can only reference variables that still exist in the presolved model. And separation can exploit only model structure that is still present in the presolved model.

On the other hand, if CPX_PARAM_MIPCBREDLP is off, then CPLEX will transform any solution returned by CPXcallbackgetnodex() from the presolved space to the original space before return. So the returned vector is in terms of the original model. Likewise, any cut submitted to CPXcutcallbackadd() must be in terms of the original space. CPLEX will automatically and internally translate this cut to the presolved space. Since the cut is passed in terms of the original space, it can use any variable present in the original model (and with its original meaning).

 

To see the difference between original and presolved problem, you can export your problem to a SAV file and then use the interactive like so

CPLEX> read myprob.sav
CPLEX> write myprob.lp
CPLEX> write myprob.pre
CPLEX> read mypob.pre
CPLEX> write myprob.pre.lp

Then compare myprob.lp and myprob.pre.lp, they represent the original and the presolved model respectively. In some cases the two models will be identical.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

Thank you. This really helps.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: AndreaTramontani

Hello,

Daniel already replied to your questions on CPX_PARAM_MIPCBREDLP and CPX_PARAM_PRELINEAR, and to all subsequent questions.

About this specific question:

> However, they are not in the same form as the cutval[] array that I populate and pass to the CPXcutcallbackadd() function.
> That is, the constraint in the .lp file seems to be multiplied by some fraction of the cutval[] entries that I pass via code.
> Is this the default behavior? Can the user disable this so that cutval[] entries/coefficients are faithfully replicated in the .lp file?

What CPLEX does when the user adds a cut (cutval/cutind arrays) with a callback (e.g., CPXXcutcallbackadd) is the following:
1. Transform the cut from the original model to the presolved model ("crushing"), assuming CPX_PARAM_MIPCBREDLP = CPX_OFF
2. Apply some scaling to the cut coefficients
3. Add to the nodelp the resulting crushed and scaled cut.

The user has no control on the cut scaling this operation cannot be disabled.
Of course, if presolve is disabled (or if the user adds cuts directly in the presolved space, i.e., CPX_PARAM_MIPCBREDLP = CPX_ON), then
the cut you can see in the nodelp is just a scaling of the cutval array passed to CPXXcutcallbackadd, so you should be able to "recover" somehow the "original" cut from the one
in the nodelp.
 

#CPLEXOptimizers
#DecisionOptimization