Originally posted by: Lessi

I try to solve a maximization problem by branch & check method. I use populate() method in Cplex to enumerate all MIP solutions. Each solution to the MIP problem is a binary sequence (y_0,y_1,...,y_N) where y_i in {0,1}

1. When a feasible solution "s" I found, I need to check some properties. Therefore, the callback function that I write the verification code should be the ILOINCUMBENTCALLBACK since

I am able to access the solution there with the function getObjValue(), getValue() and getValues().

2. If I find a feasible solution in step 1 after checking procedure. suppose its objective value is X, I want to ignore all solutions that have an objective value less than X, therefore, I will add a constraint of form: obj >= X+1.

So I want to know whether the callback I use to add the constraint (obj >= X+1) is the UserCutCallBack instead of LazyCutCallback since it will allow me to stop branching earlier? Is it true. Since it is the maximization problem, so it is a valid cut. 

3. If a feasible solution is not found in step one, I want to add a knapsack constraint of form :  sum(y_u) for all u in s <=  (size of s) - 1. The goal is to ignore enumerating and checking solutions that consist "s" as a sub-solution. 

Can I  add this cut as a usercut? or I need to use lazy cut? or another function? Since it will eliminate some solutions so it violates the description of usercut so I am not sure if it is correct, but it is since I think usercut is stronger than lazycut because it is executed after solving an LP while lazycut is executed when a feasible solution is found? Do I understand those concepts correctly?

Thank you for your advice,

Lessi

Originally posted by: EdKlotz

2. If I find a feasible solution in step 1 after checking procedure. suppose its objective value is X, I want to ignore all solutions that have an objective value less than X, therefore, I will add a constraint of form: obj >= X+1.

So I want to know whether the callback I use to add the constraint (obj >= X+1) is the UserCutCallBack instead of LazyCutCallback since it will allow me to stop branching earlier? Is it true. Since it is the maximization problem, so it is a valid cut. 

In terms of correctness, you can express this either as via user cuts or lazy constraints.   But in terms of speed, based on your description you have no interest in exploring node LPs with objectives < X+1 once you have a solution with objective X.   However, I wonder if you really need to use the populate method at all.  The populate method is essentially no different than the regular branch and cut method until a first feasible solution is found (after any checking done by an incumbent callback).   Based on your description, as soon as you find a feasible solution, you establish a cutoff value that is applied during the rest of the optimization.   If so, than I don't think you need  to use populate at all.

3. If a feasible solution is not found in step one, I want to add a knapsack constraint of form :  sum(y_u) for all u in s <=  (size of s) - 1. The goal is to ignore enumerating and checking solutions that consist "s" as a sub-solution. 

Can I  add this cut as a usercut? or I need to use lazy cut? or another function? Since it will eliminate some solutions so it violates the description of usercut so I am not sure if it is correct, but it is since I think usercut is stronger than lazycut because it is executed after solving an LP while lazycut is executed when a feasible solution is found? Do I understand those concepts correctly?

I think the following paragraph in the user manual on differences between user cuts and lazy constraints answers this question:

Cuts that are based on optimality and that remove integer feasible solutions without removing all optimal solutions are known as optimality-based cuts. Optimality-based cuts do not fit the definition of either a user cut nor a lazy constraint. For example, symmetry-breaking constraints are sometimes known as optimality-based cuts because symmetry-breaking constraints can remove integer feasible solutions without removing all optimal solutions. Symmetry-breaking constraints are not user cuts in the sense addressed here. Symmetry-breaking constraints are not necessarily lazy constraints either. However, CPLEX can support optimality-based cuts as lazy constraints. If you add an optimality-based cut as a lazy constraint in your model, you can also add it to the user cut pool. This practice of adding an optimality-based cut as a lazy constraint and simultaneously adding it to the user cut pool makes sure that CPLEX checks the optimality-based cut at each node relaxation as well as when CPLEX finds an integer feasible solution.

Originally posted by: Lessi

For your comment to question  3: In my situation, I solve a master problem (a relaxation of the original problem) and then solve a slave problem to check if the solutions to the master problem meet all constraints of the original problems.

An (optimal) solution "s" to the master problem may not be feasible regarding the constraints of the slave problem. In this case, I want to add a constraint to eliminate solutions that contain "s" as a sub-solution (each solution corresponds to a subset of a set - " sum(y_u) for all u in s <=  (size of s) - 1.")

For your comment to question 2 (If so, then I don't think you need  to use populate at all.): This is the reason that I need to use populate() method.

Many thanks! Happy New Year & Happy Holiday.

Lessi.