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

  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.


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.