[Top][All Lists]

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

[Bug-glpk] Re: [Help-glpk] Skip preprocessing

From: Andrew Makhorin
Subject: [Bug-glpk] Re: [Help-glpk] Skip preprocessing
Date: Thu, 16 Dec 2010 15:16:23 +0300

> I am trying to get glpsol to start to try to solve this problem (from
> "Logic and Integer Programming" by H.P.Williams):
> var x1, >= 1, integer;
> var x2, integer;
> maximize obj: x2;
> s.t. c1:
>      3*x1 - 3*x2 >= 1;
> s.t. c2:
>      4*x1 - 4*x2 <= 3;
> but it is stuck in preprocessing. Can I skip preprocessing in some
> way? I have tried the --nopresol and --noscale flags to no avail. It
> works fine with the --nomip flag, so it has probably something to do
> with MIP preprocessing.

The mip preprocessor can be disabled with --nointopt option.

Please note that the mip preprocessor falls into an infinite loop due to
a bug. Your instance has a property that lp relaxation to it has no
finite maximum while the integer feasible region is empty (in fact,
1/3 <= x1 - x2 <= 3/4, so no integers x1 and x2 can satisfy this
constraint). The preprocessor attempts to increase implied lower bounds
of x1 and x2 by rounding, however, this never terminates, because x1 and
x2 have no upper bounds.

If you specify some upper bounds for x1 and x2, say, 100, the
preprocessor successfully detects that yor instance has no integer
feasible solution:

GLPSOL: GLPK LP/MIP Solver, v4.45
Parameter(s) specified in the command line:
 --lp prob.txt --wlp /dev/stdout
Reading problem data from `prob.txt'...
2 rows, 2 columns, 4 non-zeros
2 integer variables, none of which are binary
13 lines were read
Writing problem data to `/dev/stdout'...
\* Problem: Unknown *\

 obj: + x2

Subject To
 c1: - 3 x2 + 3 x1 >= 1
 c2: - 4 x2 + 4 x1 <= 3

 0 <= x2 <= 100
 1 <= x1 <= 100


18 lines were written
GLPK Integer Optimizer, v4.43
2 rows, 2 columns, 4 non-zeros
2 integer variables, none of which are binary
Time used:   0.0 secs
Memory used: 0.0 Mb (29461 bytes)

reply via email to

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