not too hard mixed integer linear program that both PPL and GLPK fail to solve

[Vincent Delecroix]

Dear all,

I have a 7 variables 3 constraints linear program that I want to solve
with integers

x = M.new_variable(integer=True, nonnegative=True)
M.add_constraint(x[0] - x[1] + x[2] - x[3] - x[4] - 2 * x[6] == 2)
M.add_constraint(x[0] - x[1] + x[2] - 2 * x[4] - x[5] - x[6] == 2)
M.add_constraint(2 * x[0] - x[3] - x[4] - x[5] - x[6] == -1)

However, with both

M = MixedIntegerLinearProgram(solver="PPL")

and

M = MixedIntegerLinearProgram(solver="GLPK")

The command M.solve() does not terminate in reasonable time... I do
not expect the system to have solutions, but I would like a proof of
it.

One subtlety of the system is that there are (infinitely many)
positive integral solutions of the homogeneous version (ie linear
combination == 0). I wondered if that was the reason why it is harder
for a solver.

If anyone knows of an alternative way to provide an open source
computer assisted proof that there is no solution I would be
interested.

Best
Vincent

[Dima Pasechnik]

It should be possible to construct the polyhedron determined by the feasible set of the LP, triangulate it, and do simplex by simplex or perhaps use various results relating volumes and presence of integral points in polyhedra.

--
You received this message because you are subscribed to the Google Groups "sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/sage-support/CAGEwAAnr71Pi7151VHkQ0OCCYrXVhXgjc9zt5s5V3jezE%2BdUqQ%40mail.gmail.com.

[Dima Pasechnik]

PS. You also have not set an objective function, not sure, but it could be why you have no termination 

[Vincent Delecroix]

Note that for triangulating, sage does not help

sage: M.polyhedron().triangulate()
Traceback (most recent call last):
...
NotImplementedError: triangulation of non-compact polyhedra that are
not cones is not supported

> To view this discussion visit https://groups.google.com/d/msgid/sage-support/CAAWYfq2UvmPYJmuqHN5xRDctY2dHtOkr1k-3ymgEPw0Y1gz3Tw%40mail.gmail.com.

[Vincent Delecroix]

Also M.set_objective(-x[0]) or M.set_objective(-x[0] - x[1] - x[2] -
x[3] - x[4] - x[5] - x[6]) do not seem to change anything. It seems
reasonable that this does not help the solver since we want to prove
here that there is no solution.


Curiously, there is a bug while setting M.set_objective(x[0]) with
solver="GLPK", namely

sage: M.solve()

Traceback (most recent call last):
...

MIPSolverException: GLPK: The LP (relaxation) problem has no dual
feasible solution

which is somehow irrelevant for the primal problem over the integers.

On Wed, 21 May 2025 at 19:51, Vincent Delecroix

[Dima Pasechnik]

I forgot - does Sage do the Minkowski decomposition into compact and non-compact parts (so you do have a ray in your polyhedron)

Is it even possible to define over Q a non-compact polyhedron without integer points?

(sorry, my geometry of numbers knowledge is pretty bad)

To view this discussion visit https://groups.google.com/d/msgid/sage-support/CAGEwAAnnaXtQ8TarBkB2nd0Miw%3DsDOJUoJvW3pBpL_xc3_ENmA%40mail.gmail.com.

[Vincent Delecroix]

Sure: take x0=1/2.

> To view this discussion visit https://groups.google.com/d/msgid/sage-support/CAAWYfq2RLtrgsBy55UHA0V6r5iZhM3Z5agmhRe9pmNjJ-h5b%3DA%40mail.gmail.com.

[Vincent Delecroix]

Actually, in my case one can just rely on the Smith normal form (I
wonder why PPL/GLPK do not try that first). More precisely, one can
consider the lattice in Z^3 given by the triples of values of my
equations

(x[0] - x[1] + x[2] - x[3] - x[4] - 2 * x[6],
x[0] - x[1] + x[2] - 2 * x[4] - x[5] - x[6],
2 * x[0] - x[3] - x[4] - x[5] - x[6])

where x is in Z^7. One obtains that the lattice is equal to the
vectors in Z^3 with even sum of coordinates (ie generated by (0,1,1),
(1,0,1), (1,1,0)). The lattice does not contain the particular
solution (2, 2, -1) I am looking for.

On Wed, 21 May 2025 at 20:23, Vincent Delecroix

[Vincent Delecroix]

It seems to me that problems of the form

xA = b
x >= 0
x integral

can always be solved this way. Namely use Smith normal form to find a
particular integral solution x0 of the linear equation xA = b. Then
see if one can translate along the rays of {xA = 0, x >= 0} to
transform this particular solution to a non-negative one.

On Wed, 21 May 2025 at 20:40, Vincent Delecroix