Dear John,
On Oct 8, 10:01 pm, John H Palmieri <[EMAIL PROTECTED]> wrote:
...
> This may be a silly question, but integer linear programming seems to
> be about maximizing some quantity relative to constraints given by a
> matrix equality (or inequality), where everything is happening over
> the integers. How does this relate to finding integer solutions to a
> matrix equation?
Certainly I am not expert for ILP, but I did some applications of ILP
in 3-dimensional topology. And in that application, ILP always was
about finding non-negative integer solutions of a linear system of
equalities with integer coefficients.
So, nothing about "maximizing".
Actually this is a major building block for Wolfgang Haken's theory of
normal surfaces, and thus for certain classification algorithms for a
large class of closed 3-manifolds.
> I find myself wanting to do something similar: find *all* solutions to
> Ax = b, where A, x, and b have non-negative integer entries. I'm
> trying to figure out if the various responses here will help me. In
> the situation of interest to me, I know that there are only finitely
> many solutions, and I know one solution.
In the above-mentioned application, you would have b=0, and then there
are *finitely* many non-neg integer solutions ("fundamental"
solutions) that additively generate all non-neg integer solutions. And
IIRC, for finding the fundamental solutions, you need to detect the
smallest integer points on the edges of the cone of non-negative
solutions to the equation - so, this indeed involves optimisation.
However, it seems that the problem you are interested in is classical
as well, and therefore I suspect you find a solution in
A. Schrijver:
Theory of linear and integer programming.
Wiley-Interscience, Chichester 1986.
Given the various applications, it would be great to have high-
performance ILP in Sage!
Yours
Simon
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
