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

Tue Jul 21 11:21:02 EDT 2009

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

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

Sebastian,

It seemed to work when I tried something similar, but my problem was
feasible after changes - duals did change with (2) but not with (0). You
say the result is infeasible. The duals are not updated if infeasible.
fastDual was meant to do as little as possible.

John Forrest

 "Sebastian Theophil" ---07/21/2009 10:32:24 AM---Hi John,

From:

"Sebastian Theophil" <stheophil at think-cell.com>

To:

John J Forrest/Watson/IBM at IBMUS

Cc:

<clp at list.coin-or.org>

Date:

07/21/2009 10:32 AM

Subject:

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

________________________________

Hi John,

thanks for your prompt reply. Unfortunately it doesn't work no matter
what parameters I pass. I have also updated to the most recent TRUNK to
make sure I'm not finding old bugs. 
Still, the duals don't get updated and the result is infeasible. 

Regards
Sebastian

From: John J Forrest [mailto:jjforre at us.ibm.com] 
Sent: Dienstag, 21. Juli 2009 16:14
To: Sebastian Theophil
Cc: clp at list.coin-or.org; clp-bounces at list.coin-or.org
Subject: Re: [Clp] Problem infeasible after fast dual although only
bound changed?

Sebastian,

If you want the duals updated then it should be startFastDual(2) - see
OsiClpSolverInterface.hpp;

John Forrest

"Sebastian Theophil" ---07/21/2009 07:33:45 AM---Hi, I have a very
simple primal degenerate LP problem: 

From:

"Sebastian Theophil" <stheophil at think-cell.com>

To:

<clp at list.coin-or.org>

Date:

07/21/2009 07:33 AM

Subject:

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

Sent by:

clp-bounces at list.coin-or.org

________________________________

Hi,

I have a very simple primal degenerate LP problem:

\Problem name: 

Minimize
obj: x2
Subject To
cons0: x0 + x2 >= -0
cons1: - x0 + x2 >= -10
cons2: x1 + x2 >= -0
cons3: - x1 + x2 >= -10
Bounds
x0 Free
x1 Free
x2 Free
End

The primal solution is (5, 5, -5), but there are two dual solutions
(0.5, 0.5, 0, 0) and (0, 0, 0.5, 0.5). 
The code below reads the file, searches a dual positive variable and
changes the RHS of the associated constraint. The constraint can no
longer be binding, and the dual solution should change solution after a
resolve. This works as expected without startFastDual. 

If startFastDual is active, the dual solution doesn't change though
although it is no longer feasible. 

OsiClpSolverInterface solver;
solver.readLp("C:\\primaldegenerate1.lp");
solver.initialSolve();

solver.startFastDual(0);

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

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

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

Is this a bug or am I doing sth wrong? I thought bound changes inside
fast dual were allowed. What would be the fastest way to resolve the
system after such a change? 

Thanks,
Sebastian

--
Sebastian Theophil . stheophil at think-cell.com
Software Engineer

think-cell Software GmbH . Invalidenstr. 34 . 10115 Berlin, Germany 
http://www.think-cell.com <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

_______________________________________________
Clp mailing list
Clp at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/clp
<http://list.coin-or.org/mailman/listinfo/clp> 

--
Sebastian Theophil (stheophil at think-cell.com
<mailto:stheophil at think-cell.com> )
Software Engineer 

think-cell Software GmbH

http://www.think-cell.com <http://www.think-cell.com/> 

Invalidenstr. 34

phone

+49-30-666473-10

10115 Berlin, Germany

toll-free (US)

+1-800-891-8091

Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl

Amtsgericht Berlin-Charlottenburg, HRB 85229

--
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/626b02df/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.gif
Type: image/gif
Size: 105 bytes
Desc: image001.gif
URL: <http://list.coin-or.org/pipermail/clp/attachments/20090721/626b02df/attachment.gif>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.png
Type: image/png
Size: 168 bytes
Desc: image003.png
URL: <http://list.coin-or.org/pipermail/clp/attachments/20090721/626b02df/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image004.png
Type: image/png
Size: 166 bytes
Desc: image004.png
URL: <http://list.coin-or.org/pipermail/clp/attachments/20090721/626b02df/attachment-0001.png>