Re: [Help-glpk] Question SImplex

[Andrew Makhorin]

>I don't know what is happening with my model.
>I need to specify binarie (0, 1) variables but on the solution they are
>not integer. The model is simple (Set Covering problem). Each row has
>to be covered by at least one column.

You should use the routine glp_call_bbm1 instead glp_simplex2. The
former implements a branch-and-bound method intended to solve MIP,
but the latter implements a simplex method intended to solve *pure* LP
(and therefore it just ignores any integer variables considering them
as continuous ones).

Btw, you can try writing your models in GLPK/L, which is a modeling
language supported by GLPK. For example, your model could look like the
following:

------------------------------------------------------------------------
model SCP1 /* Set Covering Problem No. 1 */;

binary variables
   x1, x2, x3, x4, x5, x6, x7, x8;

constraints
   p, q, r, s, t, u, v, x, sum;

p :=                     x5 + x6 + x7      >= 1;
q := x1                     + x6      + x8 >= 1;
r :=           x3                + x7      >= 1;
s := x1 + x2           + x5 + x6      + x8 >= 1;
t :=                                    x8 >= 1;
u :=           x3 + x4 + x5 + x6           >= 1;
v :=           x3      + x5      + x7      >= 1;
x := x1      + x3      + x5      + x7      >= 1;

sum := x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8;

minimize sum;

end;
------------------------------------------------------------------------

I ran it using the command

   glpsol --lpm scp1.lpm -o scp1.sol

and GLPSOL found the solution shown below. Is it correct? :+)

------------------------------------------------------------------------
Problem:    SCP1
Rows:       9
Columns:    8 (8 integer, 8 binary)
Non-zeros:  33
Status:     INTEGER OPTIMAL
Objective:  3 (MINimization)

  No.   Row name     St   Activity     Lower bound   Upper bound
----- ------------   -- ------------- ------------- -------------
    1 p              NL             1             1
    2 q              NL             1             1
    3 r              B              2             1
    4 s              B              1             1
    5 sum            B              3
    6 t              NL             1             1
    7 u              NL             1             1
    8 v              B              2             1
    9 x              B              2             1

  No. Column name    St   Activity     Lower bound   Upper bound
----- ------------   -- ------------- ------------- -------------
    1 x1           * NL             0             0             1
    2 x2           * NL             0             0             1
    3 x3           * NS             1             0             1
    4 x4           * NL             0             0             1
    5 x5           * B              0             0             1
    6 x6           * B              0             0             1
    7 x7           * B              1             0             1
    8 x8           * B              1             0             1

End of output
------------------------------------------------------------------------