How to Minimize a problem with a big number of variables?
Using a different approach: guess the sequence. Then the answer for 2019 returns the right result in 20 microseconds. However, it does not prove that the sequence is the actual answer.
sol = ParallelTable[{n, Minimize[{Sum[x[j], {j, 1, n}],
Table[x[j] + x[j + 1] >= j, {j, 1, n - 1}], x[n] + x[1] >= n},
Table[x[j], {j, 1, n}]]}, {n, 2, 50}];
f = FindSequenceFunction[sol[[All, 2, 1]]];
answer[n_] = f[n - 1];
(* 1/8 (-1)^(-1 + n) (-1 + 5 (-1)^(-1 + n) + 2 (-1)^(-1 + n) (-1 + n)) n *)
answer[2019]
(* 1019595 *)
NMinimize
calculates the case n==2019
mini[n_] :=NMinimize[{Sum[x[j], {j, 1, n}],Table[x[j] + x[j + 1] >= j, {j, 1, n - 1}], x[n] + x[1] >= n},Table[x[j], {j, 1, n}]][[1]]
mini[2019] // Rationalize // AbsoluteTiming
(*{0.118309, 1019595}*)
in .11 seconds
!
n = 2019;
c = Table[1, n];
m = SparseArray[{Band[{1, 1}] -> 1, Band[{1, 2}] -> 1, {n, 1} -> 1}, {n, n}];
b = Range[n];
LinearOptimization[N[c], {m, -b}, "PrimalMinimumValue"] // AbsoluteTiming // DecimalForm
(* {0.0275781, 1019595.} *)
Note that the use of N
to force machine precision is important, otherwise the result will be exact but much slower. For some reason, the slowdown becomes much more significant at n = 201
:
Exact Approximate
n = 200 0.35 s 0.002 s
n = 201 8.9 s 0.002 s
Using LinearProgramming
gives the same results (and has the same timing issue):
Total @ LinearProgramming[N[c], m, b, -∞] // AbsoluteTiming // DecimalForm
(* {0.0286999, 1019595.} *)
Note the -∞
, without it the constraint x ≥ 0
is added.