[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] Re: Simplex method infeasible, IP method feasible
From: |
Nicolo' Giorgetti |
Subject: |
[Help-glpk] Re: Simplex method infeasible, IP method feasible |
Date: |
Fri, 12 Sep 2003 17:35:59 +0200 |
On Fri, 12 Sep 2003 14:41:32 +0400 Andrew Makhorin <address@hidden> wrote:
> From: Nicolo' Giorgetti <address@hidden>
> To: <address@hidden>
> Subject: Re: [Help-glpk] Re: Simplex method infeasible, IP method
> feasible Date: Friday, September 12, 2003 2:20 PM
>
> >I'm doing some errors in defining the problem but I'm not able
> >to see where they are. Do you have any suggestion ?
> >Thank you very much.
>
> CONFER!
Dear Andrew,
Sorry, I have another problem similar to the previous one.
Could you solve it both with the simplex method and the interior point
method ?
--------- problem: output_lpt.lpt -------------------
\* Problem: Unknown *\
Minimize
obj: + x(1)
Subject To
r(1): - x(1) + x(2) + x(3) <= 0
r(2): + x(1) <= 68.855034718
r(3): - 0.222520933956 x(2) + 0.974927912182 x(3) <= 39.4828617494
r(4): - 0.900968867902 x(2) + 0.433883739118 x(3) <= 5.23377925511
r(5): - 0.900968867902 x(2) - 0.433883739118 x(3) <= -73.0421245614
r(6): + 0.623489801859 x(2) - 0.781831482468 x(3) <= 76.0438443135
Bounds
-1000000 <= x(1) <= 1000000
-1000000 <= x(2) <= 1000000
-1000000 <= x(3) <= 1000000
End
-------------------------------------------------------
I solved it using glpsol and I obtained two different outputs:
--------------- Simplex ------------------------
$glpsol --lpt output_lpt.lpt
lpt_read_prob: reading LP data from `output_lpt.lpt'...
lpt_read_prob: 3 variables, 6 constraints
lpt_read_prob: 19 lines were read
lpx_simplex: original LP has 6 rows, 3 columns, 12 non-zeros
lpx_simplex: presolved LP has 5 rows, 3 columns, 11 non-zeros
gm_scal: max / min = 4.494e+000
gm_scal: max / min = 3.016e+000
lpx_adv_basis: size of triangular part = 5
0: objval = -2.000000000e+006 infeas = 1.000000000e+000 (0)
4: objval = 6.885503472e+001 infeas = 2.000844258e-012 (0)
* 4: objval = 6.885503472e+001 infeas = 5.401980374e-006 (0)
* 5: objval = 6.885504317e+001 infeas = 7.015617570e-006 (0)
lpx_simplex: numerical instability (primal simplex, phase II)
5: objval = 6.885504317e+001 infeas = 1.000000000e+000 (0)
5: objval = 6.885504317e+001 infeas = 1.000000000e+000 (0)
PROBLEM HAS NO FEASIBLE SOLUTION
lpx_simplex: cannot recover undefined or non-optimal solution
Time used: 0.0 secs
Memory used: 0.1M (80744 bytes)
------- Interior point method ------------------------
$ glpsol --interior --lpt output_lpt.lpt
lpt_read_prob: reading LP data from `output_lpt.lpt'...
lpt_read_prob: 3 variables, 6 constraints
lpt_read_prob: 19 lines were read
lpx_interior: original LP problem has 6 rows and 3 columns
lpx_interior: transformed LP problem has 9 rows and 12 columns
Factorizing S = A*A' symbolically...
nz(A) = 24
nz(S) = 32 (upper triangular part)
nz(U) = 32
Guessing initial point...
Optimization begins...
0: F = 2.522900440e+005; rpi = 3.0e-001; rdi = 1.1e+000; gap =
2.0e-001
1: F = -4.073474860e+004; rpi = 9.2e-002; rdi = 1.1e-001; gap
= 1.8e-001
2: F = -1.149990823e+003; rpi = 1.1e-002; rdi = 1.3e-002;
gap = 2.4e-002
3: F = -4.535524941e+001; rpi = 1.1e-003; rdi = 1.3e-003; gap =
2.5e-003
4: F = 6.094629906e+001; rpi = 1.2e-004; rdi= 1.3e-004; gap =
3.2e-004
5: F = 7.301168842e+001; rpi = 1.5e-005; rdi = 1.3e-005; gap =
5.8e-005
6: F = 7.071401526e+001; rpi = 2.3e-006; rdi = 1.7e-006; gap =
7.9e-006
7: F = 6.904379861e+001; rpi= 2.3e-007; rdi = 1.7e-007; gap= 8.1e-007
8: F = 6.887392223e+001; rpi = 2.3e-008; rdi= 1.7e-008; gap= 8.1e-008
9: F = 6.885693739e+001; rpi = 2.3e-009; rdi= 1.7e-009; gap= 8.1e-009
OPTIMAL SOLUTION FOUND
Time used: 0.0 secs
Memory used: 0.1M(58588 bytes)
I solved it with the barrier algorithm of CPLEX and I have obtained the
following output:
------------ from CPLEX --------------------
Problem 'output_lpt.lpt' read.
Read time = 0.10 sec.
Tried aggregator 1 time.
LP Presolve eliminated 1 rows and 0 columns.
Reduced LP has 5 rows, 3 columns, and 11 nonzeros.
Presolve time = 0.02 sec.
Number of nonzeros in lower triangle of A*A' = 10
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.00 sec.
Summary statistics for Cholesky factor:
Rows in Factor = 5
Integer space required = 5
Total non-zeros in factor = 15
Total FP ops to factor = 55
Itn Primal Obj Dual Obj Prim Inf Upper Inf Dual Inf
0 -3.9574734e+005 -1.1000138e+007 3.10e+006 2.08e+005 1.00e+001
1 -3.1615429e+005 -1.7627440e+006 7.28e+005 4.89e+004 1.98e+000
2 2.3392532e+003 -9.5588211e+004 3.41e+004 2.29e+003 6.48e-015
3 6.9185003e+001 -1.8265269e+002 5.61e+000 3.77e-001 6.23e-015
4 6.8912782e+001 6.8129432e+001 1.09e+000 7.31e-002 4.27e-015
5 6.8846880e+001 6.8615031e+001 3.32e-002 2.13e-003 1.67e-013
6 6.8854183e+001 6.8835404e+001 1.96e-003 2.26e-015 4.06e-015
7 6.8854957e+001 6.8853283e+001 1.86e-004 2.33e-010 1.96e-015
8 6.8855028e+001 6.8854909e+001 2.43e-005 1.63e-016 1.24e-015
9 6.8855031e+001 6.8855056e+001 1.89e-005 3.09e-015 2.82e-015
10 6.8855035e+001 6.8855067e+001 9.21e-006 3.58e-015 1.90e-015
11 6.8855035e+001 6.8855071e+001 7.90e-006 6.67e-015 1.77e-015
Barrier cannot determine infeasibility.
Barrier time = 0.05 sec.
Primal crossover.
Primal: Fixed no variables.
Dual: Fixing 1 variable.
0 DMoves: Infeasibility 0.00000000e+000 Objective
6.88550432e+001 Dual: Pushed 1, exchanged 0.
Using devex.
Removing shift (1).
Total crossover time = 0.08 sec.
Primal simplex - Infeasible: Infeasibility = 8.4553621207e-006
Solution time = 0.18 sec. Iterations = 0 (0)
Best Regards,
Nicolo'.
- [Help-glpk] Simplex method infeasible, IP method feasible, Nicolo' Giorgetti, 2003/09/09
- [Help-glpk] Re: Simplex method infeasible, IP method feasible, Andrew Makhorin, 2003/09/10
- Re: [Help-glpk] Re: Simplex method infeasible, IP method feasible, Nicolo' Giorgetti, 2003/09/11
- [Help-glpk] Re: Simplex method infeasible, IP method feasible, Andrew Makhorin, 2003/09/11
- Re: [Help-glpk] Re: Simplex method infeasible, IP method feasible, Nicolo' Giorgetti, 2003/09/12
- [Help-glpk] Re: Simplex method infeasible, IP method feasible, Andrew Makhorin, 2003/09/12
- [Help-glpk] Re: Simplex method infeasible, IP method feasible,
Nicolo' Giorgetti <=
- [Help-glpk] Re: Simplex method infeasible, IP method feasible, Andrew Makhorin, 2003/09/12
- Re: [Help-glpk] Re: Simplex method infeasible, IP method feasible, Nicolo' Giorgetti, 2003/09/13
- [Help-glpk] Re: Simplex method infeasible, IP method feasible, Andrew Makhorin, 2003/09/11