Long Run Time/Tracking CPLEX Progress

[Tomas Zunino]

Hello,

I'm running a Linear Program with just over 10,000 binary variables
and 17,500 constraints. I'm fairly certain my problem is feasible
(when I've slipped up and created infeasible problems CPLEX identifies
it immediately), but I've tried running CPLEX through AMPL only to
have it run for over 24 hours (I abandoned the process with ctrl+c, so
I'm not sure how long this would have taken).

Is this run time typical? Is it possible to track CPLEX's progress to
diagnose what the issue might be?

Thanks,
Tomas

[Marvin Hagen]

Hi Tomas,

 

I ran across this option in the ILOG AMPL CPLEX manual which may fulfill your needs:.

 

option cplex_options  'mipdisplay=2';

 

More info will be printed when setting to 3,4,& 5, if needed.

 

Hope this helps.

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To post to this group, send email to am...@googlegroups.com.
To unsubscribe from this group, send email to ampl+uns...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/ampl?hl=en.

[Tomas Zunino]

Hi Marvin,

Thanks for the help. I tried it out, but I could not figure out what
was going on. I also tried to use the solvers at www.neos-server.org,
but they all timed out.

Is there a reason why a problem with 10,000 binary variables and
17,500 constraints should take so long? I did note that no integer
solution was provided when the algorithm was interrupted/timed out.
Would providing an initial solution/basis reduce the time needed to
solve?

Thanks,
Tomas

[Marvin Hagen]

 

Yes, my understanding is that providing the sovler with a "warm" start will generally reduce the solution time.

[Robert Fourer]

A linear optimization problem in 10,000 continuous variables should not take
very long, unless it has some pathological characteristics such as extensive
degeneracy or greatly varying coefficient magnitudes. But optimization over
binary variables is intrinsically a much harder problem, and while some such
problems with even hundreds of thousands of binary variables turn out to be
easy, there are others with fewer than a thousand variables that cannot
currently be solved to optimality in any amount of time that you'd be
willing to wait. In my experience it is not at all unusual that a problem
of the size you have may experience very long run times.

To improve performance you really do need to look at the "mipdisplay=2"
output. When the "gap" stays large and the "nodes left" grows steadily,
then chances are that CPLEX (or any similar solver) will take a very long
time. If you know a feasible solution that gives a much better objective
value than what appears in the "best integer" column, then setting the
variables to this solution before solving may be helpful. In particular if
nothing appears under "best integer" then CPLEX was unable to find a
feasible solution and you could definitely help things out by supplying one.
(But if you can't find a feasible solution either then it's possible that
none exists.)

Bob Fourer
4...@ampl.com

[Tomas Zunino]

Using other solvers, I've found that when they've timed out, they
provide the best solution up to that point. I know they are not the
optimal solution because I can quickly disprove that by switching a
few of the variables. I've looked around for commands to give
variables initial values, but all of them seem to be giving me errors
(I figure they might be for older versions of AMPL). What command
should I be using?

Thanks again for the help. It's coming along.

Tomas

[Robert Fourer]

The commands for setting initial values of variables haven't substantially
changed; in particular any of the possibilities described in the AMPL book
ought to work. Basically there are three possibilities. You can specify an
expression for the initial values in the statement that defines the
variables:

var Buy {j in FOOD} >= f_min[j], <= f_max[j],
:= (f_min[j] + f_max[j]) / 2;

(Be sure to use ":=", as "=" will permanently define the variable to equal
the expression.) You can also make any number of assignments of initial
values using "let" statements:

let {j in FOOD} Buy[j] := (f_min[j] + f_max[j]) / 2;
let Buy['FISH'] := 3;

You can also assign initial values as data just as you do for parameters:

var Buy := BEEF 1 CHK 2 FISH 3 HAM 3 MCH 5 MTL 4 SPG 4 TUR 1 ;

Any of the formats that work for parameters will also work for variables.
If you assign values to variables in more than one way, the last values
assigned before the "solve;" are the ones that the solver receives.