Re: [Fwd: Question for infeasible LP problem]
Dear Jeanette,
Consider using library functions glp_get_unbnd_ray() and
glp_get_row_stat() to determine *one* of the rows leading to
infeasibility. See file doc/glpk.pdf of the GPLK source.
Best regards
Heinrich
On 1/5/21 2:44 AM, Mate Hegyhati wrote:
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:=; 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 +
*Subject*: Question for infeasible LP problem
*To*: help-glpk@gnu.org mailto:%22help-g...@gnu.org%22%20%3chelp-g...@gnu.org%3e>>
*From*: "Du, Jeanette" mailto:%22Du,%20jeanette%22%20%3cjeanette...@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
Re: [Fwd: Question for infeasible LP problem]
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:=; 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 +
*Subject*: Question for infeasible LP problem
*To*: help-glpk@gnu.org >
*From*: "Du, Jeanette" >
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.
[Fwd: Question for infeasible LP problem]
Forwarded Message Date: Mon, 4 Jan 2021 23:23:17 + Subject: Question for infeasible LP problem To: help-glpk@gnu.org From: "Du, Jeanette" > > > > > > > > > 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. > > >
