[Coin-discuss] addCol / resolve problem with OsiClpSolverInterface?

[Tobias Achterberg]

Hi Stefan,

I see nothing wrong in the dual solution. Probably you are confused
about the definition of the dual LP.

Here again is your primal LP (with the corresponding dual multipliers
in brackets):

Min  68 x0 + 8 x1 + 7 x2 + 6 x3 + 10 x4
s.t.    x0 +   x1               +    x4  = 1  (y0)
        x0 +          x2        +    x4  = 1  (y1)
        x0 +                 x3          = 1  (y2)
        x0                              <= 1  (r0)
               x1                       <= 1  (r1)
                      x2                <= 1  (r2)
                             x3         <= 1  (r3)
                                     x4 <= 1  (r4)
        x0,    x1,    x2,    x3         >= 0

The common mistake is that one forgets about the upper bounds in the
dual. Here is the dual:

Max   y0 + y1 + y2 + r0 + r1 + r2 + r3 + r4
s.t.  y0 + y1 + y2 + r0                      <= 68  (x0)
      y0                + r1                 <=  8  (x1)
           y1                + r2            <=  7  (x2)
                y2                + r3       <=  6  (x3)
      y0 + y1                          + r4  <= 10  (x4)
      y0,  y1,  y2  free variables
                     r0,  r1,  r2,  r3,  r4  <=  0

As far as I understood, the dual solution you obtained was y0=8, y1=7,
y2=6, r0=r1=r2=r3=0, r4=-5. This is a feasible dual solution, and its
objective value is indeed 8+7+6-5 = 16.


Best regards,  Tobias


Stefan R0pke wrote:
> Hello,
> 
> I ran into a problem when using OsiClpSolverInterface. To illustrate the
> problem, consider the following LP:
> 
> Minimize
>  68 x0 + 8 x1 + 7 x2 + 6 x3
> Subject To
>     x0 +   x1                = 1
>     x0 +          x2         = 1
>     x0 +                 x3  = 1
> Bounds
>  0 <= x0 <= 1
>  0 <= x1 <= 1
>  0 <= x2 <= 1
>  0 <= x3 <= 1
> End
> 
> I solve the problem using OsiClpSolverInterface and get the solution x1
> = x2 = x3 = 1 as expected. Then I add an extra variable (x4) to the
> problem to get
> 
> Minimize
>  68 x0 + 8 x1 + 7 x2 + 6 x3 + 10 x4
> Subject To
>     x0 +   x1               +    x4  = 1
>     x0 +          x2        +    x4  = 1
>     x0 +                 x3          = 1
> 
> I do this with the addCol method on OsiClpSolverInterface. After calling
> resolve on OsiClpSolverInterface I get the expected solution x3=x4=1 but
> the reduced costs and dual variables appear to be wrong.
> OsiClpSolverInterface reports that the reduced cost of x4 is -5 (I had
> expected it to be zero) and the dual variables are 8, 7 and 6 which
> doesn't add up to 16 as I expected.
>  If I try to resolve the problem from scratch then I get the expected
> values.
>  Am I doing something wrong?
> 
> Below is sample code to illustrate the problem
> 
> Best regards,
> Stefan
> 
> ----------- main.cpp -----------
> 
> #include <OsiClpSolverInterface.hpp>
> #include <CoinPackedVector.hpp>
> 
> using namespace std;
> 
> void printVector(const string &strHeader, const string &strVarName,
> const double *pVec, int iNElements)
> {
>     int i;
>     cout << strHeader << ": ";
>     for (i=0; i < iNElements; i++)
>         cout << strVarName << i << "=" << pVec[i] << "  ";
>     cout << endl;
> }
> 
> void printSolution(const OsiSolverInterface &osiSolver)
> {
>     cout << "LP value: " << osiSolver.getObjValue() << endl;
>     printVector("Solution", "x", osiSolver.getColSolution(),
> osiSolver.getNumCols());
>     printVector("Reduced cost", "r", osiSolver.getReducedCost(),
> osiSolver.getNumCols());
>     printVector("Dual variables", "d", osiSolver.getRowPrice(),
> osiSolver.getNumRows());
> }
> 
> int main(void)
> {
>     OsiClpSolverInterface osiSolver;
> 
>     // read LP
>     osiSolver.readLp("test.lp");
>     osiSolver.setObjSense(1);
>     osiSolver.initialSolve();
>     cout << "**** Initial problem: ****" << endl;
>     printSolution(osiSolver);
> 
>     // Add a column with cost 10, covering row 0 and 1.
>     CoinPackedVector column;
>     column.insert(0,1);
>     column.insert(1,1);
>     osiSolver.addCol(column, 0, 1, 10);
>     osiSolver.resolve();
>     cout << "**** After adding column and resolve: ****" << endl;
>     printSolution(osiSolver);
> 
>     // Solve from scratch:
>     CoinWarmStart *pWarmStart = osiSolver.getEmptyWarmStart();
>     osiSolver.setWarmStart(pWarmStart);
>     delete pWarmStart;
>     osiSolver.resolve();
>     cout << "**** Solved from scratch: ****" << endl;
>     printSolution(osiSolver);
>     return 0;
> }
> 
> ----------- test.lp -----------
> 
> Minimize
>  68 x0 + 8 x1 + 7 x2 + 6 x3
> Subject To
>  x0 + x1 = 1
>  x0 + x2 = 1
>  x0 + x3 = 1
> Bounds
>  0 <= x0 <= 1
>  0 <= x1 <= 1
>  0 <= x2 <= 1
>  0 <= x3 <= 1
> End
> 
> 
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss

-- 
Tobias Achterberg          Konrad-Zuse-Zentrum fuer
                           Informationstechnik Berlin
Tel: +49 (0)30 84185-301   Takustr. 7
Email: achterberg at zib.de   D-14195 Berlin, Germany