3
$\begingroup$

The following code produces the error message "The following constraints are not valid". However, if I add the additional constraint "diam <= 3" (commented out below), it runs correctly and finds a solution in 3 seconds. Why is it not able to find such a solution without this extra constraint? (It also runs correctly if I remove any constraint, hence why I couldn't provide a shorter example.)

Clear["Global`*"]

n = 9;
r = 6;

(*allow writing d[i,j] and w[i,j,l] to refer to variable dij and wijl*)
d[i_, j_] := ToExpression["d" ~~ ToString@Row@Sort[{i, j}]];
w[i_, j_, l_] := ToExpression["w" ~~ ToString@Row@Sort[{i, j, l}]];


vars := Flatten@Join[
    Table[d[i, j], {i, n - 1}, {j, i + 1, n}],
    Table[w[i, j, l], {i, n - 2}, {j, i + 1, n - 1}, {l, j + 1, n}],
    Table[
     m3[i, j], {i, DeleteCases[Range[1, n], r]}, {j, 
      DeleteCases[Range[1, n], r | i]}],
    Table[m2[i], {i, DeleteCases[Range[1, n], r]}],
    {m1, phi, phiAlt, diam, diff} 
    ];


NMinimize[{diam,
  Table[
   d[i, j] <= d[i, l] + d[j, l] &&
    d[i, l] <= d[i, j] + d[j, l] &&
        d[j, l] <= d[i, j] + d[i, l],
   {i, 1, n - 2}, {j, i + 1, n - 1}, {l, j + 1, n}],

  Table[
   -d[i, j] <= w[i, l, m] - w[j, l, m] <= d[i, j] &&
    -d[i, l] <= 
     w[i, j, m] - w[l, j, m] <= d[i, l] &&
    -d[i, m] <= 
     w[i, j, l] - w[m, j, l] <= d[i, m] &&
    -d[j, l] <= 
     w[j, i, m] - w[l, i, m] <= d[j, l] &&
    -d[j, m] <= 
     w[j, i, l] - w[m, i, l] <= d[j, m] &&
    -d[l, m] <= 
     w[l, i, j] - w[m, i, j] <= d[l, m],
   {i, 1, n - 3},
   {j, i + 1, n - 2},
   {l, j + 1, n - 1},
   {m, l + 1, n}
   ],

  Table[m3[p3, p2] <= w[p2, j, r] - d[j, p3],
   {p3, DeleteCases[Range[1, n], r]},
   {p2, DeleteCases[Range[1, n], r | p3]},
   {j, DeleteCases[Range[1, n], r | p3 | p2]}
   ],
  Table[m2[p2] <= w[j, l, r] - d[j, p2] - d[l, p2],
   {j, DeleteCases[Range[1, n - 1], r]},
   {l, DeleteCases[Range[j + 1, n], r]},
   {p2, DeleteCases[Range[1, n], j | l | r]}
   ],
  Table[m1 <= w[j, l, r] - d[j, r] - d[l, r],
   {j, DeleteCases[Range[1, n - 1], r]},
   {l, DeleteCases[Range[j + 1, n], r]}
   ],
  Table[phiAlt <= w[p3, p2, r] + m3[p3, p2] + m2[p2] + m1,
   {p3, DeleteCases[Range[1, n], r]},
   {p2, DeleteCases[Range[1, n], r | p3]}
   ],

  Table[w[i, j, l] >= 0, {i, n - 2}, {j, i + 1, n - 1}, {l, j + 1, n}],
  Table[0 <= d[i, j] <= diam, {i, n - 1}, {j, i + 1, n}],
  Table[d[i, j] \[Element] Integers, {i, n - 1}, {j, i + 1, n}],
  Table[w[i, j, l] \[Element] Integers, {i, n - 2}, {j, i + 1, 
    n - 1}, {l, j + 1, n}],

  phi == w789 + w589 - d57 + w349 - d38 - d48 + w126 - d19 - d29 - d69,
  diff <= phiAlt - phi,
  d13 == 0,
  d13 + d59 <= d15 + d39 == d19 + d35,
  d13 + d68 <= d16 + d38 == d18 + d36,
  d13 + d69 <= d16 + d39 == d19 + d36,
  d13 + d78 <= d17 + d38 == d18 + d37,
  d13 + d89 <= d18 + d39 == d19 + d38,
  d24 + d68 <= d26 + d48 == d28 + d46,
  d24 + d69 <= d26 + d49 == d29 + d46,
  d24 + d89 <= d28 + d49 == d29 + d48,
  d18 + d57 <= d15 + d78 == d17 + d58,
  w128 == w126 + d68,
  w129 == w126 + d69,
  w148 == w146 + d68,
  w149 == w146 + d69,
  w238 == w236 + d68,
  w239 == w236 + d69,
  w348 == w346 + d68,
  w349 == w346 + d69,
  w589 == w568 + d69,
  w789 == w679 + d68,
  w569 + w678 >= w567 + w689 == w568 + w679,
  (*diam <= 3,*)
  diff >= 0.5
  }, vars]

In the code, I'm defining the notation d[i_,j_] and w[i_,j_,l_] because in NMinimize, most constraints involving these variables are specified as Tables. Besides integrality constraints, all other constraints are linear and there are around 3000 constraints total.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.