Originally posted by: PeteCacioppi

I've never applied lazy constraints before, and want to get a feel for how challenging the following task is, and some pointers on most relevant sections of the documentation.

The task is to run an optimization that minimizes one objective (p), and from amongst the solutions that achieve this goal, select the solution that minimizes a secondary goal (s).

My sense is this can be accomplished by

• Set CPLEX to enumerate all possible solutions in a solution pool.
• Maintain a constraint of the form "s <= bestS" where "bestS" is the best possible secondary value found so far.

Does this sound like a valid technique for lexicographical optimization?  I'm using Java. Can you point me at some sections of the documentation to help me get jump started?

Thanks

Originally posted by: EdKlotz

I don't think lazy constraints are the best way to accomplish this.   First of all, telling CPLEX to enumerate all possible solutions in the model disables a lot of CPLEX's node pruning features and will slow performance.  In that case, CPLEX can only prune a node when enough branches have made it infeasible.   No pruning based on the primary objective is possible.   Now, you could restrict the solution pool to enumerating just the optimal solutions, applying a lazy constraint callback as you described to optimize the secondary goal.   But, this seems more complicated than just minimizing the first objective, adding a constraint that the first objective equals the optimal value you just obtained, then minimizing the second objective.    I think that would be easier and also probably run faster.   Is there some reason you don't want to take that approach (e.g. you may want to generalize the priorities on the two objective from the pure lexicographic approach you mention above to something involving Pareto optimality)?

Nonetheless, if you want to take this approach, have a look at the BendersATSP.java example that comes with the CPLEX distribution to see how to use the IloCplex.LazyConstraintCallback method to add lazy constraints dynamically during the course of the optimization like you describe.    However, this example assumes a regular MIP optimization, not the 2-phase optimization associated with the solution pool.    The Populate.java example shows how to use the solution pool feature to accumulate solutions within 10% of optimal.   So, essentially you could modify that example to have the solution pool find solutions that are optimal, then merge some of the code in the BendersATSP.java example that uses the LazyConstraint callback.   You would need to replace the code in BendersATSP.java that generates subtour elimination constraints for a TSP problem as lazy constraints with your lazy constraints involving the secondary objective.   You should also have a look at the documentation on the solution pool in the user manual.    If you are going to use callbacks with the solution pool, you need to be clear on how the solution pool operates.  Namely, it is a two phase approach.   In the first phase, CPLEX solves the MIP to optimality (or whatever stopping criterion you specify), but it retains nodes it would normally prune if they have potential to yield sub optimal solutions that are still of interest based on the solution pool parameters you have specified (e.g. solutions within 10% of optimal as in Populate.java).   In the second phase, after it knows the optimal objective value,
 CPLEX processes the remaining nodes, branching as needed to find additional solutions.    For some slides with additional info on this, try

http://www.stanford.edu/dept/ICME/docs/seminars/Danna-2008-01-30.pdf

and if you need to dig even deeper, have a look at

Emilie Danna, Mary Fenelon, Roland Wunderling,
Zonghao Gu. Generating multiple solutions for mixed
integer programming models. Proceedings of IPCO
2007. LNCS 4513, pages 280-294.

Another approach to consider if you may want to generalize your prioritization of the two (or more) objective involves using a branch  callback function.    You probably would not need to change CPLEX's branching selection (although you could if you thought that would help performance).   Rather, you would use the makeBranch(int i,java.lang.Object data)
method branch as CPLEX would do, but you would call the prune() method of IloCplex.BranchCallback to prune certain nodes based on the two (or more) objectives rather than the single objective criterion CPLEX uses.

Originally posted by: PeteCacioppi

Yes, I meant to say enumerate all the optimal solutions in the solution pool, and from those choose the optimal for the secondary objective.

I am trying to perform a comparison test of a somewhat sophisticated algorithm that was published a few years ago, to show my approach is faster.

This algorithm is doing something even a bit trickier than what I describe, but schematically it is the same.

However, the key step is it is forcing the secondary objective to be strictly better with each cut. So, when an optimal solution with primary result P also has secondary result S, it applies the lazy constraints  s <= S - epsilon and primary = P. . This technically renders the current solution infeasible. If it also renders all remaining solutions infeasible, then current solution is returned. Otherwise, a new solution is discovered.

This is a very tricky method to achieve a fairly straightforward result, but the claim is it improves run time.

Originally posted by: EdKlotz

 > I am trying to perform a comparison test of a somewhat sophisticated algorithm that was published a few years 

> ago,   to show my approach is faster.

Well in some sense then your best bet is to use the solution pool and enumerate; since that will probably be the most inefficient way for CPLEX to accomplish the task, it is most likely to show that your approach is faster.

However, if you want a more fair comparison, where each method is running as quickly as possible, I think the basic minimize-constraint-minimize approach that doesn't use callbacks at all is the way to go.   Fundamentally, CPLEX should have the opportunity to make use of the two objectives involved during the course of the optimization at all times.    That is not the case with the solution pool approach, which has no information about the secondary objective in the actual problem to be optimized at all.   Nor is that the case with Paul's incumbent callback approach, which only looks at the secondary objective when evaluating incumbents.   The Branch callback approach I described does incorporate both objectives into the pruning step of the branch and cut algorithm, but it doesn't consider it anywhere else.  And, all three of these approaches require that you disable dual presolve reductions and any other dual based performance improvements such as anti symmetry reductions.  The minimize-constraint-minimize approach incorporates the two objectives, albeit separately in the two minimizations.   And, as long as you only need one solution for each of your two objectives, you don't need to disable any of the dual tightening features.

All that being said, if your approach is more flexible in terms of extensibility beyond finding a single lexicographically optimal solution for two objectives, then it's less clear which approach you should compare it to.  The minimize-constraint-minimize approach is probably less flexible than the other approaches discussed here.  But, I still contend that using the solution pool to enumerate all solutions except for those you eliminate via lazy constraints will probably be the most time consuming of all the approaches discussed here, and therefore the least suitable for a fair comparison.    Incumbent or branchcallbacks, or perhaps a combination of both, would  probably offer a more fair comparison.

Originally posted by: PeteCacioppi

It is probably the case that the original algorithm is doing something more like Branch callback than it is solution pooling.

Sorry, this isn't making sense to me. If you know that primary = P is optimal, you can add that constraint (once) and then minimize the secondary objective. You do not need to add cuts constraining the secondary objective. That's assuming you are not using the solution pool. If you use the solution pool at intensity 4 (find all optimal solutions), you can just filter out the ones that are suboptimal on the secondary objective.

Originally posted by: PeteCacioppi

My understanding of the combinatorial approach is that it is well positioned to exploit situations such as the following :  the best result for the primary is P, and, from amongst those solutions that achieve P, there are only a few possibilities for the value of the secondary.

When P is achieved, you apply a cut that forces improvements to the secondary. The idea is that this will be quicker than restarting the optimization.

At any rate, I'm not a huge fan of this idea, and am probably not the best person to defend it. A two-phase solving process makes more sense to me.  I only wanted to give this approach an airing and get some feedback. Thanks for your time.