Re: [Help-glpk] ILP problem , unexpected solution

[Andrew Makhorin]

> I am trying to solve a simple integer linear program
> with the following constraints

> x1 + x2 +x3 +x4 = 1 
>  10.00x1 + (-1.00)x2 < 5.00 
> 1.00x2 and +(-2.00)x3  < 5.00
> 2.00x3 + (-0.50)x4  < 5.00 
> I have no objective function to optimise. 

> I am expecting output as x1 = 0 x2 = 1 x3 = 0 and x4 = 0

> But when i solved using glpk 4.23 , i always get the output x1 = 0 x2 = 0 x3 
> = 0 and x4 = 0

> My code is as follows. Can somebody pls help me pointing out the problem.

> int main()
> {
>     glp_prob *lp;
>     int ia[1+1000], ja[1+1000]; 
>     double ar[1+1000];
>     int  x1, x2, x3,x4; 
> ;
>     
>     outfile = fopen("lpout.out","w");   
>     float cur1, cur2, cur3, cur4;
>     float bound_p, bound_q, bound_r;
>     
>      
>     glp_iocp      parm;
>     glp_smcp simplex_parm;
>     int ret;
>     
>      
>      /*10.00x1 + (-1.00)x2 < 5.00 
>              1.00x2 and +(-2.00)x3  < 5.00
>              2.00x3 + (-0.50)x4  < 5.00 
>              */
>      lp = glp_create_prob(); 
>      glp_set_prob_name(lp, "sample"); 
>      glp_set_obj_dir(lp, GLP_MAX); 
>     
>      
>      glp_add_rows(lp, 4);
>      
>      bound_p = 5 ;
>      bound_q =  5;
>      bound_r = 5 ;
>      
>      fprintf(outfile, "bound_p = %.2f bound_q %.2f bound_r =  %.2f \n ", 
> bound_p, bound_q, bound_r);
>      
>      glp_set_row_name(lp, 1, "p");
>      glp_set_row_bnds(lp, 1, GLP_UP, -DBL_MAX, bound_p); 
>      glp_set_row_name(lp, 2, "q"); 
>      glp_set_row_bnds(lp, 2, GLP_UP, -DBL_MAX, bound_q); 
>      glp_set_row_name(lp, 3, "r"); 
>      glp_set_row_bnds(lp, 3, GLP_UP, -DBL_MAX, bound_r);
>     
>      glp_set_row_name(lp, 4, "o");
>      glp_set_row_bnds(lp, 4, GLP_FX, 1, 1); 
>                                      
>      glp_add_cols(lp, 4); 
>      glp_set_col_name(lp, 1, "x1"); 
>      glp_set_col_bnds(lp, 1, GLP_DB, 0, 1); 
>      glp_set_col_kind(lp, 1, GLP_IV);
>       
>      glp_set_col_name(lp, 2, "x2"); 
>      glp_set_col_bnds(lp, 2, GLP_DB, 0, 1); 
>      glp_set_col_kind(lp, 2, GLP_IV);
>      
>      glp_set_col_name(lp, 3, "x3"); 
>      glp_set_col_bnds(lp, 3, GLP_DB, 0, 1); 
>      glp_set_col_kind(lp, 3, GLP_IV);
>      
>      glp_set_col_name(lp, 4, "x4"); 
>      glp_set_col_bnds(lp, 4, GLP_DB, 0, 1); 
>      glp_set_col_kind(lp, 4, GLP_IV);
>              
>      
>      
>      ia[1] = 2, ja[1] = 1, ar[1] = 10.0;
>      ia[2] = 2, ja[2] = 2, ar[2] = -1.0;
>      ia[3] = 2, ja[3] = 3, ar[3] = 0.0;
>      ia[4] = 2, ja[4] = 4, ar[4] = 0.0;
>      
>      
>    
>      
>      ia[5] = 3, ja[5] = 1, ar[5] = 0.0;
>      ia[6] = 3, ja[6] = 2, ar[6] = 1.0;
>      ia[7] = 3, ja[7] = 3, ar[7] = -2.0;
>      ia[8] = 3, ja[8] = 4, ar[8] = 0.0;
>      
>      
>      ia[9] = 4, ja[9] = 1, ar[9] = 0.0;
>      ia[10] = 4, ja[10] = 2, ar[10] = 0.0; 
>      ia[11] = 4, ja[11] = 3, ar[11] = 2.0; 
>      ia[12] = 4, ja[12] = 4, ar[12] = -0.5;
>      
>      fprintf(outfile, "x1 + x2 +x3 +x4 = 1 \n");
>      /*x1 + x2+ x3 + x4  = o */
>      ia[13] = 1, ja[13] = 1, ar[13] = 1; 
>      ia[14] = 1, ja[14] = 2, ar[14] = 1; 
>      ia[15] = 1, ja[15] = 3, ar[15] = 1;
>      ia[16] = 1, ja[16] = 4, ar[16] = 1;
>           
>      glp_load_matrix(lp, 16, ia, ja, ar);
>      
>      glp_init_smcp( simplex_parm);
>      simplex_parm.presolve = GLP_OFF;
>      
>      if(glp_simplex(lp,  simplex_parm) != 0)
>      {
>          printf("failure of simplex\n");
>          exit(-1);
>      } 


>      
>     x1 = glp_get_col_prim(lp, 1);
>     x2 = glp_get_col_prim(lp, 2);
>     x3 = glp_get_col_prim(lp, 3);
>     x4 = glp_get_col_prim(lp, 4);
>      
>     fprintf(outfile,"\n x1 = %d; x2 = %d; x3 = %d x4 = %d \n", x1, x2, x3, 
> x4);
>    
>     glp_delete_prob(lp);

>     return 0;
> }
> The terminal output is
> "      0:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (0)
>       1:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
> OPTIMAL SOLUTION FOUND"

> Thanks,
> satish

Looks like you missed the very first constraint.

Once you have built your instance, you can write it to a text file
in cplex lp format for visual inspection:

   glp_write_lp(lp, NULL, "foobar.lp");

This also allows running your instance with the glpsol stand-alone
solver:

   $ glpsol --cpxlp foobar.lp

FYI: the most recent version of glpk is 4.41.