MINOS feasibility_tolerance parameter and an "infeasible problem"

[anten...@gmail.com]

I have a set of problems I'm trying to solve with MINOS, and for some of these, I get the "infeasible problem (or bad starting guess)" message.  In all of these problems, a solution exists, and if I use a different feasibility_tolerance value, a solution is found.  Unfortunately, there is not one feasibility_tolerance value that works across all my problems, which I can understand, but what confuses me is that I can relax this parameter too much. For example if feasibility_tolerance=0.001 fails, I may find that using 0.01 finds a solution, but then using 0.1 does not (using the same data and model).  See attached files to test.

Below is what the documentation says about this parameter.  To me it reads as if a larger value should work when smaller values work, but maybe I'm misunderstanding:

A variable or linear constraint is considered to be feasible if it does not lie outside its bounds by more than r. If MINOS determines that the sum of all infeasibilities cannot be reduced to zero, it reports ‘‘no feasible solution’’ and returns the last solution that it found. The sum of infeasibilities in the reported solution is not necessarily the minimum possible; however, if all the infeasibilities are quite small, it may be appropriate to raise r by a factor of 10 or 100.

Ideally, I would like to skip this feasibility test, but I'm not seeing an option to do that, so maybe there isn't one.  I did turn off the AMPL pre-solving via "option presolve 0;", but I think that's unrelated to what MINOS is doing.  I guess I just need a better understanding of why the feasilbility_tolerance values fail (or succeed) for me as they do, and if there's any other suggested changes to my model or parameters so that answer finding is more consistent, I would like to hear those as well. Thanks!

[Robert Fourer]

The feasibility_tolerance allows MINOS to treat slightly infeasible variables or constraints as being feasible. Setting feasibility_tolerance to 0.001 or higher is not recommended and can have unreliable results as you have seen.

The message "infeasible problem (or bad starting guess)" tells you that MINOS's iterations converged to an infeasible point, most likely a local minimum of the sum-of-infeasibilities function. This will occur when there is no feasible solution at all, but it can also occur when a feasible solution exists but the initial values of the variables are not well chosen. In your example I don't see any initial values assigned to the variables, which would mean that AMPL sends MINOS default initial values of 0 for all variables; this could be a poor choice since variables bin_counts and num_chosen_preds are bounded away from zero by the constraints.

If you make the bounds explicitly available to MINOS by replacing

var bin_counts{bin_ids};
var num_chosen_preds;
...
s.t. c2{bid in bin_ids}: bin_counts[bid] >= target_bounds[bid, 'lower'];
s.t. c3{bid in bin_ids}: bin_counts[bid] <= target_bounds[bid, 'upper'];
...
s.t. c5: num_chosen_preds >= 1;

by

var bin_counts {bid in bin_ids} >= target_bounds[bid,'lower'], <= target_bounds[bid,'upper'];
var num_chosen_preds >= 1;

then in my tests MINOS solves the problem successfully even with all minos_options settings left at their default values. Changing "option presolve 0" to "option presolve 1" has the same effect as it automatically eliminates the above constraints and folds them into the bounds.

Bob Fourer
am...@googlegroups.com

=======

[Michael Saunders]

Dolan,

If all the constraints are linear, the feasibility_tolerance means what it says.

If some constraints are nonlinear, MINOS solves a sequence of subproblems

that have linear constraints (which include all real linear constraints plus linearizations

of the nonlinear constraints).  feasibility_tol applies to the linear constraints plus the

linearized nonlinear constraints.  As Robert says, if the variables are not initialized to

reasonable values, there could be unnecessary trouble because the early linearizations

may not have a feasible solution.

Your model has some large numbers in it.

Scale_option=2 can sometimes help (this scales all linear and nonlinear constraints),

but again it depends on having reasonable initial values.

Michael

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+unsubscribe@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[anten...@gmail.com]

Thank you for the reply.  I implemented your suggested change, but I'm still running into cases where the solver hits this infeasible point. I can usually get MINOS to find the answer by tweaking the MINOS parameters (minor_iterations, feasibility_tolerance, etc.), but there is no perfect set of MINOS parameters for all my test cases.

I am starting to wonder if MINOS is just not the right solver for my task.  For one, the majority of my variables are binary, and MINOS relaxes them to floats.  Additionally, I would like to have the option of a more exhaustive search (i.e., not giving up immediately because it hit some local minimum).  I did try a few of the other non-linear solvers (Baron, Snopt, etc.), though stuck with MINOS because of the much faster runtimes. However, I may try these again, or at least optionally failover to one of them when MINOS fails.

Do you have any recommended solvers that may better suit by task (or other suggestions to get MINOS to work more consistently)?

[Robert Fourer]

The capabilities of some popular nonlinear solvers are as follows:

Local optimality, continuous variables only
CONOPT, Ipopt, LOQO, MINOS, SNOPT

Local optimality, continuous and integer variables
Bonmin, Knitro

Global optimality, continuous variables only
LGO

Global optimality, continuous and integer variables
BARON, Couenne

For a particular class of problems, some solvers will be more effective than others. It is very hard to predict which solver will work best, however, so usually the only way to choose a solver is to run some benchmarks on your test cases. It is generally true, however, problems with integer variables are harder than problems with continuous variables, and establishing a global optimum is harder than finding a local optimum.

Setting solver options to improve performance is also highly problem-dependent, so for help with that it is best to post an example of model & data on which a failure is occurring.