[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 *\
Maximize
obj: + x2
Subject To
c1: - 3 x2 + 3 x1 >= 1
c2: - 4 x2 + 4 x1 <= 3
Bounds
0 <= x2 <= 100
1 <= x1 <= 100
Generals
x2
x1
End
18 lines were written
GLPK Integer Optimizer, v4.43
2 rows, 2 columns, 4 non-zeros
2 integer variables, none of which are binary
Preprocessing...
PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION
Time used: 0.0 secs
Memory used: 0.0 Mb (29461 bytes)

[Prev in Thread] |
**Current Thread** |
[Next in Thread] |

**[Bug-glpk] Re: [Help-glpk] Skip preprocessing**,
*Andrew Makhorin* **<=**