[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Andrew Makhorin
Subject: Re: [Help-glpk] We live in a world of hidden inequalities
Date: Thu, 05 May 2011 17:25:05 +0400

> 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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]