[Clp] Problem infeasible after fast dual although only bound changed?

[Sebastian Theophil]

Hi John,

 

 

further testing seems to show my idea is correct.

 

Instead of updating the lower bound only I should update the bound & the
column solution accordingly (possibly making the solution primal
infeasible). 

 

This means I should calculate the new solution as B^{-1} b, i.e., as the
product of the basis matrix inverse and the new RHS. 

I know that getBInvCol returns a column of B^{-1} and its row elements
are in order of the basis variables returned by getBasics(int*).

Is the order of the columns of getBInvCol somehow changed? 

 

If my new right hand side is

b' = b - (1, 0, 0 , ..., 0 ), 

 

i.e., I reduce the first entry by 1, I don't have to calculate the
multiplication B^{-1} b but instead, my new column solution is

 

x' = x - B^{-1}_1 

 

i.e., the old solution minus the first column of the basis inverse. I am
not sure about the sign though. In practice, it seems that adding
getBInvCol(R) to the solution works. Is this because I'm manipulating
the lower bound? 

 

What I do now is the following:

 

            solver.enableSimplexInterface(true);

 

            solver.getBasics(&vecnBasics[0]);

            solver.startFastDual(2);

 

            for(int nRow=0; nRow<solver.getNumRows(); ++nRow) {

 
if(abs(solver.getRowPrice()[nRow])>gvEPSILON_CONSTRAINT) {

                        solver.setRowLower( nRow,
solver.getRowLower()[nRow]-1.0 );

                        

                        solver.getBInvCol(nRow, &vecfBInvCol[0]);

                        _vector<double>::const_iterator
itfBInvCol=vecfBInvCol.begin();

                        for(_vector<int>::const_iterator
itnBasic=vecnBasics.begin(); itnBasic!=vecnBasics.end(); ++itnBasic,
++itfBInvCol) {

 
solver.getModelPtr()->solutionRegion()[*itnBasic] += *itfBInvCol;

                        }

                        break;

                  }

            }

            solver.resolve();

            

            solver.stopFastDual();

            solver.disableSimplexInterface();

 

I only need the enableSimplexInterface call, because I need to call
getBasics(). If I don't call enableSimplexInterface,
ClpModel::pivotVariable_ is NULL. Is there another solution like setting
some option so the solver keeps pivotVariable_ around? 

 

Thanks a lot,

Sebastian 

 

From: Sebastian Theophil 
Sent: Dienstag, 21. Juli 2009 17:21
To: 'John J Forrest'
Cc: clp at list.coin-or.org
Subject: RE: [Clp] Problem infeasible after fast dual although only
bound changed?

 

John,

 

the problem is solved first and then I reduce the lower bound of a
constraint with dual value > 0.0. 

Thus, the previous dual solution is not optimal anymore because the
complementary slackness property is violated. Both dual value and
associated slack are != 0. 

 

The problem itself is still feasible of course. I have checked now what
fastDual does internally, and although I don't understand why, it
returns "1" to indicate the problem is infeasible which (in my
opininion) it is not. 

 

Maybe fastDual isn't expected to do what I want it to do. Usually, when
the RHS vector b changes, the column solution x_b is updated with x_b =
B^{-1} b. The resulting x_b may be infeasible but the dual solution
stays (dual) feasible. A dual simplex step (or multiple) go back to a
primal and dual feasible solution. 

 

I do not update the column solution though. 

 

Regards

Sebastian


--
Sebastian Theophil . stheophil at think-cell.com
Software Engineer
 
think-cell Software GmbH . Invalidenstr. 34 . 10115 Berlin, Germany 
http://www.think-cell.com . phone +49-30-666473-10 . toll-free (US) +1-800-891-8091
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl . Amtsgericht Berlin-Charlottenburg, HRB 85229

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20090721/e4d91b26/attachment.html>