[Top][All Lists]

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

Re: [Help-glpk] finding integer solutions gives seemingly infinite loop

From: Michael Hennebry
Subject: Re: [Help-glpk] finding integer solutions gives seemingly infinite loop
Date: Wed, 4 Apr 2012 16:16:37 -0500 (CDT)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

On Wed, 4 Apr 2012, John Perry wrote:

Michael Hennebry wrote on Wednesday, April 04, 2012,
On Tue, 3 Apr 2012, John Perry wrote:
From a previous conversation, I understand that setting upper bounds for
integer solutions helps the mip preprocessor find feasible solutions
for minimization problems that have no maximum. I can make this work
with the systems I'm solving right now, but I'm not sure how to set a
good upper bound in general.

Is there a good rule of thumb for this?

Is the corresponding max problem really unbounded?

Now that you make me think of it, it's unbounded above only in theory; the
largest I could have is machine word size. (I don't mean GLPK; this has to do
with the result, which is then fed into a non-LP algorithm.)

If set of feasible directions is unbounded and full-dimensional,
there is a way to quickly find a feasible solution.
Artificially strengthen all the constraints.
Solve the new problem linearly.
Round the result.

Calculating how much to strengthen each constraint
is left as an exercise for the reader.

Another possiblilty is to use optimality directly.
Original problem:
min cx
s.t. Ax >= b
     x integer

Select all integer d such that cd< 0
At optimum, not (Ax+Ad>=b).

max cx
s.t. Ax >= b
     A[j]x< b[j]-A[j]d  for some j in row_indices(A)
This results in several LPs.

A[j] is the jth row of A.
If A[j] is all-integer, b[j] should be integer and
A[j]x< b[j]-A[j]d may be strengthened to A[j]x<=b[j]-A[j]d-1 .
Otherwise it may be relaxed to A[j]x<=b[j]-A[j]d .
If A[j]d>=0, A[j]x< b[j]-A[j]d is false.

Selection of d is left as an exercise for the reader.

Whether either of these techniques will give you a useful bound,
I do not know.
The second one might be especially slow.

Michael   address@hidden
"On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword."  --  Lily

reply via email to

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