[Osi] How to define SOS constraint

[John Forrest]

Christian,

You will probably be better off using Cbc via CbcModel rather than
OsiCbc.

I attach a modified sos.cpp which seems to work on your example.  It
does give one spurious warning when it sees there are no integers but it
goes ahead and solves it - this is the output (I added a redundant
initialSolve so I could see relaxed objective value)

Coin0506I Presolve 0 (-8) rows, 0 (-8) columns and 0 (-18) elements
Clp0000I Optimal - objective value 2
Coin0511I After Postsolve, objective 2, infeasibilities - dual 0 (0),
primal 0 (0)
Clp0032I Optimal objective 2 - 0 iterations time 0.002, Presolve 0.00
Cbc3007W No integer variables - nothing to do
Cbc0016I Integer solution of 3 found by strong branching after 0
iterations and 0 nodes (0.00 seconds)
Cbc0001I Search completed - best objective 3, took 0 iterations and 0
nodes (0.00 seconds)
Cbc0032I Strong branching done 2 times (2 iterations), fathomed 1 nodes
and fixed 0 variables
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Problem took 0 seconds, 0 nodes with objective 3 Finished
AC_1 = 1
AC_2 = 1
BA_2 = 1
AC = 2

John Forrest

On Mon, 2010-05-17 at 18:08 +0200, Christian Schmidt wrote:
> Hi,
> 
> I'd like to define a pure SOS1 constraint (without integers). From the 
> code examples I've built the following model - a network flow with two 
> sources A and B for products 1 and 2 resp. and one sink C. The sink 
> should only be delivered from one source.
> 
> The model is:
> 
> min AC_1 + AC_2 + BC_1 + BC_2 + AB_1 + BA_2
> A_1: -AC_1 - AB_1 = -1
> A_2:  BA_2 - AC_2 = 0
> B_1:  AB_1 - BC_1 = 0
> B_2: -BC_2 - BA_2 = -1
> C_1:  AC_1 + BC_1 = 1
> C_2:  AC_2 + BC_2 = 1
> sAC:  AC_1 + AC_2 = AC
> sBC:  BC_1 + BC_2 = BC
> 
> SOS
> C: AC, BC <= 1
> 
> In my attached implementation the SOS constraint is simply ignored. 
> What's wrong?
> 
> Thanks for any ideas,
> Christian
> 
> 
> #include "OsiSolverInterface.hpp"
> #include "OsiCbcSolverInterface.hpp"
> 
> template<typename T, int N> inline
> int count(const T (&)[N]) { return N; }
> 
> int main(int argc, char* argv[])
> {
>    const double inf = 1e20;
> 
>    // Columns
>    const char* col[] = { "AC_1", "AC_2", "BC_1", "BC_2", "AB_1", "BA_2", 
> "AC", "BC" };
>    enum cols        { AC_1, AC_2, BC_1, BC_2, AB_1, BA_2,   AC,   BC };
>    double collb[] = {  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0 };
>    double colub[] = {  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf };
>    double colobj[]= {  1.0,  1.0,  1.0,  1.0,  1.0,  1.0,  0.0,  0.0 };
>    const int cols = count(col);
>    assert(cols == count(col) && cols == count(collb) && cols == 
> count(colub) && cols == count(colobj));
> 
>    // Rows
>    enum rows        {  A_1,  A_2,  B_1,  B_2,  C_1,  C_2,  rAC,  rBC };
>    double rowlb[] = { -1.0,  0.0,  0.0, -1.0,  1.0,  1.0,  0.0,  0.0 };
>    double rowub[] = { -1.0,  0.0,  0.0, -1.0,  1.0,  1.0,  0.0,  0.0 };
>    const int rows = count(rowlb);
>    assert(rows == count(rowlb) && rows == count(rowub));
> 
>    // Matrix
>    int index[]  = {
>      A_1, C_1, rAC // AC_1
>    , A_2, C_2, rAC // AC_2
>    , B_1, C_1, rBC // BC_1
>    , B_2, C_2, rBC // BC_2
>    , A_1, B_1 // AB_1
>    , B_2, A_2 // BA_2
>    , rAC // AC
>    , rBC // BC
>    };
>    double values[] = {
>      -1, +1, +1
>    , -1, +1, +1
>    , -1, +1, +1
>    , -1, +1, +1
>    , -1, +1
>    , -1, +1
>    , -1
>    , -1
>    };
>    int start[] = { 0, 3, 6, 9, 12, 14, 16, 17, count(index) };
>    assert(count(index) == count(values) && count(index) == start[cols]);
>    assert(count(start) == cols+1);
> 
>    OsiSolverInterface* solver = new OsiCbcSolverInterface();
>    solver->loadProblem(cols, rows, start, index, values, collb, colub, 
> colobj, rowlb, rowub);
> 
>    int index2[] =  { AC, BC };
>    OsiObject* sos[] = {
>      new OsiSOS(solver, count(index2), index2, NULL, 1)
>    };
>    solver->addObjects(1, sos);
> 	
>    solver->setObjSense(1); // minimize
>    solver->branchAndBound();
>    bool solved = solver->isProvenOptimal();
>    if (solved) {
>      const double* solution = solver->getStrictColSolution();
>      const double eps = solver->getIntegerTolerance();
>      for (int i = 0; i < cols; i++)
>        if (fabs(solution[i]) > eps)
>          std::cout << col[i] << " = " << solution[i] << std::endl;
>    } // if solved
> 
>    return solved;
> }
> 
> _______________________________________________
> Osi mailing list
> Osi at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/osi
> 

-------------- next part --------------
A non-text attachment was scrubbed...
Name: sosTest.cpp
Type: text/x-c++src
Size: 3040 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/osi/attachments/20100518/d6f2aeca/attachment.bin>