wrong answer from MixedIntegerLinearProgram(solver = "PPL")

[Daniel Friedan]

The following example from Sage Reference v5.6 >> Numerical Optimization >> Mixed integer linear programming
      http://www.sagemath.org/doc/reference/sage/numerical/mip.html
gives a wrong answer when solver = 'PPL' is used.  The equality constraints are violated.

Sage 5.6-OSX-64bit-10.6 under OS X 10.6.8

sage: p = MixedIntegerLinearProgram(maximization=False, solver = "PPL")
sage: print p.base_ring()
sage: w = p.new_variable()
sage: p.add_constraint(w[0] + w[1] + w[2] - 14*w[3] == 0)
sage: p.add_constraint(w[1] + 2*w[2] - 8*w[3] == 0)
sage: p.add_constraint(2*w[2] - 3*w[3] == 0)
sage: p.add_constraint(w[0] - w[1] - w[2] >= 0)
sage: p.add_constraint(w[3] >= 1)
sage: _ = [ p.set_min(w[i], None) for i in range(1,4) ]
sage: p.set_objective(w[3])
sage: p.show()
sage: print 'Objective Value:', p.solve()
sage: for i, v in p.get_values(w).iteritems():\
sage:          print 'w_%s = %s' % (i, int(round(v)))

Rational Field
Minimization:
  x_3
Constraints:
  constraint_0: 0 <= x_0 + x_1 + x_2 - 14 x_3 <= 0
  constraint_1: 0 <= x_1 + 2 x_2 - 8 x_3 <= 0
  constraint_2: 0 <= 2 x_2 - 3 x_3 <= 0
  constraint_3: - x_0 + x_1 + x_2 <= 0
  constraint_4: - x_3 <= -1
Variables:
  x_0 is a continuous variable (min=0, max=+oo)
  x_1 is a continuous variable (min=-oo, max=+oo)
  x_2 is a continuous variable (min=-oo, max=+oo)
  x_3 is a continuous variable (min=-oo, max=+oo)
Objective Value: 1
w_0 = 8
w_1 = 5
w_2 = 2
w_3 = 1

[Dima Pasechnik]

On 2013-01-29, Daniel Friedan <dfri...@gmail.com> wrote:
> ------=_Part_964_12292304.1359472365223
> Content-Type: text/plain; charset=ISO-8859-1

>
> The following example from Sage Reference v5.6 >> Numerical Optimization >>
> Mixed integer linear programming
> http://www.sagemath.org/doc/reference/sage/numerical/mip.html
> gives a wrong answer when solver = 'PPL' is used. The equality constraints
> are violated.

No, they are not. Note that you round the output,
which need not be integer.

If in the last line you do
print 'w_%s = %s' % (i, v)
you get

w_0 = 15/2
w_1 = 5
w_2 = 3/2
w_3 = 1

which is OK.

The original example does integer LP, by the way (and PPL can't so it).
So it's OK to round in this case, but not for an ordinary LP...

Best,
Dmitrii

[Daniel Friedan]

Thanks.  Sorry for the dumb posting.

Daniel

[dfri...@gmail.com]

Dmitrii,

Thanks very much. Sorry for the dumb posting. I should have mentioned
in my posting that I'm just getting into MILP in Sage.

Would it be equally dumb to post a question asking if there is an
arbitrary precision real arithmetic solver for MILP in Sage? (maybe a
version of GLPK?) Google just gives some old pages on the topic.

regards,
Daniel

[Dima Pasechnik]

On 2013-01-29, dfri...@gmail.com <dfri...@gmail.com> wrote:
> Dmitrii,
>
> Thanks very much. Sorry for the dumb posting. I should have mentioned
> in my posting that I'm just getting into MILP in Sage.
>
> Would it be equally dumb to post a question asking if there is an
> arbitrary precision real arithmetic solver for MILP in Sage? (maybe a
> version of GLPK?) Google just gives some old pages on the topic.

it appears that GLPK has such a functionality (never tried it, nor even
read docs :-)); someone has to integrate it in Sage...
Should not be too much work, as GLPK is already (mostly) integrated.

There are ways of dealing with low-dimensional ILP problems in Sage,
involving enumerating all the integer points in the polytope.

MILP is typically hard. If a normal precision MILP never produces
an answer, typically arbirary precision won't help, either.

Only for some really "bad" data an arbitrary precision MILP would be
useful, although I actually saw such data working on bounds of quantum codes
recently.

Best,
Dmitrii

[Daniel Friedan]

First, I'll try my MILP problems in double-precision (probably using CPLEX).  I'll re-post my question about arbitrary precision if it turns out that I need it.

We definitely needed arbitrary precision when we did some related problems using semi-definite programming (over the real numbers -- without the integrality constraints).  To use arbitrary precision floating point arithmetic, we had to employ SDPA-GMP as our SDP-solver, invoking it from Sage via a shell script.

Thanks again for the help.

Daniel

[Dima Pasechnik]

On 2013-01-31, Daniel Friedan <dfri...@gmail.com> wrote:
> ------=_Part_880_30796308.1359641848689
> Content-Type: text/plain; charset=ISO-8859-1

>
> First, I'll try my MILP problems in double-precision (probably using
> CPLEX). I'll re-post my question about arbitrary precision if it turns out
> that I need it.

IMHO the main problem with MILPs is that it's pretty hard to get a
certificate of optimality (much easier with LPs/SDPs).
Commercial solvers don't do them, free
solvers don't do them either, AFAIK.
(that's OK if you just want to use the solution obtained, but
claiming anything about optimality is a different matter)

>
> We definitely needed arbitrary precision when we did some related problems
> using semi-definite programming (over the real numbers -- without the
> integrality constraints). To use arbitrary precision floating point
> arithmetic, we had to employ SDPA-GMP as our SDP-solver, invoking it from
> Sage via a shell script.

SDPs are known to be much more demanding in this sense, and for good
geometric/algebraic reasons too.

Best,
Dmitrii