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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .