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.
