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 <20100.delecr...@gmail.com> wrote: > > Sure: take x0=1/2. > > On Wed, 21 May 2025 at 20:20, Dima Pasechnik <dimp...@gmail.com> wrote: > > > > 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) > > > > > > > > On Wed, May 21, 2025, 12:52 Vincent Delecroix <20100.delecr...@gmail.com> > > wrote: > >> > >> 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 > >> > >> On Wed, 21 May 2025 at 18:39, Dima Pasechnik <dimp...@gmail.com> wrote: > >> > > >> > PS. You also have not set an objective function, not sure, but it could > >> > be why you have no termination > >> > > >> > On Wed, May 21, 2025, 11:37 Dima Pasechnik <dimp...@gmail.com> wrote: > >> >> > >> >> 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. > >> >> > >> >> On Wed, May 21, 2025, 11:27 Vincent Delecroix > >> >> <20100.delecr...@gmail.com> wrote: > >> >>> > >> >>> 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 > >> >>> > >> >>> -- > >> >>> 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+unsubscr...@googlegroups.com. > >> >>> To view this discussion visit > >> >>> https://groups.google.com/d/msgid/sage-support/CAGEwAAnr71Pi7151VHkQ0OCCYrXVhXgjc9zt5s5V3jezE%2BdUqQ%40mail.gmail.com. > >> > > >> > -- > >> > 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+unsubscr...@googlegroups.com. > >> > To view this discussion visit > >> > https://groups.google.com/d/msgid/sage-support/CAAWYfq2UvmPYJmuqHN5xRDctY2dHtOkr1k-3ymgEPw0Y1gz3Tw%40mail.gmail.com. > >> > >> -- > >> 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+unsubscr...@googlegroups.com. > >> To view this discussion visit > >> https://groups.google.com/d/msgid/sage-support/CAGEwAAnnaXtQ8TarBkB2nd0Miw%3DsDOJUoJvW3pBpL_xc3_ENmA%40mail.gmail.com. > > > > -- > > 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+unsubscr...@googlegroups.com. > > To view this discussion visit > > https://groups.google.com/d/msgid/sage-support/CAAWYfq2RLtrgsBy55UHA0V6r5iZhM3Z5agmhRe9pmNjJ-h5b%3DA%40mail.gmail.com. -- 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+unsubscr...@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/sage-support/CAGEwAAk3DTKqvKU7VxULxrxU0LYQ9oyoL9ymdfwqLEYdLsRgXA%40mail.gmail.com.
