Re: How to identify which variables and constraints produce infeasible problem in AMPL-presolve?
Paul
Paul
Robert Fourer
On further investigation it appears there is no easy way to capture the inconsistent lower and upper bounds discovered by presolve -- either though bound suffixes or presolve_logfile. The main purpose of presolve is to reduce the size of the problem sent to the solver, and it's only incidental that it sometimes finds that no feasible solution is possible. The messages returned by presolve provide only limited information about the underlying cause of the infeasibility.
When presolve determines that no feasible solution is possible, it sets the built-in variables solve_result to 'infeasible' and solve_result_num to 299. A second "solve;" will cause the problem to be sent to the solver even if presolve finds no feasible solution, so it is possible to write
solve;
if solve_result_num = 299 then solve;
to force the problem to be sent to the solver. Some solvers can then provide addition information about causes of infeasibility (see the "iis" options of CPLEX and Gurobi) but even that requires some effort to interpret.
In my experience if you have a model and is going to be sometimes feasible and sometimes infeasible, depending on the data, then a better approach for automated infeasibility diagnosis is to make some of the constraints into "soft constraints" that can be violated with some penalty. This creates a new model that is always feasible; and you can check for feasibility of the original model by checking whether any of the soft constraints show positive violations. If you find any positive violations then you can report them as an indication of the constraints that are too tight.
For example, if you have a constraint on production hours available,
subject to Time {s in STAGE}:
sum {p in PROD} 1/rate[p,s] * Make[p] <= avail[s];
you can define a variable to represent time in excess of the amount available,
var ExcessTime {STAGE} >= 0;
and replace Time by this soft constraint:
subject to Time {s in STAGE}:
sum {p in PROD} 1/rate[p,s] * Make[p] <= avail[s] + ExcessTime[s];
Also you must give the ExcessTime[s] variables large cost coefficients in the objective function -- large enough to make excess time unattractive when there is a feasible solution, though not so extremely large (like 1000000000) as to cause numerical problems. After solving, you check the values of ExcessTime[s] and any are significantly positive, you report them as indicating an infeasibility. Generally you should only "soften" constraints that it makes some sense to violate; for example requirements and limits make good soft constraints, but material balances do not.
Bob Fourer
From: am...@googlegroups.com [mailto:am...@googlegroups.com]
On Behalf Of Miguel
Sent: Tuesday, July 10, 2012 10:52 AM
To: am...@googlegroups.com
Subject: [AMPL 5988] How to identify which variables and constraints produce infeasible problem in AMPL-presolve?
Hello,
I ask whether it is possible to know which variables and constraints have caused the error, besides to read the messages that presolve provides.
For example, if presolve writes the following messages:
presolve, variable corriente['PUND0272']:
impossible deduced bounds: lower = 12.2609, upper = 0
presolve: constraint RU[45] cannot hold:
body >= -1110.32 cannot be <= -1134.26; difference = 23.9349
But if we check their suffixes we don't discover any clue:
corriente['PUND0272'].status = none
corriente['PUND0272'].astatus = in
corriente['PUND0272'].lb = 12.2609
corriente['PUND0272'].ub = 16.2609
RU[45].status = none
RU[45].astatus = in
RU[45].body = 1110.32
RU[45].ub = 0
RU[45].lb = 0
This functionality is needed in order to provide an automatic mechanism to show more data about them in a programe
Thanks in advance
.