[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Problem infeasible is feasible for glpsol
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Problem infeasible is feasible for glpsol |
Date: |
Mon, 25 Apr 2005 18:51:24 +0400 |
> Find below a very simple problem (outpb.lp) which is infeasible by
> construction (row r_1 defines x_1 >=0 whereas r_6 x_1<=-1e-006).
> Although there is no feasible solution for x_1 glpsol gives the
> following output:
>
> $ glpsol --cpxlp outpb.lp -o sol
> lpx_read_cpxlp: reading problem data from `outpb.lp'...
> lpx_read_cpxlp: 8 rows, 2 columns, 8 non-zeros
> lpx_read_cpxlp: 20 lines were read
> lpx_simplex: original LP has 8 rows, 2 columns, 8 non-zeros
> Objective value = 0
> OPTIMAL SOLUTION FOUND BY LP PRESOLVER
> Time used: 0.0 secs
> Memory used: 0.1M (66340 bytes)
This is because your instance has a very small feasible region and
lp presolver is more tolerant to infeasibility than lp solver.
Solving your instance with --nopresol option gives:
========================================================================
lpx_read_cpxlp: reading problem data from `foo.mod'...
lpx_read_cpxlp: 8 rows, 2 columns, 8 non-zeros
lpx_read_cpxlp: 20 lines were read
lpx_adv_basis: size of triangular part = 8
0: objval = 0.000000000e+00 infeas = 1.000000000e+00 (0)
1: objval = 0.000000000e+00 infeas = 1.000000000e-07 (0)
PROBLEM HAS NO FEASIBLE SOLUTION
Time used: 0.0 secs
Memory used: 0.1M (53136 bytes)
========================================================================
However, if you look at the output, you will see that all optimality
conditions are "almost" satisfied:
========================================================================
Problem:
Rows: 8
Columns: 2
Non-zeros: 8
Status: INFEASIBLE (FINAL)
Objective: obj = 0 (MINimum)
No. Row name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 r_1 B 1e-06 0
2 r_2 B -1e-07 1
3 r_3 B -0.633976 1
4 r_4 B 0.633976 1
5 r_5 B 1e-07 1
6 r_6 NU -1e-06 -1e-06 < eps
7 r_7 B 0.633976 1
8 r_8 B -0.633976 1
No. Column name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 x_1 B -1e-06 -10 10
2 x_2 NL -10 -10 10 < eps
Karush-Kuhn-Tucker optimality conditions:
KKT.PE: max.abs.err. = 1.94e-16 on row 3
max.rel.err. = 1.77e-17 on row 3
High quality
KKT.PB: max.abs.err. = 1.00e-06 on row 1
max.rel.err. = 1.00e-06 on row 1
Medium quality
KKT.DE: max.abs.err. = 0.00e+00 on column 0
max.rel.err. = 0.00e+00 on column 0
High quality
KKT.DB: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
High quality
End of output
========================================================================
If you agree (the lp presolver does while the lp solver does not) that
KKT.PB is satisfied, the solution is feasible; if not, your instance
has no feasible solution.
Andrew Makhorin