[Coin-discuss] addCol / resolve problem with OsiClpSolverInterface?
John J Forrest
jjforre at us.ibm.com
Fri Mar 17 05:36:20 EST 2006
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
More information about the Coin-discuss
mailing list