How hard would be to add "Indicator Constraints"

[Domingo Alvarez Duarte]

Hello !

While testing GLPK with miplib2017 I noticed that several problems can 
not be handled by GLPK due to having "Indicator Constraints" in the mps 
file.


Looking here 
https://www.gams.com/latest/docs/UG_LanguageFeatures.html#UG_LanguageFeatures_IndicatorConstraints 
for a explanation of it I'm asking if someone else have extended GLPK to 
manage then ? Or if not how hard could be to do it ?


Cheers !

Re: How hard would be to add "Indicator Constraints"

[Erwin Kalvelagen]

Indicator constraints can be transformed into a normal constraint using
SOS1 (Special Ordered Set of type 1) variables. If the solver (like GLPK)
does not have SOS1 variables you can simulate this with binary variables,
but this needs some additional assumptions (some bounds for the big-M
constraints). So I think it is difficult to add direct and general support
for indicator constraints to GLPK.


Erwin Kalvelagen
Amsterdam Optimization Modeling Group
er...@amsterdamoptimization.com
https://www.amsterdamoptimization.com 



On Mon, Oct 5, 2020 at 6:02 AM Domingo Alvarez Duarte 
wrote:

> Hello !
>
> While testing GLPK with miplib2017 I noticed that several problems can
> not be handled by GLPK due to having "Indicator Constraints" in the mps
> file.
>
> Looking here
>
> https://www.gams.com/latest/docs/UG_LanguageFeatures.html#UG_LanguageFeatures_IndicatorConstraints
> for a explanation of it I'm asking if someone else have extended GLPK to
> manage then ? Or if not how hard could be to do it ?
>
> Cheers !
>
>
>

Re: How hard would be to add "Indicator Constraints"

[Chris Matrakidis]

Should be fairly easy to do when branching, to me the hard part seems to be
extending the api for this in a clean way.

Best Regards,

Chris Matrakidis

On Mon, 5 Oct 2020 at 16:16, Erwin Kalvelagen <
er...@amsterdamoptimization.com> wrote:

>
> Indicator constraints can be transformed into a normal constraint using
> SOS1 (Special Ordered Set of type 1) variables. If the solver (like GLPK)
> does not have SOS1 variables you can simulate this with binary variables,
> but this needs some additional assumptions (some bounds for the big-M
> constraints). So I think it is difficult to add direct and general support
> for indicator constraints to GLPK.
>
> 
> Erwin Kalvelagen
> Amsterdam Optimization Modeling Group
> er...@amsterdamoptimization.com
> https://www.amsterdamoptimization.com 
> 
>
>
> On Mon, Oct 5, 2020 at 6:02 AM Domingo Alvarez Duarte 
> wrote:
>
>> Hello !
>>
>> While testing GLPK with miplib2017 I noticed that several problems can
>> not be handled by GLPK due to having "Indicator Constraints" in the mps
>> file.
>>
>> Looking here
>>
>> https://www.gams.com/latest/docs/UG_LanguageFeatures.html#UG_LanguageFeatures_IndicatorConstraints
>> for a explanation of it I'm asking if someone else have extended GLPK to
>> manage then ? Or if not how hard could be to do it ?
>>
>> Cheers !
>>
>>
>>

Updated script for miplib2017

[Chris Matrakidis]

Domingo mentioned looking at miplib2017 problems, which reminded me of
this: I noticed some time ago that the current script offered with
miplib2017 suffers from accuracy loss when checking the results, because it
was parsing the solution file in printable form, which rounds values a bit.
An example miplib result file is in
http://plato.asu.edu/ftp/milp_res1/benchmark.glpk.1threads.7200s.res where
in the last column many solutions are reported as  "fail" or "error".

I made an updated version that also uses a solution file in printable form,
that offers more digits of accuracy (attached) and seems to work a lot
better with a subset of miplib problems I used for testing.

Best Regards,

Chris Matrakidis


run_glpk.sh
Description: application/shellscript