Is there a good way to stop searching if the objective is close enough to a known solution?

I am minimizing a sum of squares thing, so (1) I know that zero is the optimum value for the objective, and (2) I would be happy if this sum-of-squares got below 0.01.

I am using NEOS and AMPL with Bonmin. I would be open to other solvers, but I like to play in the open source world if possible.

asked 11 Jan '12, 17:06

forkandwait's gravatar image

forkandwait
46111026
accept rate: 100%


Taken from the AMPL Modeling Language Google Group:

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

A [by @4er]: 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.

link

answered 11 Jan '12, 17:33

fbahr's gravatar image

fbahr ♦
4.6k716
accept rate: 13%

edited 11 Jan '12, 17:37

That solution seems to work to enable an exit after the objective function hits a good-enough level.

However, my model seems to be fundamentally flawed in some other way (on NEOS it just won't stop running even with a very high tolerance for the ....)

Oh -- I think it's funny that the AMPL FAQ is the only FAQ that I have ever found remotely useful. I should have checked it first -- Google didn't really help (either OR is too esoteric or not esoteric enough for easy searches).

(11 Jan '12, 19:15) forkandwait

I don't know about AMPL, but many modeling environments allow you to define search tolerances. For example in GAMS, you could define absolute and relative MIP gaps via model atributes, namely Optca and Optcr. In LINGO, you could alter these settings via the options window. In addition, solvers such as CPLEX, Gurobi, and BARON allows for defining tolerances. I think you should focus your search on the terms "tolerance" and "gap".

ps. NEOS accepts BARON in GAMS format which could solve MINLPs. The relevant BARON options are EpsA and EpsR.

link

answered 12 Jan '12, 02:21

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×11

Asked: 11 Jan '12, 17:06

Seen: 1,119 times

Last updated: 12 Jan '12, 02:21

OR-Exchange! Your site for questions, answers, and announcements about operations research.