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:=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*: [email protected] <[email protected]
>> <mailto:%[email protected]%22%20%[email protected]%3e>>
>> *From*: "Du, Jeanette" <[email protected]
>> <mailto:%22Du,%20Jeanette%22%20%[email protected]%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