2
$\begingroup$

I have a family of equations I want to solve over the non-negative integers. One particular instance of it is this.

A = {{1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0}, 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1}}

b = {1, 2, 3, 1, 2, 2, 0, 1, 1, 0, 0, 0, 0, 0, 0}

I'd like to solve the problem $$ A.x = b,\quad x \in \mathbb{N}^{22} $$ So I call up LinearProgramming and ask

LinearProgramming[ Table[0, {22}], A, {#,0}& /@ b, 
                   Table[{0,Infinity}, {22}],Table[ Integers, {22}]]

The purported solution is

c = {1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

which is not, actually, a solution of the problem.

Why does this happen? Why doesn't Mathematica tell me that there is no solution?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Looks like a bug. Will investigate.. $\endgroup$ – Daniel Lichtblau Oct 28 '13 at 15:08
3
$\begingroup$

This bug has been fixed in the recently released version 12.0

LinearProgramming[Table[0,{22}], A, {#, 0}& /@ b,                                                       
       Table[{0, Infinity}, {22}],Table[Integers,{22}]] // Head

LinearProgramming::lpip: Warning: integer linear programming will use a machine-precision approximation of the inputs.

LinearProgramming::lpsnf: No solution can be found that satisfies the constraints.

(* LinearProgramming *)
Improve this answer
$\endgroup$
  • $\begingroup$ That fixed earlier, at least in version 11.3. $\endgroup$ – user64494 Apr 17 '19 at 6:21
  • $\begingroup$ Not exactly, it also depended on the operating system. $\endgroup$ – ilian Apr 17 '19 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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