Re: [Help-glpk] size of auxiliary variable

[Michael Hennebry]

On Sun, 3 Jan 2010, François Dionne wrote:

> I'm thinking of using glpk to solve a series of integer programming
> problems. The most difficult one should have around 2048 structural
> variables, which are integers with lower bounds of zero and upper bounds
> at most 1024 approximately. There are only two constraints, which are
> equalities whose coefficients are nonnegative integers not greater than
> 2048.

This problem might be made more tractable with a transformation.
As it is, the row vectors could be nearly parallel.
If |a1.a2| > 0.5 * a1.a1,
a2 can be reduced by subtracting an integer multiple of a1.
Of course, b2 must be changed by subtracting the same integer multiple of b1.

> The problem that I'm anticipating is this: how big are my auxiliary
> allowed to be? I'm expecting them to be fixed positive constant
> integers, at most around 1024^3 or 2048^3 . They should fit inside the
> mantissa of my machine's double floating point but I'm not sure how many
> guard digits I should allow.

2048**3==2**33.
IIRC double precision normally has at least 48 bits of precision.
I would normally expect 15 to be enough, but perhaps not in this case.
When doing integer programming, I like to be able to test for close enough.
In this case,
given a continous solution in which every variable is within 2**-22,
one can show that rounding would produce an all-integer solution.
It's possible that you can get less stringent
numbers by manipulating your constraints as above.

--
Michael   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."