help-glpk
[Top][All Lists]
Advanced

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

Re: [Help-glpk] size of auxiliary variable


From: Michael Hennebry
Subject: Re: [Help-glpk] size of auxiliary variable
Date: Mon, 4 Jan 2010 11:25:08 -0600 (CST)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

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

reply via email to

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