Does OsiClp handle correctly lower bounds?

[alvaropalmaaste]

I have a tiny LP:

max x2
subj to
x1 + x2 <= K
x1 FREE
x2 FREE

In CPLEX, this problem is solved as:

x1 = -oo
x2 = oo

but in Clp (run via Osi), it results on

x1 = K
x2 = 0

which gives me the impression that Clp is unwillingly forcing my LB to 0, despite the fact I explicitly created my problem with LB = -oo and UB = +oo in both COIN and CPLEX:

• OsiClp:

m_modelIP.solver()->addCols(numVariables, matBeg.data(), matInd.data(), matVal.data(), vlb.data(), vub.data(), obj.data());

• CPLEX

rval = CPXXaddcols(m_env, m_lp, numVariables, matInd.size(), obj.data(), matBeg.data(), matInd.data(), matVal.data(), vlb.data(), vub.data(), NULL);

Surfing through the Osi and Clp sources, I noticed these lines:

Osi/OsiSolverInterface.cpp

367 void OsiSolverInterface::addCols(const int numcols, const CoinBigIndex *columnStarts,
368   const int *rows, const double *elements,
369   const double *collb, const double *colub,
370   const double *obj)
371 {
372   double infinity = getInfinity();
373   for (int i = 0; i < numcols; ++i) {
374     CoinBigIndex start = columnStarts[i];
375     int number = static_cast< int >(columnStarts[i + 1] - start);
376     assert(number >= 0);
377     addCol(number, rows + start, elements + start, collb ? collb[i] : 0.0,
378       colub ? colub[i] : infinity,
379       obj ? obj[i] : 0.0);
380   }
381 }

Notice line 377-378, setting 0 as the LB when it's not explicitly set. Also:

Clp/src/OsiClp/OsiClpSolverInterface.cpp

 4268   if (collb) {
 4269     for (iCol = 0; iCol < numcols; iCol++) {
 4270       lower[iCol] = forceIntoRange(collb[iCol], -OsiClpInfinity, OsiClpInfinity);
 4271       if (lower[iCol] < -1.0e27)
 4272         lower[iCol] = -COIN_DBL_MAX;
 4273     }
 4274   } else {
 4275     CoinFillN(lower, numcols, 0.0);
 4276   }
 4277   if (colub) {
 4278     for (iCol = 0; iCol < numcols; iCol++) {
 4279       upper[iCol] = forceIntoRange(colub[iCol], -OsiClpInfinity, OsiClpInfinity);
 4280       if (upper[iCol] > 1.0e27)
 4281         upper[iCol] = COIN_DBL_MAX;
 4282     }
 4283   } else {
 4284     CoinFillN(upper, numcols, COIN_DBL_MAX);

(Notice the inconsistency between lines 4272 and 4275 v/s 4281 and 4284)

So, my doubt is: Am I misunderstanding the way to use CLP lower bounds and they assume I should always use the standard form to model the LP? Or is there a bug in there?

[jjhforrest]

If I code the problem you describe (changing to minimization to save a line of coding) - I get Coin0508I Presolve thinks problem is unbounded Clp3003W Analysis indicates model infeasible or unbounded Clp0006I 0 Obj 0 Dual inf 99.999999 (1) w.o. free dual inf (0) Clp0006I 0 Obj 0 Dual inf 99.999999 (1) w.o. free dual inf (0) Clp0006I 1 Obj -10 Dual inf 99.999999 (1) w.o. free dual inf (0) Clp0006I 1 Obj -10 Dual inf 99.999999 (1) w.o. free dual inf (0) Clp0002I Dual infeasible - objective value -10 Clp0032I DualInfeasible objective -10 - 1 iterations time 0.002 So x2 will be 10 in solution (as that was last value before finding it was dual infeasible), but the status of problem is dual infeasible - not Optimal. I think this is reasonable. John Forrest

…

On 30/08/2021 21:10, Alvaro Palma wrote: I have a tiny LP: |max x2 subj to x1 + x2 <= K x1 FREE x2 FREE | In CPLEX, this problem is solved as: |x1 = -oo x2 = oo | but in Clp (run via Osi), it results on |x1 = K x2 = 0 | which gives me the impression that Clp is unwillingly forcing my LB to 0, despite the fact I *explicitly* created my problem with |LB = -oo| and |UB = +oo| in both COIN and CPLEX: * OsiClp: |m_modelIP.solver()->addCols(numVariables, matBeg.data(), matInd.data(), matVal.data(), vlb.data(), vub.data(), obj.data()); | * CPLEX |rval = CPXXaddcols(m_env, m_lp, numVariables, matInd.size(), obj.data(), matBeg.data(), matInd.data(), matVal.data(), vlb.data(), vub.data(), NULL); | Surfing through the Osi and Clp sources, I noticed these lines: |Osi/OsiSolverInterface.cpp | |367 void OsiSolverInterface::addCols(const int numcols, const CoinBigIndex *columnStarts, 368 const int *rows, const double *elements, 369 const double *collb, const double *colub, 370 const double *obj) 371 { 372 double infinity = getInfinity(); 373 for (int i = 0; i < numcols; ++i) { 374 CoinBigIndex start = columnStarts[i]; 375 int number = static_cast< int >(columnStarts[i + 1] - start); 376 assert(number >= 0); 377 addCol(number, rows + start, elements + start, collb ? collb[i] : 0.0, 378 colub ? colub[i] : infinity, 379 obj ? obj[i] : 0.0); 380 } 381 } | Notice line 377-378, setting 0 as the LB when it's not explicitly set. Also: |Clp/src/OsiClp/OsiClpSolverInterface.cpp | |4268 if (collb) { 4269 for (iCol = 0; iCol < numcols; iCol++) { 4270 lower[iCol] = forceIntoRange(collb[iCol], -OsiClpInfinity, OsiClpInfinity); 4271 if (lower[iCol] < -1.0e27) 4272 lower[iCol] = -COIN_DBL_MAX; 4273 } 4274 } else { 4275 CoinFillN(lower, numcols, 0.0); 4276 } 4277 if (colub) { 4278 for (iCol = 0; iCol < numcols; iCol++) { 4279 upper[iCol] = forceIntoRange(colub[iCol], -OsiClpInfinity, OsiClpInfinity); 4280 if (upper[iCol] > 1.0e27) 4281 upper[iCol] = COIN_DBL_MAX; 4282 } 4283 } else { 4284 CoinFillN(upper, numcols, COIN_DBL_MAX); | (Notice the inconsistency between lines 4272 and 4275 v/s 4281 and 4284) So, my doubt is: Am I misunderstanding the way to use CLP lower bounds and they assume I should always use the standard form to model the LP? Or is there a bug in there? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#202>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABWJYHASO3DCSFTL3NMQS63T7PQTLANCNFSM5DCTBJGA>. Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[alvaropalmaaste]

I understand the answer and it's reasonable, in fact, my code wasn't properly checking the return status.

However, just from the code point of view, it puzzles me why LB is treated different than UB regarding the default settings. Why setting UB to +oo in that case, but LB as 0 and not -oo as I'd intuitively expect?

[jjhforrest]

Very few real world problems have all lower bounds infinite, but many do have zero lower bound and infinite upper bound - so it makes sense as a default if no array was given. Also historical. Dantzig's original Simplex algorithm in the 1940s was with linear constraints and 0/infinite bounds. The first LP codes I worked on used that principle, until, when computers had slightly more memory, someone noticed that there was not that much extra coding to replace x <= 10 with a simple upper bound and remove the constraint. John Forrest

…

On 31/08/2021 14:56, Alvaro Palma wrote: I understand the answer and it's reasonable, in fact, my code wasn't properly checking the return status. However, just from the code point of view, it puzzles me why |LB| is treated different than |UB| regarding the default settings. Why setting |UB| to |+oo| in that case, but |LB| as |0| and not |-oo| as I'd intuitively expect? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#202 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABWJYHBBCMIDER7M2Z46NOTT7TNRPANCNFSM5DCTBJGA>. Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[alvaropalmaaste]

Thanks a lot for your answers. As suggested, I coded a small problem to check the behavior regarding negative values in the LB:

NAME          TESTPROB
ROWS
 N  COST
 L  LIM1
COLUMNS
    XONE      COST                 1 LIM1                 1
    YONE      LIM1                 1
RHS
    RHS1      LIM1                 5
BOUNDS
 UP BND1      XONE                 8
 UP BND1      YONE                 8
 LO BND1      XONE                 -2
 LO BND1      YONE                 -2
ENDATA

which is basically

max x1
subject to
x1 + x2 <= 5
-2 <= x1 <= 8
-2 <= x2 <= 8

and run it using the CLP command line tool:

[11:29 apalma@alicanmini1 -> ~] clp file.mps -maximize -primalsimplex -solution solfile
Coin LP version 1.17.6, build Jul 11 2020
command line - clp file.mps -maximize -primalsimplex -solution solfile
At line 1 NAME          TESTPROB
At line 2 OBJSENSE
MAX found after OBJSENSE - Coin ignores
At line 4 ROWS
At line 7 COLUMNS
At line 10 RHS
At line 12 BOUNDS
At line 17 ENDATA
Problem TESTPROB has 1 rows, 2 columns and 2 elements
Model was imported from ./file.mps in 0.00011 seconds
Presolve 0 (-1) rows, 0 (-2) columns and 0 (-2) elements
Empty problem - 0 rows, 0 columns and 0 elements
Optimal - objective value 7
After Postsolve, objective 7, infeasibilities - dual 0 (0), primal 0 (0)
Optimal objective 7 - 0 iterations time 0.002, Presolve 0.00

which is the expected answer.

So, in summary, I simply had a bug in my code for relaying on the value of the returned solution without properly checking the state of that solution beforehand and basically CPLEX was also cleaning up the solution to avoid reporting garbage, while CLP didn't (but again, the problem is in my side, since COIN was telling me that solution was garbage).