Myths in mathematical programming

The INFORMS Computing Society has a collection of myths and counterexamples in math programming by Harvey Greenberg. Here’s one of the IP myths:

IP Myth 21. Determining if Ax=b has an integer solution is NP-complete for integral A, b.

My thanks to Heiko Vogel for pointing this out. The key to this myth is that there are no bounds on x. (If we restrict x to be nonnegative, 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. Also, see Aardal, Hurkens, and Lenstra.

I’d like to add that this problem might be NP-complete. However, this would imply that P=NP, so it’s not very likely.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s