MILP solver that can stop when "good enough" solution is found

[Greg K]

Hi all,

I have an MILP of an enormous size. And it looks like I will need a
life-time for any solver to find an optimal solution. The good thing
is that I don’t really need an optimal solution, good enough solution
will be sufficient for me.
So I am looking for an MILP solver that would have an option to stop
and display current solution if objective value is >= x.

Any suggestions?

Greg

[wanba...@163.com]

You can add a constraint "objective function>=x" and replace the
objective function with an arbitrary function.

[Robert Fourer]

If you follow this advice to substitute an arbitrary objective and add the
constraint

<obj func> >= x

where <obj func> is your expression for the objective, then you should tell
your solver to stop after the first integral solution has been found; for
example in CPLEX you would specify "option cplex_options 'solutionlim=1';".
Or else specify no objective at all (or an objective of 0) and the solver
should stop as soon as it finds an integer-feasible solution.

However this approach converts the optimization problem into a feasibility
problem, which is in general harder for the branch-and-bound procedure that
is used to solve integer programs. So you might want to try instead
defining a variable Z >= 0 and specifying the problem as

Minimize Z
Subj to <obj func> >= x - Z

Then a minimum will be recognized as soon as the solver finds an objective
value >= x, but the solver can work its way there from solutions that have
objective values < x and that thus require positive values of Z.

The performance of these approaches will be highly problem-dependent and
you'll have to try them on your particular problem to see how they work out.

Bob Fourer
4...@ampl.com

[Xing Li]

Dear Prof. Fourer,

 

Many thanks to your reply of email. This is very helpful for my MIP model as well.

 

Regards!

 

Xing

--
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.

--

Xing Li

B.S.E expected 2012 Industrial and Operations Engineering

University of Michigan - Ann Arbor

B.S.E expected 2012 Electrical and Computer Engineering

Shanghai Jiao Tong University - Shanghai

xin...@umich.edu |  734.531.8872 | http://ioe.engin.umich.edu/