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

[Alan Larkin]

----- Original Message ----- 
From: "Brady Hunsaker" <address@hidden>
To: <address@hidden>
Sent: Saturday, May 22, 2004 3:56 AM
Subject: Re: [Help-glpk] Are my integer constraints being ignored?


> 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
>
>
>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://mail.gnu.org/mailman/listinfo/help-glpk
>
>

Sorry, I should have followed this up.

It was a stupid stupid bug in the programmer. Invoking glpkmex incorrectly.
Nobodys fault but mine.

Thanks for the explanation.

Alan.