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
<[email protected]> wrote:
>
> 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
> <[email protected]> wrote:
> >
> > Sure: take x0=1/2.
> >
> > On Wed, 21 May 2025 at 20:20, Dima Pasechnik <[email protected]> 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 <[email protected]>
> > > 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 <[email protected]> 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 <[email protected]> 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
> > >> >> <[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/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 [email protected].
> > >> 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 [email protected].
> > > 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 [email protected].
To view this discussion visit
https://groups.google.com/d/msgid/sage-support/CAGEwAA%3DZ8HpWegpfZhj2jHj0vj3vmLRPmin8tOnqEuNdSBJT2w%40mail.gmail.com.
