Re: [Help-glpk] Are my integer constraints being ignored?

[Brady Hunsaker]

On Wed, 2004-05-19 at 19:06, Alan Larkin wrote:
> When solving a MILP with GLPK via Matlab (glpkmex) I am getting non-integer
> solutions. I could accept that (I wouldnt be happy but I could accept it) if
> there was some indication that no integer solution could be found. Instead,
> the integer constraint is seemingly just ignored. Any explanation? The first
> few lines of output are below. Thanks.
> 
> lpx_simplex: original LP has 512 rows, 496 columns, 11334 non-zeros
> lpx_simplex: presolved LP has 454 rows, 467 columns, 11276 non-zeros
> lpx_adv_basis: size of triangular part = 454
>       0:   objval =   7.218422676e+00   infeas =   1.000000000e+00 (0)
>     200:   objval =   1.495206743e+04   infeas =   4.956196015e-02 (0)
>     400:   objval =   3.576502704e+04   infeas =   4.079243578e-03 (0)
>     432:   objval =   4.615788519e+04   infeas =   1.482525588e-17 (0)
> *   432:   objval =   4.615788519e+04   infeas =   4.796163466e-14 (0)
> *   600:   objval =   1.821209863e+03   infeas =   0.000000000e+00 (0)
> *   800:   objval =   3.589917305e+02   infeas =   5.329070518e-15 (0)
> *   934:   objval =   4.076064312e+01   infeas =   7.371880884e-13 (0)
> OPTIMAL SOLUTION FOUND
> 
> P.S. Could someone please explain to me what infeas, the (sum of) primal
> infeasibilities, means?
> 
> Alan
> 

As Michael Hennebry says, it looks like GLPK doesn't realize that it is
a MIP.  It could be a bug in the glpkmex interface, though I don't see
anything obvious in the code.  What version of GLPK are you using and
can you share the code where you call the glpkmex solver function?

The sum of primal infeasibilities is a way of measuring the severity of
infeasibility.  When the simplex algorithm starts to solve an LP, often
the basic solution is infeasible.  Phase I of the algorithm attempts to
find a feasible solution.  Each violated inequality is violated by some
amount, and the sum of these amounts gives a sense of how "close" the
solution is to feasibility.  Once the solution is feasible, the
algorithm enters phase II and looks for the optimal solution.  GLPK puts
a "*" in the left column once it is in phase II.  Notice that the
infeasibility is essentially zero from that point on in your output (the
imprecision of floating-point arithmetic means that it often won't be
precisely zero).  It's not related to solving integer programs.

Brady