How to add a priori unknown user defined cuts in a branch and cut algorithm

[A-man]

Hi there,

I am wondering if it is possible to define the cuts added within a branch and cut algorithm at each node of the branch and bound tree "manually".

Here is roughly what I would like to do:


I have a MIP that should be solved with branch and cut. Cuts that should be added at each node are not known in advance. They are generated on the fly (i.e. at each node) by solving an auxiliary problem. These are the main steps of the algorithm:

1: At each node: Solve the MIP's LP relaxation optimally to get solution y.

2: Use solution y to solve an auxiliary LP problem in order to generate a cut c.

3: If cut c is violated by solution y, then add c to the problem and go back to step 1.
if no more violated cuts can be found and the current solution is not integer do branching on a fractional variable and do steps 1-3 for the resulting nodes, too.


In AMPL it is possible to define lazy constraints with suffix .lazy that are only added if they are violated. But as far as I understand, all of these constraints need to be known in advance (do they?), like e.g. inventory balance constraints in a lot-sizing problem, so that CPLEX can search the cut pool for violated constraints. As I have stated above, my cuts are NOT known in advance but they are generated by solving an auxiliary problem at each node. So they become known as soon as the auxiliary problem is solved.

Is there some way in AMPL (maybe with a feature like lazy constraints) to define and add cuts in such a way at each node of the branch and bound tree?

Thanks a lot in advance!

Have a nice day!

---

View this message in context: How to add a priori unknown user defined cuts in a branch and cut algorithm
Sent from the AMPL mailing list archive at Nabble.com.

[A-man]

--
View this message in context: http://ampl.996311.n3.nabble.com/How-to-add-a-priori-unknown-user-defined-cuts-in-a-branch-and-cut-algorithm-tp11555.html

[Robert Fourer]

After AMPL starts a CPLEX run, AMPL does not have any further communication with CPLEX until the end of the run when a solution is returned. So all of the lazy constraints must be generated before CPLEX begins, and additional cuts cannot be passed to from AMPL to CPLEX in the middle of the CPLEX run. If you want to have CPLEX manage the branch-and-bound tree while adding your own cuts during the CPLEX run, then you need to use the "callback" feature in one of the lower-level CPLEX programming interfaces available from IBM.

If you are going to manage the branch-and-bound tree yourself then you can do it in an AMPL script or (for large problems or more complicated situations) in a program that makes calls to the AMPL API. But in this case CPLEX would only be used for solving the continuous LP relaxations at the nodes.

Bob Fourer
am...@googlegroups.com

[A-man]

Dear Mr. Fourer,

thanks a lot for your helpful reply! After reading your answer two more
questions crossed my mind:

Firstly:
My initial intention was just to add constraints at each node of the branch
and bound tree in the middle of a cplex run so that cplex would still be
able to automatically add other cuts. That is why I would have liked to use
lazy constraint callbacks through AMPL. In your post you mentioned
lower-level cplex programming interfaces. I'm not sure what you mean
exactly. Did you mean something like OPL or cplex optimization studio?

Secondly:
If I interpret your reply correctly, you recommend to use a program that
makes calls to the AMPL API in case problems get large. Why is this superior
to coding the branch and cut algorithm in a .run-file?

Many thanks again!

Have a nice day!







--

View this message in context: http://ampl.996311.n3.nabble.com/AMPL-10814-How-to-add-a-priori-unknown-user-defined-cuts-in-a-branch-and-cut-algorithm-tp11570p11602.html

[Robert Fourer]

You might be able to add cuts through callbacks to the OPL scripting language (which is different from the OPL modeling language). An alternative is to use a CPLEX API; there are APIs for calling CPLEX from C++, Java, Python, and other languages. All of these are part of the IBM CPLEX Optimization Studio product for which further information is available from IBM.

AMPL script (.run) files provide a convenient way to program algorithmic schemes with AMPL models, but they do not execute as fast as compiled programming languages, particularly if there are a lot of nested loops that do not contain solves. Also general-purpose programming languages offer more advanced features for building complex programs and data structures. The AMPL APIs let you take advantage of these features without giving up the convenience and reliability of AMPL for defining your models and generating optimization problems.

Bob Fourer
am...@googlegroups.com


-----Original Message-----
From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of A-man