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 <[email protected]> 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 [email protected]. > 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 [email protected]. To view this discussion visit https://groups.google.com/d/msgid/sage-support/CAAWYfq3Nu8mBnUd%2B1rk6ijarX_CfpZA4fmjZ3nY9wGGQ2%3Dc_Vg%40mail.gmail.com.
