[Coin-discuss] addCol / resolve problem with OsiClpSolverInterface?
Stefan R0pke
sropke at diku.dk
Fri Mar 17 11:33:47 EST 2006
Dear Tobias and John,
Thank you for your clear answers, it makes sense to me now!
It seems like I have to take the course on linear programming once again ;-)
Best regards,
Stefan
On Fri, 17 Mar 2006, John J Forrest wrote:
> Tobias - thanks,
>
> Stefan - if you want more predictable results and expect reduced cost on
> added variable to be zero for your algorithm then you can always give an
> infinite upper bound to x4 - resolve and then set bound. Modifying your
> example code shows this and will work if the bound you want is not less
> than implied bound.
>
> John Forrest
>
>
>
> Tobias Achterberg
> <achterberg at zib.d
> e> To
> Sent by: Discussions about open source
> coin-discuss-boun software for Operations Research
> ces at list.coin-or. <coin-discuss at list.coin-or.org>
> org cc
>
> Subject
> 03/17/06 03:11 AM Re: [Coin-discuss] addCol / resolve
> problem with
> OsiClpSolverInterface?
> Please respond to
> Discussions about
> open source
> software for
> Operations
> Research
> <coin-discuss at lis
> t.coin-or.org>
>
>
>
>
>
>
> 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
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
>
>
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
>
More information about the Coin-discuss
mailing list