[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Fwd: Question for infeasible LP problem]

From: Mate Hegyhati
Subject: Re: [Fwd: Question for infeasible LP problem]
Date: Tue, 5 Jan 2021 02:44:59 +0100
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0


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!


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*: < <>> *From*: "Du, Jeanette" < <mailto:%22Du,>>


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?


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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]