3
$\begingroup$

I need to get a rational solution of the linear constraints p={1-49 Subscript[a15, 56]-Subscript[a4, 1]==0,-1+140 Subscript[a15, 56]-Subscript[a4, 2]==0,-100 Subscript[a15, 56]+2 Subscript[a4, 1]-Subscript[a4, 4]==0,-13 Subscript[a30, 16]-Subscript[a4, 7]+2 Subscript[a4, 16]-Subscript[a4, 29]==0,-49 Subscript[a15, 56]+4 Subscript[a21, 3]-Subscript[a30, 37]-Subscript[a4, 1]+2 Subscript[a4, 3]-Subscript[a4, 37]==0,-Subscript[a27, 37]+6 Subscript[a30, 16]-4 Subscript[a30, 37]-Subscript[a4, 11]+2 Subscript[a4, 22]-Subscript[a4, 37]==0,-Subscript[a27, 37]-13 Subscript[a30, 37]-Subscript[a4, 22]+2 Subscript[a4, 37]==0,-Subscript[a1, 3]+2 Subscript[a1, 5]+4 Subscript[a12, 55]+200 Subscript[a15, 56]-4 Subscript[a21, 3]-2 Subscript[a4, 1]-2 Subscript[a4, 2]+2 Subscript[a4, 3]+2 Subscript[a4, 4]-Subscript[a4, 8]-Subscript[a4, 46]==0,2 Subscript[a27, 37]-Subscript[a30, 16]+12 Subscript[a30, 37]-Subscript[a4, 16]+2 Subscript[a4, 29]-Subscript[a4, 46]==0,-Subscript[a21, 3]+6 Subscript[a30, 37]-Subscript[a4, 3]-Subscript[a4, 29]+2 Subscript[a4, 46]==0,-Subscript[a12, 55]+2 Subscript[a4, 2]-Subscript[a4, 7]-Subscript[a4, 59]==0,-Subscript[a12, 55]-8 Subscript[a27, 37]+2 Subscript[a4, 22]-2 Subscript[a4, 29]-2 Subscript[a4, 37]+2 Subscript[a4, 46]+4 Subscript[a41, 5]==0,-Subscript[a1, 3]+98 Subscript[a15, 56]-4 Subscript[a21, 3]+2 Subscript[a4, 1]-Subscript[a4, 3]-Subscript[a4, 46]-Subscript[a42, 3]==0,2 Subscript[a12, 55]-100 Subscript[a15, 56]+4 Subscript[a21, 3]-4 Subscript[a27, 37]-Subscript[a4, 1]+2 Subscript[a4, 2]-2 Subscript[a4, 3]-Subscript[a4, 4]-2 Subscript[a4, 5]+2 Subscript[a4, 8]-Subscript[a4, 37]+2 Subscript[a4, 46]-2 Subscript[a46, 5]==0,2 Subscript[a1, 3]-Subscript[a1, 5]-280 Subscript[a15, 56]+8 Subscript[a21, 3]-2 Subscript[a4, 1]+2 Subscript[a4, 2]-Subscript[a4, 5]+2 Subscript[a4, 46]-Subscript[a46, 5]==0,-4 Subscript[a12, 55]+140 Subscript[a15, 56]-8 Subscript[a21, 3]+2 Subscript[a4, 1]-Subscript[a4, 2]-2 Subscript[a4, 3]+2 Subscript[a4, 5]+2 Subscript[a4, 37]-2 Subscript[a4, 46]+2 Subscript[a42, 3]+4 Subscript[a46, 5]==0,-Subscript[a4, 7]+2 Subscript[a4, 8]+2 Subscript[a4, 11]-2 Subscript[a4, 12]-Subscript[a4, 16]-2 Subscript[a4, 17]+2 Subscript[a4, 27]-Subscript[a4, 59]+4 Subscript[a47, 24]==0,-Subscript[a1, 5]-6 Subscript[a12, 55]+2 Subscript[a4, 1]-2 Subscript[a4, 2]-2 Subscript[a4, 4]+2 Subscript[a4, 5]+2 Subscript[a4, 7]-Subscript[a4, 12]-Subscript[a51, 20]==0,-2 Subscript[a12, 55]-Subscript[a21, 3]+8 Subscript[a27, 37]-Subscript[a4, 3]+2 Subscript[a4, 5]-Subscript[a4, 8]-Subscript[a4, 19]-Subscript[a4, 29]+2 Subscript[a4, 30]+2 Subscript[a4, 37]-Subscript[a4, 46]-Subscript[a42, 3]+4 Subscript[a46, 5]+2 Subscript[a51, 20]==0,-Subscript[a4, 5]+2 Subscript[a4, 8]-Subscript[a4, 12]-Subscript[a4, 30]-Subscript[a46, 5]+4 Subscript[a51, 20]==0,-Subscript[a4, 4]+2 Subscript[a4, 5]+2 Subscript[a4, 7]-2 Subscript[a4, 8]-Subscript[a4, 11]-2 Subscript[a4, 12]+2 Subscript[a4, 17]-Subscript[a4, 24]-2 Subscript[a4, 59]+2 Subscript[a41, 5]-4 Subscript[a47, 24]-2 Subscript[a51, 20]-5 Subscript[a51, 24]==0,-13 Subscript[a30, 17]+2 Subscript[a4, 7]-Subscript[a4, 8]-2 Subscript[a4, 11]-2 Subscript[a4, 16]+2 Subscript[a4, 17]+2 Subscript[a4, 22]-Subscript[a4, 27]-Subscript[a4, 30]-Subscript[a51, 20]-2 Subscript[a51, 24]==0,12 Subscript[a30, 16]-Subscript[a4, 4]+2 Subscript[a4, 11]-Subscript[a4, 22]-Subscript[a51, 24]==0,2 Subscript[a12, 55]-Subscript[a4, 1]+2 Subscript[a4, 4]-Subscript[a4, 11]+2 Subscript[a4, 59]-Subscript[a51, 24]==0,-Subscript[a12, 55]-4 Subscript[a30, 16]-Subscript[a4, 2]+2 Subscript[a4, 7]-Subscript[a4, 16]-Subscript[a4, 59]+2 Subscript[a51, 24]==0,2 Subscript[a12, 55]-4 Subscript[a30, 17]+2 Subscript[a4, 2]-Subscript[a4, 3]-2 Subscript[a4, 4]-2 Subscript[a4, 7]+2 Subscript[a4, 8]+2 Subscript[a4, 11]-Subscript[a4, 17]-2 Subscript[a4, 59]-2 Subscript[a51, 20]+2 Subscript[a51, 24]==0,6 Subscript[a30, 17]+2 Subscript[a4, 11]-Subscript[a4, 12]-2 Subscript[a4, 16]-2 Subscript[a4, 22]+2 Subscript[a4, 27]+2 Subscript[a4, 29]-Subscript[a41, 5]+2 Subscript[a51, 20]+2 Subscript[a51, 24]==0,-Subscript[a4, 11]+2 Subscript[a4, 12]+2 Subscript[a4, 16]-2 Subscript[a4, 17]-Subscript[a4, 22]+2 Subscript[a4, 24]-2 Subscript[a4, 27]+2 Subscript[a4, 30]+4 Subscript[a41, 5]-Subscript[a47, 24]+4 Subscript[a51, 20]+3 Subscript[a51, 24]-2 Subscript[a9, 17]==0,4 Subscript[a27, 37]-Subscript[a30, 17]+2 Subscript[a4, 16]-Subscript[a4, 17]-2 Subscript[a4, 22]-Subscript[a4, 27]-2 Subscript[a4, 29]+2 Subscript[a4, 30]+2 Subscript[a4, 37]-4 Subscript[a41, 5]-Subscript[a51, 20]-Subscript[a9, 17]==0,-4 Subscript[a28, 19]-Subscript[a4, 16]+2 Subscript[a4, 17]-Subscript[a4, 19]+2 Subscript[a4, 22]-Subscript[a4, 29]-2 Subscript[a4, 30]+2 Subscript[a41, 5]-2 Subscript[a51, 20]-2 Subscript[a51, 24]-4 Subscript[a9, 25]==0,Subscript[a4, 19]+2 Subscript[a4, 24]-Subscript[a4, 27]+2 Subscript[a41, 5]-Subscript[a51, 20]+2 Subscript[a51, 24]+4 Subscript[a9, 17]-2 Subscript[a9, 25]==0,4 Subscript[a28, 19]-2 Subscript[a4, 19]+2 Subscript[a4, 24]+2 Subscript[a4, 30]-Subscript[a4, 59]-Subscript[a51, 20]-2 Subscript[a51, 24]+4 Subscript[a9, 17]-Subscript[a9, 25]==0,-8 Subscript[a28, 19]-2 Subscript[a4, 19]-2 Subscript[a4, 24]+2 Subscript[a4, 27]-Subscript[a47, 24]-2 Subscript[a51, 20]+4 Subscript[a9, 25]==0,2 Subscript[a28, 19]-Subscript[a4, 12]+2 Subscript[a4, 17]-2 Subscript[a4, 24]-2 Subscript[a4, 27]+4 Subscript[a47, 24]+3 Subscript[a51, 20]+4 Subscript[a51, 24]-4 Subscript[a9, 17]+4 Subscript[a9, 25]==0,4 Subscript[a12, 55]+2 Subscript[a21, 3]+4 Subscript[a27, 37]+2 Subscript[a4, 3]-Subscript[a4, 5]+2 Subscript[a4, 29]-Subscript[a4, 30]-2 Subscript[a4, 37]-2 Subscript[a4, 46]-Subscript[a41, 5]-4 Subscript[a46, 5]-4 Subscript[a9, 35]==0,-Subscript[a28, 19]-Subscript[a4, 8]+2 Subscript[a4, 12]-Subscript[a4, 17]+2 Subscript[a4, 19]+2 Subscript[a4, 24]-Subscript[a4, 27]+2 Subscript[a4, 59]-5 Subscript[a41, 5]+4 Subscript[a51, 20]-Subscript[a9, 17]-2 Subscript[a9, 35]==0,12 Subscript[a30, 17]+2 Subscript[a4, 4]-Subscript[a4, 5]-2 Subscript[a4, 7]-2 Subscript[a4, 11]+2 Subscript[a4, 12]+2 Subscript[a4, 16]+2 Subscript[a4, 59]-Subscript[a51, 20]-2 Subscript[a51, 24]-Subscript[a9, 35]==0,7 Subscript[a28, 19]-Subscript[a4, 17]+Subscript[a4, 19]-2 Subscript[a4, 24]+2 Subscript[a4, 27]-Subscript[a4, 30]-Subscript[a41, 5]-2 Subscript[a47, 24]-3 Subscript[a51, 20]-Subscript[a9, 25]-Subscript[a9, 35]==0,-4 Subscript[a27, 37]+2 Subscript[a4, 19]-Subscript[a4, 22]-Subscript[a4, 24]+2 Subscript[a4, 29]-2 Subscript[a4, 30]-Subscript[a4, 37]-2 Subscript[a41, 5]-2 Subscript[a51, 20]-2 Subscript[a51, 24]+4 Subscript[a9, 35]==0,Subscript[a12, 55]-Subscript[a4, 2]+2 Subscript[a4, 3]+2 Subscript[a4, 4]-2 Subscript[a4, 5]-Subscript[a4, 7]-2 Subscript[a4, 8]+2 Subscript[a4, 12]+2 Subscript[a4, 59]+2 Subscript[a51, 24]+4 Subscript[a9, 35]==0,Subscript[a1, 3]>=0,Subscript[a1, 5]>=0,Subscript[a12, 55]>=0,Subscript[a15, 56]>=0,Subscript[a21, 3]>=0,Subscript[a27, 37]>=0,Subscript[a28, 19]>=0,Subscript[a30, 16]>=0,Subscript[a30, 17]>=0,Subscript[a30, 37]>=0,Subscript[a4, 1]>=0,Subscript[a4, 2]>=0,Subscript[a4, 3]>=0,Subscript[a4, 4]>=0,Subscript[a4, 5]>=0,Subscript[a4, 7]>=0,Subscript[a4, 8]>=0,Subscript[a4, 11]>=0,Subscript[a4, 12]>=0,Subscript[a4, 16]>=0,Subscript[a4, 17]>=0,Subscript[a4, 19]>=0,Subscript[a4, 22]>=0,Subscript[a4, 24]>=0,Subscript[a4, 27]>=0,Subscript[a4, 29]>=0,Subscript[a4, 30]>=0,Subscript[a4, 37]>=0,Subscript[a4, 46]>=0,Subscript[a4, 59]>=0,Subscript[a41, 5]>=0,Subscript[a42, 3]>=0,Subscript[a46, 5]>=0,Subscript[a47, 24]>=0,Subscript[a51, 20]>=0,Subscript[a51, 24]>=0,Subscript[a9, 17]>=0,Subscript[a9, 25]>=0,Subscript[a9, 35]>=0}

the variables are

vars={Subscript[a1, 3],Subscript[a1, 5],Subscript[a12, 55],Subscript[a15, 56],Subscript[a21, 3],Subscript[a27, 37],Subscript[a28, 19],Subscript[a30, 16],Subscript[a30, 17],Subscript[a30, 37],Subscript[a4, 1],Subscript[a4, 2],Subscript[a4, 3],Subscript[a4, 4],Subscript[a4, 5],Subscript[a4, 7],Subscript[a4, 8],Subscript[a4, 11],Subscript[a4, 12],Subscript[a4, 16],Subscript[a4, 17],Subscript[a4, 19],Subscript[a4, 22],Subscript[a4, 24],Subscript[a4, 27],Subscript[a4, 29],Subscript[a4, 30],Subscript[a4, 37],Subscript[a4, 46],Subscript[a4, 59],Subscript[a41, 5],Subscript[a42, 3],Subscript[a46, 5],Subscript[a47, 24],Subscript[a51, 20],Subscript[a51, 24],Subscript[a9, 17],Subscript[a9, 25],Subscript[a9, 35]}

now I need to get a rational solution of p. I tried FindInstance LinearOptimization and Minimize and different methods are different in speed. For example, use Minimize[Total[vars],p,vars]//AbsoluteTiming, it takes 0.401411 seconds and output an exact rational solution. Use FindInstance[p,vars], it takes 0.545074 seconds and output an exact rational solution, slower than the first method. Use LinearOptimization[Total[vars],p,vars,Method->"Simplex"], it takes 2.08624 seconds and output an exact rational solution, much slower than the first method. Use LinearOptimization[Total[vars],p,vars,Method->"CLP"], it takes only 0.0067805 seconds, much faster than all the methods, but the result is numerical. Is there any method to get an rational solution while as faster as possible? Thanks.

$\endgroup$
1
  • $\begingroup$ (nmin = NMinimize[{Total[vars], p}, vars, WorkingPrecision -> 100, AccuracyGoal -> 20, PrecisionGoal -> 20] // Rationalize[#, 0] &) // AbsoluteTiming yields the same result as Minimize and is abourt 5 times faster. $\endgroup$
    – Akku14
    May 8 at 14:13

1 Answer 1

12
$\begingroup$

Your problem is not a linear programming problem, but rather a linear system of equations. You have 40 equations for 39 variables and so the problem is over-determined, but luckily it is still solvable.

First, extract the coefficients of the problem into matrix/vector representation:

M = D[p[[;; 40, 1]], {vars}];
b = p[[;; 40, 1]] - M . vars;

Now $M$ is a $40\times39$ matrix and $b$ is a 40-vector; your problem can now be written as $M\cdot x+b=0$. We solve it with LinearSolve in a fraction of a millisecond:

x = LinearSolve[M, -b]; // RepeatedTiming // First
(*    0.000353668    *)

x
(*    {1783932837904341077/2780412442842475762,
       594136606591323051/1390206221421237881,
       147462186435643008/1390206221421237881,
       ...,
       294293138346748441/5560824885684951524}    *)

All coefficients in $x$ are nonnegative, so your constraints are satisfied:

p /. Thread[vars -> x]
(*    {True, True, True, True, True, True, True, True, True, True,
       True, True, True, True, True, True, True, True, True, True,
       ...
       True, True, True, True, True, True, True, True, True, True}    *)
$\endgroup$

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.