Use of lazy suffix

[Pratim Vakish]

Hello,

I know that a novelty of CPLEX 10 is that it recognizes the suffix .lazy on constraints.
I also know how to use and define the lazy suffix using AMPL:
suffix lazy IN;
let {i in ORIG, j in 1..J} Flow[i,j].lazy := 1;

The following values can be given to the suffix lazy:
lazy := 1 ; CPLEX considers the corresponding constraint as a lazy constraint;
lazy := 2 ; CPLEX considers the corresponding constraint as a user cut;
lazy:= 3; CPLEX considers the corresponding constraint as both lazy constraint and user cut.

My question is:
What does it mean for CPLEX that a constraint is lazy, or is a user cut, or is both?
How will CPLEX use a lazy constraint in the branch-and-cut algorithm?
How will CPLEX use a user cut in the branch-and-cut algorithm?
How will CPLEX use a constraint defined as both user cut and lazy constraint in the branch-and-cut algorithm?

What is the differnce between there three options? What is the respective impact on these three options on the branching algorithm?

Pratim
_________________________________________________________________
All-in-one security and maintenance for your PC.  Get a free 90-day trial!
http://www.windowsonecare.com/purchase/trial.aspx?sc_cid=wl_wlmail

[Robert Fourer]

Pratim,

.lazy = 1 is for lazy constraints. These constraints must be satisfied in a
feasible solution, but initially CPLEX does not put them all into the
problem being solved; it puts in only those that have been violated by a
solution that has been found. Possibly only a small fraction of the lazy
constraints will need to be put into the problem explicitly, and then the
rest will turn out to be satisfied anyhow; if this is the case then the work
of solving might be reduced, because a smaller constraint matrix and basis
matrix are used.

.lazy = 2 is for user cuts, and applies only when there are integer
variables. The user cuts are implied by the other constraints, and so they
are not needed at all; but they cut off some fractional solutions and so may
yield better lower bounds for the branch-and-bound procedure, thereby
speeding its search of the solution space. CPLEX does not put all of these
cuts into the problem it is solving, but rather only includes ones that cut
off a fractional solution that has been obtained at some node of the search
tree. Using only these "active" cuts may reduce solution time, because a
smaller constraint matrix and basis matrix are involved.

I don't see any reason why it could help to declare a constraint to be both
a user cut and a lazy constraint. As a user cut, the constraint would
always be satisfied, so there would be no reason to add it using the lazy
constraint mechanism.

Bob Fourer
4...@ampl.com

[Steve@UC]

I am frustrated with the documentation for ampl/cplex. I have an
unrestricted academic license for both products, and the manual with
date January 2006 and file name "amplcplex100userguide.pdf", and this
is the 2nd or 3rd time this year that features valuable to me have been
revealed in this forum, that are not found in my manual. Is there any
other source of documentation or addenda?

[Robert Fourer]

There's some more information in a file named README.txt that should have
been included with your documentation. I am attaching a copy to this
message.

The lazy constraints and user cuts don't seem to be documented in any of the
AMPL/CPLEX materials, though they're mentioned in the regular CPLEX user's
guide. That's clearly something to be fixed in the next release.

Bob Fourer
4...@ampl.com

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

[Benoît Martin]

Hello, I want to use lazy constraints and I don't understand how to apply the suffix lazy. Indeed, in the examples on this group, it is always added on 'let' statement (for example in this thread, let {i in ORIG, j in 1..J}  Flow[i,j].lazy := 1;).
But I write my constraint as

min obj..

subject to

constraint1 {i in I, j in J} x[i,j]+r[i,j]<=t[i,j]

Where can I put the lazy suffix then?

Thanks!

[Robert Fourer]

Using a "let" statement, you can write

suffix lazy IN;
constraint1 {i in I, j in J}: x[i,j] + r[i,j] <= t[i,j];
let {i in I, j in J} constraint1.lazy := 1;

However for a simple definition you have the option of defining the suffix values at the end of the constraint definition:

suffix lazy IN;
constraint1 {i in I, j in J}: x[i,j] + r[i,j] <= t[i,j], suffix lazy 1;

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of Benoît Martin
Sent: Wednesday, January 18, 2017 4:39 PM
To: AMPL Modeling Language

[Benoît Martin]

Thanks Bob!

[Benoît Martin]

I noticed something strange to me..
I am solving  a MILP (minimization) and when I set certain constraints to be lazy, CPLEX seems to struggle to find integer solutions during the branch-and-bound .

Hence, even though the lower bound rapidly converges towards the value I know the objective must take, as there is no progress in the integer incumbent (or even no incumbent), it doesn't converge.
Do you have an explanation for that?

Thanks,

Benoît

[Robert Fourer]

With lazy constraints, CPLEX may be finding integer solutions, but they may violate some of the lazy constraints. Then CPLEX has to add those violated lazy constraints, and when it solves again the solution may become fractional. So finding a truly feasible integer solution may become harder, and defining lazy constraints may not be helpful. Lazy constraints are most likely to be helpful when (1) there are a very large number of lazy constraints, so that node subproblems are much faster to solve when they are left out, and (2) almost all of the lazy constraints are satisfied even when they are left out of the problem.

[Prat]

Hello Bob,

I would like to know:

- which solvers I can use to define lazy cuts with AMPL.

- for which type of problems I can use lazy cuts in AMPL. 

Is it only doable for mixed-integer linear problems? Can it also be used for mixed-integer nonlinear problems? Or for nonlinear continuous optimization problems?

Thanks,

Prat

[AMPL Google Group]

Lazy constraints are supported for mixed-integer problems by CPLEX, Gurobi, and Xpress. Each has a somewhat different way of specifying lazy constraints, which you can find by searching the option listing for "lazy". There are links to the option listings on our solver pages:

https://ampl.com/products/solvers/solvers-we-sell/cplex/
https://ampl.com/products/solvers/solvers-we-sell/gurobi/
https://ampl.com/products/solvers/solvers-we-sell/xpress/

As far as I know about these implementations, lazy constraints have to be linear and they have to appear in mixed-integer problems. Most often them are used with mixed-integer linear problems, but they might work with certain mixed-integer quadratic problems that these three solvers support -- it's hard to tell from the documentation.

I don't know of any lazy constraint implementations for continuous problems or for general mixed-integer nonlinear problems.

--
Robert Fourer
am...@googlegroups.com

{#HS:901288350-49207#}