Originally posted by: LeandroCC

I want to solve a very large model using only a subset of the binary variables to start with. So I create the whole model, and then for the undesirable variables I set their UB to 0.

Then what I do is the following:

cplex.setParam(IloCplex::LimSolInt, 1);
 
while ( !optimal )
{
  cplex.solve();   //it will stop after EVERY node
  check reduced costs;
  if (reduced_cost(var) < 0)
     var.setUB(1.0);
}

Apparently it works. What happens is that whenever I change the UB of a variable (allow the model to use it, or add it to the model in CG terms), CPLEX will re-start the optimization. Otherwise, it continues from where it stopped.

Questions:

1. is this an efficient way to implement it? Can I achieve the same through a callback? Can it be made more efficient by adding a vector of constraints (bounds on each variable) and querying the dual values associated with each of these constraints? (I tried and didn't like it, got stuck in a bug somewhere....)
2. Can I add the variable (free its bound) without having to restart the optimization? (because I lose all cuts that cplex worked so hard to add, and maybe some other structure of the tree)...
3. is there a way to allow presolve to be turned on (or partly on) in this case?

Thanks in advance for any info!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I think you can use callbacks to reduce but not eliminate restarts. I don't have docs in front of me, so I may be slightly off, but what I would try a cut callback that checks the reduced costs. If you are not going to toggle a bound, the cut callback does nothing. If you are going to toggle a bound, it sets a semaphore in your code indicating what the change is to be and then aborts the CPLEX run.

So you still do a full restart after each column is "added", but you avoid the stop/warm start when nothing changes.

Turning on a column would likely make previous cuts and/or previous pruning decisions invalid, so I'm pretty sure there is no way to do this in a single call to solve().

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

If you are solving a MIP, then there is no way to resume the solving process after having changed the model. CPLEX will always start from scratch; only the feasible solutions from the previous solve will be tried as a MIP start in the subsequent solve.

A very common (heuristic) approach for solving very big MIPs is the so-called branch-and-generate framework. Here, you would solve the LP relaxation using column generation (you would need to disable dual presolve reductions and remove the integrality constraints, then solve the model as LP, repeatedly add/activate columns with negative reduced costs, and resolve, typically with primal simplex). Then, you could fix one or many of the variables with fractional value to some integer (simulating branching), and resolve the LP, again using column generation to activate even more variables. Repeat this process until you have generated a reasonable number of variables, then turn the problem into a MIP and let CPLEX solve it (enable dual presolve reductions again!).

The final solution of this process is not necessarily optimal, since you have not generated all columns of the problem. If you like, you could now solve the fixed LP to get reduced cost values and duals and generate/activate additional columns, then solve the problem again as a MIP.

As you can see, the LP based branch-and-generate process is basically a procedure to quickly generate a bunch of useful columns. So it is a kind of preprocessing step to the main MIP based procedure (which you described in your post).

In the MIP based procedure I would not stop immediately after every new incumbent solution. I would let CPLEX continue to collect more solutions, and then inspect all of them (using the solution pool feature) to generate new columns for all of those solutions. In this way, you are generating many more useful columns per iteration of your algorithm.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: LeandroCC

Thanks a lot for your comments Paul and Tobias.

A further question raised by Tobias' comment: if I want to have an exact approach, do I need to check for reduced costs for every feasible solution or for every node? According to the last part of your answer, I assume it is for every solution, but I've been doing it for every node (and using Paul's suggestion of the cut callback also implies we need it for every node).
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Leandro: Just to be clear, I suggested a cut callback because I interpreted your original post as meaning you checked reduced costs at every node. If you want to check reduced costs only when an integer feasible solution is obtained, change the user cut callback to a lazy constraint callback.

As far as I know, both approaches are heuristic, as is the approach Tobias mentioned. There are frameworks available to do actual branch-price-and-cut (MIP column generation), and I think some of them can use CPLEX as the LP solver.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, all approaches that are discussed in this thread are heuristics.
To get a true optimal solution, you would need to do branch-and-price, which CPLEX does not support.
As Paul said, there are branch-and-price and branch-cut-and-price frameworks available, one of them being SCIP (scip.zib.de), in which you can use CPLEX as LP solver.
But you should be aware of the fact that branch-and-price (and even more so branch-cut-and-price) is one of the most complicated algorithms to implement within integer linear programming, both from the practical and theoretical side.
You need to know exactly what you do, in particular how you organize the branching decisions so that you pricing problem in the nodes does not become too hard to solve.
Tobias
#CPLEXOptimizers
#DecisionOptimization