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 <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/CAGEwAAmCHMKJV7sUyFcubxTcbwH-c%2ByJedJ7t57%3Dsa5ohP7nMA%40mail.gmail.com.
