3
$\begingroup$

I need to find a solution (all solutions, or at least upper and lower bounds) in positive integer numbers to the system $Ax \ge f$, where $A$ is an integer matrix.

With SageMath, I solved it with the function

Polyhedron.integral_points()

But, this is very slow and can take about 2-3 hours for a matrix which is about $30 \times 10$.

Is there another, faster way to do this? Preferably with SageMath or Python.

$\endgroup$

2 Answers 2

2
$\begingroup$

Essentially this is an integer linear programming problem (e.g. for finding bounds on a variable, your objective could be to maximize or minimize that variable). Although integer linear programming is NP-complete, there is well-developed software for this which should be quite fast for a problem the size you mentioned. In SageMath you can use the MILP class.

$\endgroup$
2
$\begingroup$

I suggest to employ Normaliz backend in SageMath, which is very efficient. Also, if there are infinitely many solutions, it's worth to compute integral_points_generators() rather than integral_points() -- the latter is limited to 10,000 points by default.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.