[Top][All Lists]

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

Re: [Help-glpk] Problems using MIP

From: Andrew Makhorin
Subject: Re: [Help-glpk] Problems using MIP
Date: Sat, 12 Oct 2002 16:52:38 +0400

>I have the following problem when trying to solve MIP problems with
>glpk: I formulate the problem and, given that MIP solver needs an
>optimal basic solution of LP relaxation,
>first try to solve the problem with lpx_simplex. But then the solver
>finds that the
>problem is unbounded (and maybe the MIP solution is bounded!!!) and
>then it is
>not possible to use the MIP solver because no initial optimal basic
>solution of LP
>relaxation exists.

If lp relaxation of a mip problem is unbounded and there is at least
one integer feasible point, the mip problem is also unbounded (sic!).

You can try to make all variables double-bounded introducing dummy
lower and upper bounds. If then you will look at optimal solution of
lp relaxation (the routine lpx_print_sol allows to write it to a text
file), you will easily notice which additional constraint(s) need to be
introduced into your problem.

Another, easiest way is to limit the objective function. To do that you
need to introduce a row that is a copy of the objective function row and
assign a dummy lower (in case of minimization) or upper (in case of
maximization) bound to the corresponding auxiliary variable.

Unboundness means you missed some significant factors (expressed as
constraints) in your model, because there is no unboundness in the real

reply via email to

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