Re: [Help-glpk] We live in a world of hidden inequalities

[Andrew Makhorin]

> Don't worry, I think this has nothing to do with global economics or
> worldwide peace.
> 
> I have a model which, when run, glpk advises me that it has discovered
> 162 hidden inequalities. I assume in the model and not the world,
> because 162 would seem small for the world. Also the numbr varies with
> the data I supply to the model and its difficult to see how that would
> affect the world.
> 
> What are they? Both in a general sense, what are hidden inequalities?
> and in the particular case of my model, how do I investigate them?
> 
> Are they a good or a bad thing? The model works quickly and produces
> correct answers. Should every model have some? How have I induced them?
> 
> LPs for a long time have had only two objectives, min and max, and they
> are really the same. Perhaps it is time for a new objective to find the
> data with the minimum hidden inequalities, which is presumably the
> fairest solution.
> 

Cover inequality is an inequality in the form

   x1 + x2 + ... + xn >= 1

where x1, x2, ..., xn are binary variables. It means that at least one
xj should be 1 in any integer feasible solution. Hidden cover inequality
is an inequality which doesn't have the form above, but is equivalent to
some cover inequality. For example,

   2x1 + 3x2 + 2x3 >= 2

is hidden cover inequality, because it is equivalent to and therefore
can be replaced by the following cover inequality:

   x1 + x2 + x3 >= 1

Such replacements are used internally by the mip preprocessor, and you
may just ignore all messages concerning details of the preprocessing.