0
$\begingroup$

I need to solve a bunch of Diophantine Equations that takes so looong with FindInstance/Reduce, so I tried LinearProgramming and it's very fast. Here is a simple one:

m = {
{1, 1, 1, 0, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 1, 1, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 1, 1},
{0, 0, 1, 0, 1, 0, 0, 0, 0, 1},
{1, 0, 0, 1, 0, 0, 1, 0, 0, 1},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0}
};
c = ConstantArray[1, 10];
b = {{247, 0}, {260, 0}, {117, 0}, {208, 0}, {325, 0}, {234, 0}, {377, 0}, {364, 0}, {442, 0}, {130, 0}};
LinearProgramming[c, m, b, 1, Integers]

BUT, I have a constraint on the result: all values in result vector x must be distinct.

Then I thought I could add many lines on my matrix like this

{1, -1, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 0, -1, 0, 0, 0, 0, 0, 0, 0},
...

Stating that x0-x1 >= 1, then x0-x2 >=1 (and thus are distinct) but it's possible that x1>x0. And if I write

{1, -1, 0, 0, 0, 0, 0, 0, 0, 0},
{-1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 0, -1, 0, 0, 0, 0, 0, 0, 0},
{-1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
...

Then I ask for x0-x1 >= 1 AND x1-x0 >= 1 that is impossible... The documentation states linear constraints are specified by the matrix m and the pairs {bi,si}. For each row mi of m, the corresponding constraint is mi.x≥bi if si==1, or mi.x==bi if si==0, or mi.x≤bi if si==-1. but nothing for mi.x!=bi...

Any idea on how to manage that ?

$\endgroup$
  • 1
    $\begingroup$ You are trying to enforce an "either-or" constraint of the form x<=-1 || x>= 1.There is a standard way to do this using a new 0-1 variable and two inequality constraints relating it to x. This requires also knowing in advance a maximum value for x (which in this case is the largest difference between any pair of solution values). $\endgroup$ – Daniel Lichtblau Oct 24 '19 at 17:37

Your Answer

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

Browse other questions tagged or ask your own question.