help-glpk
[Top][All Lists]

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

 From: satish raman Subject: Re: [Help-glpk] ILP problem , unexpected solution Date: Wed, 30 Dec 2009 00:43:01 +0530

On Tue, Dec 29, 2009 at 7:51 PM, Andrew Makhorin wrote:
> Below here is your instance passed to glp_simplex in cplex format:

> \* Problem: sample *\

> Maximize
>  obj: 0 x1

> Subject To
>  p: + x4 + x3 + x2 + x1 <= 5
>  q: - x2 + 10 x1 <= 5
>  r: - 2 x3 + x2 <= 5
>  o: - 0.5 x4 + 2 x3 = 1

> Bounds
>  0 <= x1 <= 1
>  0 <= x2 <= 1
>  0 <= x3 <= 1
>  0 <= x4 <= 1

> Generals
>  x1
>  x2
>  x3
>  x4

> End

Below here is the solution. (Note that in your program x1, x2,
x3, and x4 are declared as int.)

Problem:
Rows:       4
Columns:    4
Non-zeros:  10
Status:     OPTIMAL
Objective:  obj = 0 (MAXimum)

No.   Row name   St   Activity     Lower bound   Upper bound
------ ------------ -- ------------- ------------- -------------
1 p            B              1                           5
2 q            NU             5                           5
3 r            B             -1                           5
4 o            NS             1             1             =

No. Column name  St   Activity     Lower bound   Upper bound
------ ------------ -- ------------- ------------- -------------
1 x1           B            0.5             0             1
2 x4           NL             0             0             1
3 x3           B            0.5             0             1
4 x2           NL             0             0             1

Sorry for the botchup. I did some code juggling and posted incorrect code. I have posted the modified code at the end. I have upgraded to glpk 4.41. I actually want x1, x2 ,x3 ,x4 to take only binary values 0 and 1. I have used glp_set_col_kind function to set the column kind to  GLP_IV
my foobar.lp(glp_write_lp function's output) is as follows

\* Problem: sample *\

Maximize
obj: 0 x1

Subject To
p: - x2 + 10 x1 <= 5
q: - 2 x3 + x2 <= 5
r: - 0.5 x4 + 2 x3 <= 5
o: + x4 + x3 + x2 + x1 = 1

Bounds
0 <= x1 <= 1
0 <= x2 <= 1
0 <= x3 <= 1
0 <= x4 <= 1

Generals
x1
x2
x3
x4

End

the code
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);

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_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, ja = 1, ar = 10.0;
ia = 1, ja = 2, ar = -1.0;
ia = 1, ja = 3, ar = 0.0;
ia = 1, ja = 4, ar = 0.0;

ia = 2, ja = 1, ar = 0.0;
ia = 2, ja = 2, ar = 1.0;
ia = 2, ja = 3, ar = -2.0;
ia = 2, ja = 4, ar = 0.0;

ia = 3, ja = 1, ar = 0.0;
ia = 3, ja = 2, ar = 0.0;
ia = 3, ja = 3, ar = 2.0;
ia = 3, ja = 4, ar = -0.5;

fprintf(outfile, "x1 + x2 +x3 +x4 = 1 \n");
/*x1 + x2+ x3 + x4  = o */
ia = 4, ja = 1, ar = 1;
ia = 4, ja = 2, ar = 1;
ia = 4, ja = 3, ar = 1;
ia = 4, ja = 4, ar = 1;

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

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;
}

I get x1 , x2, x3 and x4 all zero's
I think The right solution is x1 can't be one and one of other 3 variables should be 1. I don't know if i am doing something silly.
Is it okay to have x1, x2 , x3, x4 to be int type? Are there any special type that i should use.