SOS constraints on continuous variables

[lovasoa]

I am trying to solve the following "toy" problem using the C API of cbc

Maximize
  x + y

Bounds
  x <= 2
  y <= 3

SOS
  sos1: S1 :: x : 1  y : 2
End

all variables are continuous. The expected solution is x=0.0 and y=3.0. But cbc returns x=2.0 and y=3.0.

No error or warning is raised, but cbc seems to silently ignore the SOS constraint.

[jjhforrest]

If I run that as a .lp file using standalone cbc (2.10.5), I get an error message. To get it to work, I added Subject To and it gave me the correct result.

…

On 19/03/2021 16:10, Ophir LOJKINE wrote: I am trying to solve the following "toy" problem using the C API of cbc |Maximize x + y Bounds x <= 2 y <= 3 SOS sos1: S1 :: x : 1 y : 2 End | all variables are continuous. The expected solution is |x=0.0| and |y=3.0|. But cbc returns |x=2.0| and |y=3.0| (ignoring the SOS constraint). — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#376>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABWJYHCK6P6ST7HTNW5IJKTTENZO7ANCNFSM4ZPCRSZA>.

[lovasoa]

I am using the C API (through the rust binding), not the LP format parser.

[lovasoa]

You can reproduce the issue for instance by running this test in the rust binding :

https://github.com/KardinalAI/coin_cbc/blob/master/src/raw.rs#L527-L550

If you remove these lines:

        m.set_integer(0);
        m.set_integer(1);

then the solver returns [-1, -1] instead of [-1, 0]

[lovasoa]

Trying to debug that further, I see that the status of the problem after the solve is 0 when the variables are integers, but -1 when they are continuous. Is that related ?

[lovasoa]

Adding an integer variable with an objective coefficient of 0 and a no constraint seems to be enough to force Cbc to take the SOS constraint into account even for the other, non-integer variables.

@jjhforrest : could this be a bug where the branching algorithm is not started if the problem doesn't contain at least one integer variable ?

[lovasoa]

Testing the workaround, it seems to work on macos, but on linux, cbc fails with

CglPreProcess.cpp:2492: OsiSolverInterface* CglPreProcess::preProcessNonDefault(OsiSolverInterface&, int, int, int): Assertion `numberProhibited_ == oldModel->getNumCols()' failed.

should I open a separate issue ?

[odow]

Related issue: #363

[jjhforrest]

@jjhforrest : could this be a bug where the branching algorithm is not started if the problem doesn't contain at least one integer variable ?

I don't think it is a bug in cbc - may be a bug in rust interface. cbc solved with .lp file quite happily.

[lovasoa]

I don't think it is a bug in cbc - may be a bug in rust interface. cbc solved with .lp file quite happily.

I think this is a bug in the cbc C interface. The rust interface just calls Cbc_solve. The bug is that Cbc_solve doesn't take into account the SOS constraints when there is no integer variable.

[lovasoa]

@jjhforrest

Here is a C program that illustrates that the issue is not in the rust binding but in cbc itself:

 #include  <coin/Cbc_C_Interface.h>
 #include  <stdio.h>
 #include  <string.h>

 int  main(int  argc,char* argv[])
 {
      Cbc_Model* m =Cbc_newModel();
      int  numcols = 2;
      int  numrows = 0;
      int  start[3] = {0};
      int  *index  = 0;
      double  *value =0;
      double  *collb = 0;
      double  colub[] = {2.0, 3.0};
      double  obj[] = {1.0, 1.0};
      double  *rowlb =0;
      double  *rowub =0;
      Cbc_loadProblem(m,
          numcols, numrows,
          start,index,
          value,
          collb, colub,
          obj,
          rowlb, rowub);
      Cbc_setObjSense(m, -1); // maximize

      // sos: x:1 y:2
      int sosRowStarts[] = {0, 2};
      int sosColIndices[] = {0, 1};
      double sosWeights[] = {1., 2.};
      int sosType = 1;
      Cbc_addSOS(m, 1, sosRowStarts, sosColIndices, sosWeights, sosType);

      Cbc_writeLp(m, "/tmp/test.lp");

      int status = Cbc_solve(m);
      printf("Solve status: %d\n", status);
      const double* solution = Cbc_getColSolution(m);
      printf("solution: [%f, %f]", solution[0], solution[1]); 
      Cbc_deleteModel(m);
      return  0;
 }

[jjhforrest]

There may be problems in C interface but your C program is incorrect (and segfaults when I run it). There are two columns so it should be int start[3] = {0}; as the code thinks the total number of elements is start[numcols] The program then gets the correct answer. I do not understand why some messages occur as I am not familiar with C interface.

…

On 20/03/2021 21:54, Ophir LOJKINE wrote: @jjhforrest <https://github.com/jjhforrest> Here is a C program that illustrates that the issue is not in the rust binding but in cbc itself: #include <coin/Cbc_C_Interface.h> #include <stdio.h> #include <string.h> int main(int argc,char* argv[]) { Cbc_Model* m =Cbc_newModel(); int numcols =2; int numrows =0; int start[2] = {0}; int *index =0; double *value =0; double *collb =0; double colub[] = {2.0,3.0}; double obj[] = {1.0,1.0}; double *rowlb =0; double *rowub =0; Cbc_loadProblem(m, numcols, numrows, start,index, value, collb, colub, obj, rowlb, rowub); Cbc_setObjSense(m, -1);// maximize // sos: x:1 y:2 int sosRowStarts[] = {0,2}; int sosColIndices[] = {0,1}; double sosWeights[] = {1.,2.}; int sosType =1; Cbc_addSOS(m,1, sosRowStarts, sosColIndices, sosWeights, sosType); Cbc_writeLp(m,"/tmp/test.lp"); int status =Cbc_solve(m); printf("Solve status: %d\n", status); const double* solution =Cbc_getColSolution(m); printf("solution: [%f, %f]", solution[0], solution[1]); Cbc_deleteModel(m); return 0; } — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#376 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABWJYHFT7XHVTEOUS5X3S6DTEUKRPANCNFSM4ZPCRSZA>.

[lovasoa]

You are right, I updated the code above. It doesn't segfault, and illustrates that the bug is in cbc, not the rust interface.

[odow]

I can take a look at this today (I think I know what the issue is). Until last week, JuMP was using a patched version of Cbc, which was why we didn't find this earlier.

[odow]

This is fixed on master

Cbc/src/Cbc_C_Interface.cpp

Line 2146 in 1706330

|| ((solver->getNumIntegers()+model->nSos)==0)) {

whereas the 2.10 branch doesn't check for SOS constraints:

Cbc/Cbc/src/Cbc_C_Interface.cpp

Line 848 in f40e410

if (solver->getNumIntegers() == 0 || model->relax_ == 1) {

What is the status of the 3.0 release?

[tkralphs]

What is the status of the 3.0 release?

There is a draft PR open (#374) that I'd like to recruit some help in finishing before we go to 3.0. But I know the natives are getting restless. What's left do at a minimum is

• some debugging (there are still probably a few surface-level bugs hanging around that I haven't had time to track down) and
• some thorough testing to make sure there are no performance regressions.

I would also really like to create a minimal CbcSolver class, rename CbcMain1() and move it into that class, make CbcMain0() the default constructor of the CbcParameters class, and finally break up the humongous while loop into some smaller pieces so we can reformat the code. Currently, clang-reformat can't even parse the code in CbcSolver.cpp. Emacs also gets lost when trying to find matching parentheses. It would be a great test case for a code reformatter! I will post a message to Discussions about this. None of this would change any functionality and shouldn't take much time. The heavy lifting is done (there are some nice-to-have things listed in the PR that are a little more difficult, but we could push those off to another release if needed).