Solving Integer Second Order Cone Program by SCIP. (2012/06/29)

Kazuhiro KOBAYASHI

SOCP with integer variables can be solved by using SCIP. We describe the sample code to solve it in C++ language.

SOC constraint handler is included in SCIP. The constraint handler implements second order cone constraints of the form

\( \sqrt{ \gamma+ \sum_{i=1}^n \left( \alpha_i \left( x_i+\beta_i\right) \right)^2 } \leq \alpha_{n+1} \left( x_{n+1} + \beta_{n+1} \right). \)

The simplest form of the second order cone is represented by

\( \sqrt{ \sum_{i=1}^n x_i^2 } \leq x_{n+1}. \)

The parameters to represent this simplest second order cone constraints is \( \alpha_i = 1, \beta_i=0, \gamma=0, \alpha_{n+1}=1, \beta_{n+1}=0. \)

We consider an instance of linear program with an SOC constraints
\begin{align*} \max & x+y \\ \mbox{s.t.} & x+3y=17 &\mbox{(line 1)}, \\ & 4x+3y=23 &\mbox{(line 2)}, \\ & \sqrt{y^2} \leq x & \mbox{(SOC)}, \\ & x,y : \mbox{integer}. \end{align*} soclines
The two two lines, line 1 and line 2, and the objective function with value 7, x+y=7, are shown in the above figure. The horizontal axis corresponds to x, and the vertical axix corresponds to y.

Without the SOC constraint, the problem is the LP, whose optimal value is 7 at (2,5). By introducing the SOC constraint, the optimal value becomes 6 at (4,2).

The C++ code to solve the LP with the SOC constraints is shown below.

int main(
   int                        argc,          /**< number of arguments from the shell */
   char**                     argv           /**< array of shell arguments */
   )
{
    //creating problem
    SCIP* scip;
    SCIPcreate(&scip);
    SCIPincludeDefaultPlugins(scip);
    SCIPcreateProb(scip, "LP with SOC", NULL, NULL, NULL, NULL, NULL, NULL, NULL);
    SCIPsetObjsense(scip, SCIP_OBJSENSE_MAXIMIZE);

    std::vector< SCIP_VAR* > vars(2); // vector to hold two variables x and y.

    SCIP_VAR* var;
    SCIPcreateVar(scip, &var, "x", 0.0, 10.0, 1.0, SCIP_VARTYPE_INTEGER, TRUE, FALSE, 
                  NULL, NULL, NULL, NULL, NULL);
    SCIPaddVar(scip,var);
    vars[0] = var;

    SCIPcreateVar(scip, &var, "y", 0.0, 10.0, 1.0, SCIP_VARTYPE_INTEGER, TRUE, FALSE, 
                  NULL, NULL, NULL, NULL, NULL);
    SCIPaddVar(scip,var);
    vars[1] = var;

    std::vector cons(3); // vector to hold pointers to three constraints.
    SCIP_CONS* con;

    //===== creation of two linear constraints =====
    //creation of x+3y=17
    SCIPcreateConsLinear(scip, &con, "line1", 0, NULL, NULL, 0, 17.0, TRUE, 
                         TRUE, TRUE, TRUE, TRUE, FALSE, 
                         FALSE, FALSE, FALSE, FALSE);
    SCIPaddCoefLinear(scip,con,vars[0],1.0); // 
    SCIPaddCoefLinear(scip,con,vars[1],3.0);    
    SCIPaddCons(scip, con);
    cons[0] = con;

    //creation of 4x+3y=23
    SCIPcreateConsLinear(scip, &con, "line2", 0, NULL, NULL, 0, 23.0, TRUE, 
                         TRUE, TRUE, TRUE, TRUE, FALSE, 
                         FALSE, FALSE, FALSE, FALSE);
    SCIPaddCoefLinear(scip,con,vars[0],4.0);
    SCIPaddCoefLinear(scip,con,vars[1],3.0);
    SCIPaddCons(scip,con);
    cons[1] = con;

    //===== creation of the SOC constraint =====
    // pointer to hold SOC constraint sqrt( sum_i=1^n x_i ) ¥geq alpha_n+1 ( x_{n+1} + beta_{n+1})
    SCIP_CONS *conssoc;    
    SCIP_VAR** rhsvars;
    rhsvars = new SCIP_VAR*[2];
    rhsvars[0] = vars[0]; //x 
    
    SCIP_VAR** lhsvars;
    lhsvars = new SCIP_VAR*[2];
    lhsvars[0] = vars[1]; //y 
   
    //vars[0] : x, vars[1]:y   I want y <= x^2    
    SCIPcreateConsSOC(scip, &conssoc, "soc", 1,//(n)
                      lhsvars, //array with variables on left hand side 
                      NULL, //a_i is zero
                      NULL, //b_i is zero
                      0, //gamma is zero
                      rhsvars[0], //var in rhs
                      1.0, // alpha_n+1 
                      0.0,  // beta_{n+1}
                      TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE);
    cons[2] = conssoc;
    SCIPaddCons(scip, conssoc);
    
    FILE* tsocp=fopen("test1.socp","w");
    if(tsocp==NULL){
        std::cout << "cannot open file:" << "test1.socp" << std::endl;
    }
    SCIPprintCons(scip, conssoc, tsocp);

    //solve the problem
    SCIPsolve(scip);

    SCIP_SOL* sol=SCIPgetBestSol(scip);
    SCIPprintStatistics(scip, stdout);
    std::cout << "x:" << SCIPgetSolVal(scip, sol, vars[0]) << std::endl;
    std::cout << "y:" << SCIPgetSolVal(scip, sol, vars[1]) << std::endl;
    
    SCIPreleaseVar(scip, &vars[0]);
    SCIPreleaseVar(scip, &vars[1]);

    SCIPreleaseCons(scip,&cons[0]);
    SCIPreleaseCons(scip,&cons[1]);
    SCIPreleaseCons(scip,&conssoc);
  

    SCIPfree(&scip);
   return 0;
}