[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Are my integer constraints being ignored?
From: |
Alan Larkin |
Subject: |
Re: [Help-glpk] Are my integer constraints being ignored? |
Date: |
Sun, 23 May 2004 14:21:36 +0100 |
----- 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.