# Name for subclass of ILP without any inequality constraints (including constraints on x)

In "Myths and Counterexamples of Mathematical Programming" myth "IP Myth 21" says:

The problem of finding $$x\in \mathbb{Z}$$ such that $$Ax=b$$, where $$A\in\mathbb{Z}^{m\times n}$$ and $$b\in \mathbb{Z}^m$$, is NP-complete.

Which is incorrect (as all myths in this excellent resource are).

The key to this myth is that there are no bounds on $$x$$. (If we add $$x≥0$$, we have the standard form of a linear integer program, which is NP-complete.) This is the problem of solving linear diophantine equations for which Brown provides simple, polynomial-time algorithms

• Is there a name for this problem class in OR/Optimization?

• Is there a name for this problem class some linear equality constraints over $$\mathbb{R}$$ are added?

• Are you aware of any MILP solvers which find such subproblems and solve them using specialized routines?

• Are problems of the same form but with $$\min ||x||$$, $$\min c^Tx$$, $$\min \sum_i (c_i x_i)^2$$, $$\min x^T D x$$ or $$\min x^T D x + c^Tx$$ where D positive definite as objective still solvable in polynomial time?

## 1 Answer

1. https://en.m.wikipedia.org/wiki/Diophantine_equation
2. any milp solver can handle it, but maybe something like mathematica/mable has special algortihms or one can use the algorithm described by the wiki entry

4a) https://en.m.wikipedia.org/wiki/Lattice_problem 4b) is i think polytime, either the problem is unbounded, infeasible or all solutions are optimal.