How to stop the solution process of a linear problem when its lower bound is positive?

[MFABRI]

Dear,

I have a question about the AMPL and its interaction with the solver CPLEX.

I need to stop the solution process of a linear problem when its lower bound, calculated by some CPLEX´s heuristics, is positive. 

So, when the lower bound is bigger than zero, the optimization is not relevant anymore and I want to interrupt it in the middle of the process, saving time.

Therefore, I would like to know which code does that evaluation and stops the solution process if necessary.

Did I explain my question properly? 

Could you help me with that, please?

Sincerely,

[fbahr]

Setting an absolute bound stopping criterion for MIP
> http://www-01.ibm.com/support/docview.wss?uid=swg21449686

> Question

Is there any parameter to instruct CPLEX MIP to stop when a given value is reached as solution?

>Cause

CPLEX does offer an absmipgap parameter that tells CPLEX to stop the optimization when the difference between the current solution and the bound given by the best node is within a specified absolute value. [..] However, there is no parameter to tell CPLEX to stop once the current solution has reached a certain absolute value. ...

Yet, not all hope is to be lost.

Let's say your problem looks sth. like this:

var x {1..10} binary;
param p {1..10} = Uniform01();
param sgn {i in 1..10} = if (i mod 2) = 0 then 1 else -1;

maximize obj:
  sum{i in 1..10} sgn[i]*p[i]*x[i];

s.t. cons {j in 1..5}:
  sum{i in 2*j-1..2*j} sgn[i]*x[i] = 0;

s.t. nontrivial:
  sum{i in 1..10} x[i] >= 1;

We can rewrite this [w/o big efforts] into a problem that satisfies you needs:

var z >= 0;
var x {1..10} binary;
param p {1..10} = Uniform01();
param sgn {i in 1..10} = if (i mod 2) = 0 then 1 else -1;

minimize obj:
  z;

s.t. con0:
  sum{i in 1..10} sgn[i]*p[i]*x[i] + z >= 0;

s.t. cons {j in 1..5}:
  sum{i in 2*j-1..2*j} sgn[i]*x[i] = 0;

s.t. nontrivial:
  sum{i in 1..10} x[i] >= 1;

I. e., if the initial formulation has solutions with positive objective function values, the rewritten one stops with z* = 0, otherwise they are equivalent.

--fbahr

[fbahr]

P.S.: Having this said, ...and after running a series of [toy] test problem: the proposed reformulation is almost never advantageous. Alternatively, you might consider initially running problem instances with a relatively large mipgap tolerance -- and re-(warm)start instances [after adjusting the mipgap parameter] if they terminated with a negative objective function value.

[fbahr]

In your AMPL installation location you'll find a README.cplex.txt file[1] which explains how to set CPLEX solver parameters.

The equivalent to SET MIP LIMITS SOLUTIONS[2] is

option cplex_options $cplex_options "mipsolutions=...";

--fbahr

[1], alternatively: http://www.ampl.com/BOOKLETS/README101.cplex
[2]: http://pic.dhe.ibm.com/infocenter/cplexzos/v12r5/topic/com.ibm.cplex.zos.help/UsrMan/topics/discr_optim/mip/usage/11_terminate.html

On Thu, Feb 27, 2014 at 12:30 AM, Marcelus Fabri <marce...@gmail.com> wrote:

Dear Florian, 

Thank you very much for your comments and ideas. I remember that when i used to work only with cplex (generating LP files) . We could set mip solution bounds, if I am not mistaken the commands were: set mip limits solutions . Is there a way to set cplex through ampl?

thanks again

[Robert Fourer]

This and related questions have come up before:  How can you stop the MIP solution process when the lower bound is >= a certain threshold, or when the upper bound is <= a certain threshold?  There are approaches to manipulating the formulation and/or currently available options, so as to get more-or-less these effects, but they tend to have serious disadvantages, such as making the solution process a lot harder or failing to return a useful solution in runs where the threshold is not reached.

 

There is also the option of rewriting your model to use the solver's API (callable library) so that you can use callbacks to implement the desired threshold.  This tends to tie you to one solver, though.  And it seems like potentially a great deal of work just to implement such a simple option.

 

As far as I know, no threshold options of these kinds currently exist.  It might turn out that one of the MIP solvers that we support has a hidden option of the kind you want, or that the developers will add such an option, in which case we can also add it to the AMPL-solver interface.

 

If indeed there are no such options available, I think it could be explained by the solver developers' focus on returning a good solution.  If you are minimizing and you stop as soon as the lower bound is >= some threshold, it is very possible that the integer-feasible solution returned will be very far from optimal (or that no feasible solution will have been found yet).  So this would be a bad stopping criterion if you were just trying to solve one problem.  What the solver developers may not have considered is the situation where someone is solving many MIPs, with the property that if any MIP's lower bound reaches the threshold then it can't possibly have an interesting solution and can be discarded.  (Curiously, this is much like the "cutoff" criterion that MIP solvers employ to stop the dual simplex method when it is solving a node subproblem.)

 

Bob Fourer

am...@googlegroups.com

 

 

From: am...@googlegroups.com [mailto:am...@googlegroups.com]

On Behalf Of MFABRI
Sent: Tuesday, February 25, 2014 7:21 PM
To: am...@googlegroups.com
Subject: [AMPL 8090] How to stop the solution process of a linear problem when its lower bound is positive?