Re: [Fwd: Question for infeasible LP problem]

[Mate Hegyhati]

Hi!

Maybe I'm wrong, but I don't think that such an indicator is 
programmable.  Consider this small example with 3 non-negative variables:

x + y <= 1
x + z <= 1
y + z <= 1
x + y + z >= 2

Remove any of the constraints, and it becomes feasible. You wouldn't be 
able to tell, which one is wrong if I don't provide any semantics. And 
from the solvers point of view, the model you provide has no semantics, 
just "arbitrary" cutting planes.

Nevertheless, I know the feeling of having an infeasible implementation 
of a model with many constraints, and scratching my head. In the 
following I describe what I usually do in this situation. Hopefully, 
someone will be outraged with the ugliness of it, and provide a much 
simpler approach :-)

Most often I have an idea, where the bug might be, so if I have 2-3 
suspicious constraints where I probably mistyped something, I usually 
comment them out one-by-one, and if the model becomes feasible only in 
one case, I triple-check that constraint character by character.

If that is not the case, or doesn't help, nor does a general 
double-check, rubber-duck method, etc.,  I try the following:

1) I find the smallest dataset I can where the model is 
infeasible/results in a suboptimal solution.
2) Hopefully, either a feasible solution is already known for that 
dataset, or easy to find. (not necessarily optimal, just feasible is enough)
3) I enforce the variables (if necessary all of them, maybe just a few 
key ones, in my case typically binaries) to have these values, and then 
either comment the constraints out one-by-one to test, or add an "error" 
variable to all the right hand sides, and minimize that.

A simple way to do this is to change the variable to param and have a 
separate data file with the values of the variables in the feasible 
solution. (You can use more data files at the same time.)

The disadvantage of this is that you have to change it back to var after 
you are done. If you need to repeat this step couple of times, another 
option could be something like this:

param bigM = 1024;
param NOTFIXED=-1; # or something irrelevant

param foo_value{SET}, default NOTFIXED;
var foo{element in SET} # >=0, integer, etc
 <= (if foo_value[element]==NOTFIXED then bigM else foo_value[element]),
 >= (if foo_value[element]==NOTFIXED then -bigM else foo_value[element])
 ;

then, if you don't provide the data file with a solution, you get the 
"original" model. If you do, you get these variables fixed.

Of course this can be tedious if you have a lot of different variables.

The error part is simpler:

param max_error default 0;
var error >=0, <= max_error;

s.t. suspicious_constraint{...}:
  LHS <= RHS + error;


minimize objective:
  # original objective
  + bigM * error
  ;

Again, if you provide param max_error:=9999; in a data file, error would 
be allowed but minimized. otherwise it is removed by the preprocessor.


I strongly hope, that someone has a much more elegant way of doing this.

All the best!

Mate



On 1/5/21 12:52 AM, Andrew Makhorin wrote:
> -------- Forwarded Message --------
>
> *Date*: Mon, 4 Jan 2021 23:23:17 +0000
> *Subject*: Question for infeasible LP problem
> *To*: help-glpk@gnu.org <help-glpk@gnu.org 
> <mailto:%22help-glpk@gnu.org%22%20%3chelp-glpk@gnu.org%3e>>
> *From*: "Du, Jeanette" <jeanette_du@freddiemac.com 
> <mailto:%22Du,%20Jeanette%22%20%3cjeanette_du@freddiemac.com%3e>>
> > Hello,
> >
> > I am relatively new to GLPK LP solver. Is there a way to find out the 
> > constraint(s) that cause infeasibility of a problem in the .out file?
> >
> > Thanks,
> >
> > Jeanette(Yuqian) Du
> >
> > Investments and Capital Markets
> >
> > Freddie Macv
> >
> > The information transmitted in this e-mail is for the exclusive use of 
> > the person or entity to which it is addressed and may contain legally 
> > privileged or confidential information. If you are not the intended 
> > recipient of this e-mail, you are prohibited from reading, printing, 
> > duplicating, disseminating or otherwise using or acting in reliance 
> > upon this information. If you have received this information in error, 
> > please notify the sender at Freddie Mac immediately, delete this 
> > information from your computer and destroy all copies of the information.