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