RE: [Help-glpk] restarting GLPK with dual simplex

[Meketon, Marc]

I appreciate your quick reply.  I think it works now, but would like to
make sure.

The initial LP takes about 40 minutes to solve, so trying out different
ideas is a bit slow.

I now explicitly turn off the presolver before the second call to the
simplex.  My pseudo code looks like:

   glpk_set_int_parm lp, GLPK_K_PRESOL, 1      ' turn on presolve
   retVal = glpk_simplex(lp)                   ' runs primal simplex
   glpk_set_col_bnds lp, 1, GLPK_LO, 4.0, 0.0  ' change a lower bound
   
   glpk_set_int_parm lp, GLPK_K_DUAL,1         ' set to dual
   glpk_set_int_parm lp, GLPK_K_PRESOL, 0      ' turn off presolve
   retVal = glpk_simplex(lp)                   ' restart


When I run this I get the output below.  The first call to the (primal)
simplex found an optimal solution at iteration 80153.  The second call,
after moving some lower bounds from 0 to some positive integer, found a
solution 7000 iterations later.  I guess that I expected the
infeasibility to be reported as the dual infeasibility, but my current
guess is that the reported infeasibility is always primal infeasibility
even when running the dual simplex algorithm.  Is that correct?

lpx_simplex: original LP has 90620 rows, 100218 columns, 228296
non-zeros
lpx_simplex: presolved LP has 80847 rows, 90416 columns, 206425
non-zeros
lpx_adv_basis: size of triangular part = 79956
      0:   objval = -4.215632000e+006   infeas =  1.000000000e+000 (882)
    200:   objval = -4.187296000e+006   infeas =  8.009070164e-001 (882)
    400:   objval = -4.157580000e+006   infeas =  6.348391586e-001 (882)
    600:   objval = -4.113328000e+006   infeas =  5.348092624e-001 (882)

...


* 79400:   objval = -1.365902869e+006   infeas =  1.378418171e-013 (573)
* 79600:   objval = -1.365941998e+006   infeas =  1.283289810e-013 (573)
* 79800:   objval = -1.365971959e+006   infeas =  1.846124645e-013 (573)
* 80000:   objval = -1.366007208e+006   infeas =  2.784508353e-013 (573)
* 80153:   objval = -1.366019568e+006   infeas =  2.209002718e-013 (573)
OPTIMAL SOLUTION FOUND
| 80153:   objval = -1.366019568e+006   infeas =  1.257028878e+002
(1393)
| 80200:   objval = -1.366013885e+006   infeas =  2.355887767e+005
(1393)
| 80400:   objval = -1.365940191e+006   infeas =  6.716265908e+005
(1393)
| 80600:   objval = -1.365871727e+006   infeas =  9.822039799e+005
(1393)

...

| 87200:   objval = -1.321948868e+006   infeas =  1.240393208e+004
(1390)
| 87400:   objval = -1.321933838e+006   infeas =  1.267813545e+005
(1390)
| 87600:   objval = -1.321367598e+006   infeas =  1.564607280e+005
(1390)
| 87800:   objval = -1.320261620e+006   infeas =  1.940146887e+004
(1388)
| 88000:   objval = -1.318992167e+006   infeas =  3.435233401e+002
(1388)
| 88038:   objval = -1.318992080e+006   infeas =  1.320801363e-010
(1388)
OPTIMAL SOLUTION FOUND


-----Original Message-----
From: Andrew Makhorin [mailto:address@hidden 
Sent: Sunday, April 02, 2006 13:14
To: Meketon, Marc
Cc: address@hidden
Subject: Re: [Help-glpk] restarting GLPK with dual simplex

> Is there any interaction between presolve and restarting with the
dual?
> I set the presolve "on" before the first call to the simplex method.

The presolver must be disabled before re-optimization. If it is
enabled, the current basis is ignored that makes re-optimizaton
impossible.

---------------------------------------------------------------------------- 
This e-mail and any attachments may be confidential or legally privileged.  If 
you received this message in error or are not the intended recipient, you 
should destroy the e-mail message and any attachments or copies, and you are 
prohibited from retaining, distributing, disclosing or using any information 
contained herein.  Please inform us of the erroneous delivery by return e-mail. 

Thank you for your cooperation.
----------------------------------------------------------------------------