Originally posted by: davidrey123

Hi,

I have some questions regarding user cuts and lazy constraints, as well as their usage through callbacks. I apologize if these have already been answered in other threads and, if so, please redirect me to the relevant answer(s).

1. What is the difference between a traditional linear constraints and a user cut from an implementation perspective? I understand that from a theoretical standpoint a user cut is not necessary to find the optimal of a problem, and that its incorporation in a MILP is only to strengthen the LP-relaxation of the MILP. But from an implementation perspective, what is the difference between writing a constraint a as traditional linear constraint or as a user cut? Essentially, if I have identified some user cuts for my problem, why shouldn't I include them in the formulation as traditional linear constraints?

2. What is the benefit of using implementing user cuts or lazy constraints through control callbacks? My understanding is that user cuts and lazy constraints can both be added using component libraries which do not require control callbacks. Yet, when reading about user cuts and lazy constraints, it seems that they are often implemented through control callbacks. What is the intention behind implementing user cuts and lazy constraints through control callbacks? Is this expected to offer more control on progress of the Branch-and-Cut algorithm because callbacks can be triggered based on specific conditions, whereas using component libraries to add user cuts and lazy constraints to the MILP would simply let CPLEX decide on the timing of their usage?

Thank you,

-David

Valid inequalities as cuts or linear constraints: This is a potential performance issue: If you put the inequalities as constraints then they are definitely part of the model. Any relaxation will have to solve a larger LP, no matter whether these constraints are violated or not. If you only put the inequalities as cuts then the working model will be smaller and CPLEX will only add those cuts if they are violated, i.e., if they are going to change something. You probably have to experiment which of the two strategies is faster in your case.

Callback vs. static tables: If you provide the constraints/cuts as static table then you have to list them all at once. That sometimes is an issue if there are many of them, in particular if there are exponentially many of them. A callback has the advantage that CPLEX gives you a solution and asks for a constraint/cut to cut off this particular solution. So you need to generate only those constraints, that cut off that particular point (while for a static table you have to create all constraints that cut off any potential point). So a callback can save both space and time. Again, you may have to test which strategy works better for your case. If it is feasible to enumerate all cuts/constraints before starting the solve then that is probably more efficient than using a callback,

Originally posted by: davidrey123

Hi Daniel,

Thank you for your answers, that clarifies a lot. Just a few follow-ups.

If you only put the inequalities as cuts then the working model will be smaller and CPLEX will only add those cuts if they are violated

My understanding is that If the inequalities are defined as user cuts, CPLEX may add them at any point in the B&C, but if the inequalities are defined as lazy constraints, they will only and always be checked when an integer solution has been found, is this correct? Is the choice of imposing valid inequalities as user cuts or lazy constraints problem-dependent? For instance, subtour elimination constraints in the TSP (assuming they are separated by callbacks), would you recommend passing them as user cuts or lazy constraints?

A callback has the advantage that CPLEX gives you a solution and asks for a constraint/cut to cut off this particular solution

Are control callbacks automatically triggered before or after each CPLEX LP-relaxation solve (i.e. at each node in the B&C tree)? Could you please recommend a CPLEX example to get started with such node-level callbacks? I would like to understand how to trigger control callbacks appropriately.

Thanks again for your time,

-David

If you only put the inequalities as cuts then the working model will be smaller and CPLEX will only add those cuts if they are violated

My understanding is that If the inequalities are defined as user cuts, CPLEX may add them at any point in the B&C, but if the inequalities are defined as lazy constraints, they will only and always be checked when an integer solution has been found, is this correct? Is the choice of imposing valid inequalities as user cuts or lazy constraints problem-dependent? For instance, subtour elimination constraints in the TSP (assuming they are separated by callbacks), would you recommend passing them as user cuts or lazy constraints?

Please take a look at this chapter in the user manual: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/progr_adv/usr_cut_lazy_constr/01_uc_lc_title_synopsis.html

I think you are missing an important difference between user cuts and lazy constraints: user cuts are not required for correctness. No integer feasible solution will ever violate a user cut (even if the cut is not in the formulation). Results will be correct even if CPLEX just ignores all cuts. Lazy constraints are required for correctness. They may cut off solutions that are otherwise integer feasible. They are a way to somehow "hide" part of the problem formulation from CPLEX. CPLEX is not allowed to ignore lazy constraints. Subtour elimination constraints are lazy constraints. If you only specify them as user cuts then CPLEX is allowed to return a solution with subtours!

A callback has the advantage that CPLEX gives you a solution and asks for a constraint/cut to cut off this particular solution

Are control callbacks automatically triggered before or after each CPLEX LP-relaxation solve (i.e. at each node in the B&C tree)? Could you please recommend a CPLEX example to get started with such node-level callbacks? I would like to understand how to trigger control callbacks appropriately.

There are different kind of callbacks, depending on what you want to do. I suggest to start with this chapter of the manual: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/progr_adv/callbacks_basic/01_cb_title_synopsis.html

As of version 12.8 there also is the generic callback which provides a different approach. If you can achieve what you want to do using a generic callback then this is preferred over control callbacks. The generic callback is described at https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/progr_adv/callbacks/introCallbacks.html.

Originally posted by: davidrey123

Hi Daniel,

Thanks for the additional feedback and pointers, that clarifies things for me.

Cheers,

-David