linprog cannot find solution

I am running linprog to solve a problem with only equality constraints. The problem formulation is correctly setup, but the solver returns "no feasible solution found". How do I get linprog to find a solution?

[Walter Roberson]

What evidence do you have that there is a solution ?

[John D'Errico]

It would be best if you provide the problem itself, so we can examine it. Then we could verify a solution does exist or not. Until then, we can only conjecture if a solution truly exists at all.

[Austin Brehm]

linprog(f,A,b,Aeq,beq,lb,ub)

f = 1x256 matrix containing decimal values less than 1

A = empty matrix

b = empty matrix

Aeq = 32x256 matrix containing decimal values

beq = 1x32 matrix containing values ranging from 500-2000

lb = 1x256 zero matrix

ub = zero matrix

[Walter Roberson]

should we just use rand to construct the matrices or will you attach them?

[John D'Errico]

Just telling us the shape of those matrices is not sufficient to tell us anything, since it is quite easy to construct such a set of matrices that has NO feasible solution. Would you like me to show you how? Or, you can give us the matrices, and we can show you if a solution can ever exist.

Answer 1

[Steven Lord]

By the way you described the lb and ub inputs, both your lower and upper bounds are 0. That means the only possible feasible solution is the zero vector. Can that vector possibly satisfy your equality constraints? Since beq is not also the zero vector, it cannot.

So linprog is correct when it states that the problem you specified has no feasible solution. It doesn't matter what f or Aeq contain.

If you change either the lower or upper bounds your problem may have a solution. If you do and linprog still reports no feasible solution we will likely need to see the specific values in Aeq, beq, lb, and ub in order to determine if that's correct.

[John D'Errico]

Good catch by Steve.

[Austin Brehm]

Results.xlsx shows the values for f, Aeq, and beq. Any ideas? Do the beq values need to be scaled down? Thank you for your help everyone, I really appreciate it.

[Austin Brehm]

Sorry, I made an error. ub is set to an empty matrix [ ], not a zeros matrix. lb is set to a zeros matrix. In other words, the lower bound is zero and the upper bound does not exist.

[Walter Roberson]

Setting up for future investigation:

t = readtable('Results.xlsx', 'readvariablenames', false);
f = t{1,2:end};
A = [];
b = [];
Aeq = t{5:end,2:end};
beq = t{3,2:33} .';
lb = zeros(1,256);
ub = [];
sol = linprog(f,A,b,Aeq,beq,lb,ub)

Answer 2

[John D'Errico]

I'll answer this a different way than did Walter, using different tools to answer the question at hand.

You have a linear system of equations as equality constraints.

Aeq*x = beq

Linear algebra shows us that Aeq is rank deficient.

size(Aeq)
ans =
    32   256
rank(Aeq)
ans =
    31

So it has 32 rows, but a numerical rank of only 31. When will a solution to such a problem exist? That is, does there exist a vector x such that Aeq*x== beq, despite the rank deficiency?

That can happen of course. In fact, it is entirely possible. Not here of course. Why not?

If a vector x existed such that this was possibly true, then it must be true that beq could be written as a linear combination of the columns of Aeq. That is, when you multiply Aeq*x, you form a linear combination of those columns. So, the simple test to see if such a solution exists, is to append beq to Aeq,and THEN test the rank again. It that rank is STILL 31, then a solution exists.

rank([Aeq,beq])
ans =
    32

So here, the new matrix is now of full rank. That tells us that beq has information content in it that was not in the matrix Aeq. Is the differential a lot? It is not huge, but it is significant. So, was the problem possibly just a typing error?

U,S,V] = svd(Aeq);
U(:,end)'*beq
ans =
       35.293
bdelta = U(:,end)'*beq*U(:,end)
bdelta =
       6.2336
       6.2336
       6.2336
       6.2336
       6.2336
       6.2336
       6.2336
       6.2336
       6.2336
       6.2336
       6.2336
       6.2336
       6.2336
       6.2336
       6.2336
       6.2336
      -5.9663
      -6.0712
      -6.6701
      -5.8189
      -5.7125
      -6.2129
      -6.4774
      -5.7752
      -6.1643
      -6.6471
      -6.9377
      -6.1171
      -6.0338
      -6.4881
      -6.7246
        -5.92

So, my best guess at how to change the vector beq, so that a solution COULD exist is to adjust beq by bdelta. As you can see, if we perturb beq by bdelta, then a solution will exist.

rank([Aeq,beq-bdelta])
ans =
    31

Again, IF we perturbed the elements of beq by the amounts in the vector bdelta, then the problem would now in theory be feasible. The thing is, bdelta is not that small, not relative to the size of the numbers in beq, nor is bdelta indicative of where you may have made a typing error. It may indicate there was a typo in your construction of the coefficients in Aeq.

In the end, linprog failed because your problem is inconsistent. No solution can ever be found that will satisfy the equality constraint system as you have posed it. My best guess is you made some unknown error in constructing the equations. It may have been when those coefficients were brought into MATLAB. Hmm, I could probably locate the smallest single element perturbation of Aeq or beq that would bring the problem back into feasiblilty. I'm not confident it is worth the effort at this point, since I do not know how those variables were created.

It LOOKS like Aeq was created programmatically. So the first 16 rows indicate weighted sums of each block of 16 unknowns. The second set of 16 rows are just copies of the identity matrix. So I know what your matrix tries to do, but at the same time, I see no obvious mistakes as to how Aeq was created. It seems to be consistent with itself based on all of the checks I can make. (I did make a few of them.)

So, then I looked more carefully at beq.

beq
beq =
          1068.95017960331
          1123.34967983758
          856.792128689677
          1714.94424488521
          951.991254099641
           1034.9504919569
          951.991254099641
          1481.02639387787
          934.311416523505
          654.153990317039
          440.635951897548
          1837.34312041231
          1168.22926753084
             379.436514134
          1521.82601905357
          1296.06809308137
                      1896
                      1800
                      1512
                      1566
                      1494
                      1566
                      1566
                      1800
                       736
                       544
                       832
                       624
                       480
                       336
                       408
                       256

Does anything seem out of kilter? It is not obvious to me. I could check for single element perturbations to beq that would restore feasibility to the problem.

I just did exactly that, and nothing obvious was flagged in my eyes, except that each of the first 16 elements of beq was too large by almost exactly the same amount: 199.816.

So you did something wrong. I'm not sure what it was or where you error came from, but linprog is 100% correct in telling you that no feasible solution exists for the system you have posed.

[John D'Errico]

By the way, I see by reading your comments to Walter, that you were wondering how you might find an approximate solution.

The problem is, there are infinitely many possible approximate solutions. Not just a simple infinity either. But a whole boatload of infinities. But, what is the best we can possibly do?

x0 = lsqlin(Aeq,beq,[],[],[],[],zeros(256,1));

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the default value of the optimality tolerance,
and constraints are satisfied to within the default value of the constraint tolerance.

<stopping criteria details>

LSQLIN does solve that problem, giving ONE possible solution.

plot(x0,'-o')

Indeed, some of those elements are very near zero, but all are positive.

The error made in the solution is:

norm(Aeq *x0 - beq)
ans =
       35.293

Which, if you appreciate the linear algebra I did to write my answer, it is not a coincidence that this yields the same number.

U(:,end)'*beq
ans =
       35.293

However, the solution x0 is not necessarily one that minimizes the linprog problem posed. In order to do that, we need to modify beq.

nullAeq = null(Aeq');
beqhat = beq - beq'*nullAeq*nullAeq
beqhat =
       1062.7
       1117.1
       850.56
       1708.7
       945.76
       1028.7
       945.76
       1474.8
       928.08
       647.92
        434.4
       1831.1
         1162
        373.2
       1515.6
       1289.8
         1902
       1806.1
       1518.7
       1571.8
       1499.7
       1572.2
       1572.5
       1805.8
       742.16
       550.65
       838.94
       630.12
       486.03
       342.49
       414.72
       261.92
rank([Aeq,beqhat])
ans =
    31

But, can we now solve the approximate problem? Yes. But the solution is only one of infinitely many equally valid solutions.

xhat = linprog(f,A,b,Aeq,beqhat,lb,ub);
plot(xhat)

Most of the elements are 0, as should be expected. And there are infinitely many ways I could have solved the problem differently, getting a completely different approximate solution for each, that would have been equally well approximately valid.

Answer 3

[Walter Roberson]

If you use the symbolic toolbox, you can solve the first 31 (of 32) equalities for variables [1:17 33 48 49 65 81 97 113 129 145 161 177 193 209 225 241 ] .

However when you substitute that into the 32nd equation

x16 + x32 + x48 + x64 + x80 + x96 + x112 + x128 + x144 + x160 + x176 + x192 + x208 + x224 + x240 + x256 == 256

then you get the inconsistency

12772858437668988265496/27386139134060684307 == 256

Your equality equations are not consistent with each other, so the system cannot be solved.

[Austin Brehm]

Okay so with the constraints that I have, no solution exists? Is there a way to approximate a solution?

[Walter Roberson]

With the constraints you have now, there is no solution. If you want to approximate a solution you will need to describe how you are willing to relax your equalities.

[Walter Roberson]

Suppose you approximate the solution by considering each equality equation Aeq(K,:)*x == beq(K) as being Aeq(K,:)*x - beq(K) and asking to minimize the squared sum of residues residue = sum((Aeq*x - beq).^2) . In the case where all of the equalities could be met, the residue would be 0. If not all of the equalities can be met, then you can try to minimize the residue, to minimize the constraint violation in one sense, under the assumption that the equalities are all of equal weight.

If you construct that residue then you can proceed to minimize it by using calculus: differentiate with respect to a variable, solve for zero, substitute back in, go for another variable, and so on. You can proceed in the order x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x33, x49, x65, x81, x97, x113, x129, x145, x161, x177, x193, x209, x225 . After that, you arrive at a residue that has no variables and is non-zero, indicating that the equalities cannot all be solved simultaneously. Back substitute from there to get values those variables must equal in terms of the others in order to get the f with least constraint violation.

x1 = (8772648985220703*x18)/8621075391639826 + (92568112640880017408*x19)/82801118599004708817 + (8407957995560919*x20)/8621075391639826 + (4127107857803151*x21)/4310537695819913 + (8977404239245911*x22)/8621075391639826 + (14193657175611539456*x23)/13073860831421796129 + (80148310768499032064*x24)/82801118599004708817 + (4453553770196300*x25)/4310537695819913 + (4802331290924450*x26)/4310537695819913 + (32093776844548997120*x27)/27600372866334902939 + (84892852975933849600*x28)/82801118599004708817 + (4359264757226295*x29)/4310537695819913 + (90041593249925169152*x30)/82801118599004708817 + (4858336151197661*x31)/4310537695819913 + (4277079358747569*x32)/4310537695819913 + (8772648985220703*x34)/8621075391639826 + (92568112640880017408*x35)/82801118599004708817 + (8407957995560919*x36)/8621075391639826 + (4127107857803151*x37)/4310537695819913 + (8977404239245911*x38)/8621075391639826 + (14193657175611539456*x39)/13073860831421796129 + (80148310768499032064*x40)/82801118599004708817 + (4453553770196300*x41)/4310537695819913 + (4802331290924450*x42)/4310537695819913 + (32093776844548997120*x43)/27600372866334902939 + (84892852975933849600*x44)/82801118599004708817 + (4359264757226295*x45)/4310537695819913 + (90041593249925169152*x46)/82801118599004708817 + (4858336151197661*x47)/4310537695819913 + (4277079358747569*x48)/4310537695819913 + (8772648985220703*x50)/8621075391639826 + (92568112640880017408*x51)/82801118599004708817 + (8407957995560919*x52)/8621075391639826 + (4127107857803151*x53)/4310537695819913 + (8977404239245911*x54)/8621075391639826 + (14193657175611539456*x55)/13073860831421796129 + (80148310768499032064*x56)/82801118599004708817 + (4453553770196300*x57)/4310537695819913 + (4802331290924450*x58)/4310537695819913 + (32093776844548997120*x59)/27600372866334902939 + (84892852975933849600*x60)/82801118599004708817 + (4359264757226295*x61)/4310537695819913 + (90041593249925169152*x62)/82801118599004708817 + (4858336151197661*x63)/4310537695819913 + (4277079358747569*x64)/4310537695819913 + (8772648985220703*x66)/8621075391639826 + (92568112640880017408*x67)/82801118599004708817 + (8407957995560919*x68)/8621075391639826 + (4127107857803151*x69)/4310537695819913 + (8977404239245911*x70)/8621075391639826 + (14193657175611539456*x71)/13073860831421796129 + (80148310768499032064*x72)/82801118599004708817 + (4453553770196300*x73)/4310537695819913 + (4802331290924450*x74)/4310537695819913 + (32093776844548997120*x75)/27600372866334902939 + (84892852975933849600*x76)/82801118599004708817 + (4359264757226295*x77)/4310537695819913 + (90041593249925169152*x78)/82801118599004708817 + (4858336151197661*x79)/4310537695819913 + (4277079358747569*x80)/4310537695819913 + (8772648985220703*x82)/8621075391639826 + (92568112640880017408*x83)/82801118599004708817 + (8407957995560919*x84)/8621075391639826 + (4127107857803151*x85)/4310537695819913 + (8977404239245911*x86)/8621075391639826 + (14193657175611539456*x87)/13073860831421796129 + (80148310768499032064*x88)/82801118599004708817 + (4453553770196300*x89)/4310537695819913 + (4802331290924450*x90)/4310537695819913 + (32093776844548997120*x91)/27600372866334902939 + (84892852975933849600*x92)/82801118599004708817 + (4359264757226295*x93)/4310537695819913 + (90041593249925169152*x94)/82801118599004708817 + (4858336151197661*x95)/4310537695819913 + (4277079358747569*x96)/4310537695819913 + (8772648985220703*x98)/8621075391639826 + (92568112640880017408*x99)/82801118599004708817 + (8407957995560919*x100)/8621075391639826 + (4127107857803151*x101)/4310537695819913 + (8977404239245911*x102)/8621075391639826 + (14193657175611539456*x103)/13073860831421796129 + (80148310768499032064*x104)/82801118599004708817 + (4453553770196300*x105)/4310537695819913 + (4802331290924450*x106)/4310537695819913 + (32093776844548997120*x107)/27600372866334902939 + (84892852975933849600*x108)/82801118599004708817 + (4359264757226295*x109)/4310537695819913 + (90041593249925169152*x110)/82801118599004708817 + (4858336151197661*x111)/4310537695819913 + (4277079358747569*x112)/4310537695819913 + (8772648985220703*x114)/8621075391639826 + (92568112640880017408*x115)/82801118599004708817 + (8407957995560919*x116)/8621075391639826 + (4127107857803151*x117)/4310537695819913 + (8977404239245911*x118)/8621075391639826 + (14193657175611539456*x119)/13073860831421796129 + (80148310768499032064*x120)/82801118599004708817 + (4453553770196300*x121)/4310537695819913 + (4802331290924450*x122)/4310537695819913 + (32093776844548997120*x123)/27600372866334902939 + (84892852975933849600*x124)/82801118599004708817 + (4359264757226295*x125)/4310537695819913 + (90041593249925169152*x126)/82801118599004708817 + (4858336151197661*x127)/4310537695819913 + (4277079358747569*x128)/4310537695819913 + (8772648985220703*x130)/8621075391639826 + (92568112640880017408*x131)/82801118599004708817 + (8407957995560919*x132)/8621075391639826 + (4127107857803151*x133)/4310537695819913 + (8977404239245911*x134)/8621075391639826 + (14193657175611539456*x135)/13073860831421796129 + (80148310768499032064*x136)/82801118599004708817 + (4453553770196300*x137)/4310537695819913 + (4802331290924450*x138)/4310537695819913 + (32093776844548997120*x139)/27600372866334902939 + (84892852975933849600*x140)/82801118599004708817 + (4359264757226295*x141)/4310537695819913 + (90041593249925169152*x142)/82801118599004708817 + (4858336151197661*x143)/4310537695819913 + (4277079358747569*x144)/4310537695819913 + (8772648985220703*x146)/8621075391639826 + (92568112640880017408*x147)/82801118599004708817 + (8407957995560919*x148)/8621075391639826 + (4127107857803151*x149)/4310537695819913 + (8977404239245911*x150)/8621075391639826 + (14193657175611539456*x151)/13073860831421796129 + (80148310768499032064*x152)/82801118599004708817 + (4453553770196300*x153)/4310537695819913 + (4802331290924450*x154)/4310537695819913 + (32093776844548997120*x155)/27600372866334902939 + (84892852975933849600*x156)/82801118599004708817 + (4359264757226295*x157)/4310537695819913 + (90041593249925169152*x158)/82801118599004708817 + (4858336151197661*x159)/4310537695819913 + (4277079358747569*x160)/4310537695819913 + (8772648985220703*x162)/8621075391639826 + (92568112640880017408*x163)/82801118599004708817 + (8407957995560919*x164)/8621075391639826 + (4127107857803151*x165)/4310537695819913 + (8977404239245911*x166)/8621075391639826 + (14193657175611539456*x167)/13073860831421796129 + (80148310768499032064*x168)/82801118599004708817 + (4453553770196300*x169)/4310537695819913 + (4802331290924450*x170)/4310537695819913 + (32093776844548997120*x171)/27600372866334902939 + (84892852975933849600*x172)/82801118599004708817 + (4359264757226295*x173)/4310537695819913 + (90041593249925169152*x174)/82801118599004708817 + (4858336151197661*x175)/4310537695819913 + (4277079358747569*x176)/4310537695819913 + (8772648985220703*x178)/8621075391639826 + (92568112640880017408*x179)/82801118599004708817 + (8407957995560919*x180)/8621075391639826 + (4127107857803151*x181)/4310537695819913 + (8977404239245911*x182)/8621075391639826 + (14193657175611539456*x183)/13073860831421796129 + (80148310768499032064*x184)/82801118599004708817 + (4453553770196300*x185)/4310537695819913 + (4802331290924450*x186)/4310537695819913 + (32093776844548997120*x187)/27600372866334902939 + (84892852975933849600*x188)/82801118599004708817 + (4359264757226295*x189)/4310537695819913 + (90041593249925169152*x190)/82801118599004708817 + (4858336151197661*x191)/4310537695819913 + (4277079358747569*x192)/4310537695819913 + (8772648985220703*x194)/8621075391639826 + (92568112640880017408*x195)/82801118599004708817 + (8407957995560919*x196)/8621075391639826 + (4127107857803151*x197)/4310537695819913 + (8977404239245911*x198)/8621075391639826 + (14193657175611539456*x199)/13073860831421796129 + (80148310768499032064*x200)/82801118599004708817 + (4453553770196300*x201)/4310537695819913 + (4802331290924450*x202)/4310537695819913 + (32093776844548997120*x203)/27600372866334902939 + (84892852975933849600*x204)/82801118599004708817 + (4359264757226295*x205)/4310537695819913 + (90041593249925169152*x206)/82801118599004708817 + (4858336151197661*x207)/4310537695819913 + (4277079358747569*x208)/4310537695819913 + (8772648985220703*x210)/8621075391639826 + (92568112640880017408*x211)/82801118599004708817 + (8407957995560919*x212)/8621075391639826 + (4127107857803151*x213)/4310537695819913 + (8977404239245911*x214)/8621075391639826 + (14193657175611539456*x215)/13073860831421796129 + (80148310768499032064*x216)/82801118599004708817 + (4453553770196300*x217)/4310537695819913 + (4802331290924450*x218)/4310537695819913 + (32093776844548997120*x219)/27600372866334902939 + (84892852975933849600*x220)/82801118599004708817 + (4359264757226295*x221)/4310537695819913 + (90041593249925169152*x222)/82801118599004708817 + (4858336151197661*x223)/4310537695819913 + (4277079358747569*x224)/4310537695819913 + (8772648985220703*x226)/8621075391639826 + (92568112640880017408*x227)/82801118599004708817 + (8407957995560919*x228)/8621075391639826 + (4127107857803151*x229)/4310537695819913 + (8977404239245911*x230)/8621075391639826 + (14193657175611539456*x231)/13073860831421796129 + (80148310768499032064*x232)/82801118599004708817 + (4453553770196300*x233)/4310537695819913 + (4802331290924450*x234)/4310537695819913 + (32093776844548997120*x235)/27600372866334902939 + (84892852975933849600*x236)/82801118599004708817 + (4359264757226295*x237)/4310537695819913 + (90041593249925169152*x238)/82801118599004708817 + (4858336151197661*x239)/4310537695819913 + (4277079358747569*x240)/4310537695819913 + (8772648985220703*x242)/8621075391639826 + (92568112640880017408*x243)/82801118599004708817 + (8407957995560919*x244)/8621075391639826 + (4127107857803151*x245)/4310537695819913 + (8977404239245911*x246)/8621075391639826 + (14193657175611539456*x247)/13073860831421796129 + (80148310768499032064*x248)/82801118599004708817 + (4453553770196300*x249)/4310537695819913 + (4802331290924450*x250)/4310537695819913 + (32093776844548997120*x251)/27600372866334902939 + (84892852975933849600*x252)/82801118599004708817 + (4359264757226295*x253)/4310537695819913 + (90041593249925169152*x254)/82801118599004708817 + (4858336151197661*x255)/4310537695819913 + (4277079358747569*x256)/4310537695819913 - 561364608676283893184584958384761037397048940183932329728433928/37226881503254587069916582681156129322543129006689830182215

x2 = 15597682935217799466258756605032702599588435432/8636250076029926322527764764222395259999055 - x34 - x50 - x66 - x82 - x98 - x114 - x130 - x146 - x162 - x178 - x194 - x210 - x226 - x242 - x18

x3 =   13115614949356682968509103379211779470135397016/8636250076029926322527764764222395259999055 - x35 - x51 - x67 - x83 - x99 - x115 - x131 - x147 - x163 - x179 - x195 - x211 - x227 - x243 - x19

x4 = 13574620714447891615132647752871238623575862066/8636250076029926322527764764222395259999055 - x36 - x52 - x68 - x84 - x100 - x116 - x132 - x148 - x164 - x180 - x196 - x212 - x228 - x244 - x20

x5 = 12951891814580669074145856622866575798530132458/8636250076029926322527764764222395259999055 - x37 - x53 - x69 - x85 - x101 - x117 - x133 - x149 - x165 - x181 - x197 - x213 - x229 - x245 - x21

x6 = 13578024208663211864714834987971697362945233714/8636250076029926322527764764222395259999055 - x38 - x54 - x70 - x86 - x102 - x118 - x134 - x150 - x166 - x182 - x198 - x214 - x230 - x246 - x22

x7 = 13580307840478033900937689107998187955539713346/8636250076029926322527764764222395259999055 - x39 - x55 - x71 - x87 - x103 - x119 - x135 - x151 - x167 - x183 - x199 - x215 - x231 - x247 - x23

x8 = 15595126169080269888312985464803217980591555448/8636250076029926322527764764222395259999055 - x40 - x56 - x72 - x88 - x104 - x120 - x136 - x152 - x168 - x184 - x200 - x216 - x232 - x248 - x24

x9 = 1281903298560746707533536047223546380632735776/1727250015205985264505552952844479051999811 - x41 - x57 - x73 - x89 - x105 - x121 - x137 - x153 - x169 - x185 - x201 - x217 - x233 - x249 - x25

x10 = 951105131872375600099938109975880167958297504/1727250015205985264505552952844479051999811 - x42 - x58 - x74 - x90 - x106 - x122 - x138 - x154 - x170 - x186 - x202 - x218 - x234 - x250 - x26

x11 = 1449055124206575453976842755500027610300766656/1727250015205985264505552952844479051999811 - x43 - x59 - x75 - x91 - x107 - x123 - x139 - x155 - x171 - x187 - x203 - x219 - x235 - x251 - x27

x12 = 1088369718560180210286569895343474443660231504/1727250015205985264505552952844479051999811 - x44 - x60 - x76 - x92 - x108 - x124 - x140 - x156 - x172 - x188 - x204 - x220 - x236 - x252 - x28

x13 = 839501874190650375097096354648154289288195072/1727250015205985264505552952844479051999811 - x45 - x61 - x77 - x93 - x109 - x125 - x141 - x157 - x173 - x189 - x205 - x221 - x237 - x253 - x29

x14 = 2957812615173820363259716254575595575932442544/8636250076029926322527764764222395259999055 - x46 - x62 - x78 - x94 - x110 - x126 - x142 - x158 - x174 - x190 - x206 - x222 - x238 - x254 - x30

x15 = 3581665114208675197288570251078911770109545608/8636250076029926322527764764222395259999055 - x47 - x63 - x79 - x95 - x111 - x127 - x143 - x159 - x175 - x191 - x207 - x223 - x239 - x255 - x31

x16 = 2262006934488200969366163898832214724422917152/8636250076029926322527764764222395259999055 - x48 - x64 - x80 - x96 - x112 - x128 - x144 - x160 - x176 - x192 - x208 - x224 - x240 - x256 - x32

x17 = 43449351499685028368455894812102037540918774327710550310085632/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x19)/82801118599004708817 - (8407957995560919*x20)/8621075391639826 - (4127107857803151*x21)/4310537695819913 - (8977404239245911*x22)/8621075391639826 - (14193657175611539456*x23)/13073860831421796129 - (80148310768499032064*x24)/82801118599004708817 - (4453553770196300*x25)/4310537695819913 - (4802331290924450*x26)/4310537695819913 - (32093776844548997120*x27)/27600372866334902939 - (84892852975933849600*x28)/82801118599004708817 - (4359264757226295*x29)/4310537695819913 - (90041593249925169152*x30)/82801118599004708817 - (4858336151197661*x31)/4310537695819913 - (4277079358747569*x32)/4310537695819913 - (8772648985220703*x18)/8621075391639826

x33 = 33081805428729426625191068532832881486512460775315494745823232/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x35)/82801118599004708817 - (8407957995560919*x36)/8621075391639826 - (4127107857803151*x37)/4310537695819913 - (8977404239245911*x38)/8621075391639826 - (14193657175611539456*x39)/13073860831421796129 - (80148310768499032064*x40)/82801118599004708817 - (4453553770196300*x41)/4310537695819913 - (4802331290924450*x42)/4310537695819913 - (32093776844548997120*x43)/27600372866334902939 - (84892852975933849600*x44)/82801118599004708817 - (4359264757226295*x45)/4310537695819913 - (90041593249925169152*x46)/82801118599004708817 - (4858336151197661*x47)/4310537695819913 - (4277079358747569*x48)/4310537695819913 - (8772648985220703*x34)/8621075391639826

x49 = 66458956300020168725697762409688108951548322660410206436472832/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x51)/82801118599004708817 - (8407957995560919*x52)/8621075391639826 - (4127107857803151*x53)/4310537695819913 - (8977404239245911*x54)/8621075391639826 - (14193657175611539456*x55)/13073860831421796129 - (80148310768499032064*x56)/82801118599004708817 - (4453553770196300*x57)/4310537695819913 - (4802331290924450*x58)/4310537695819913 - (32093776844548997120*x59)/27600372866334902939 - (84892852975933849600*x60)/82801118599004708817 - (4359264757226295*x61)/4310537695819913 - (90041593249925169152*x62)/82801118599004708817 - (4858336151197661*x63)/4310537695819913 - (4277079358747569*x64)/4310537695819913 - (8772648985220703*x50)/8621075391639826

x65 = 36784500454070716120471391437802063744668686531075423961285632/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x67)/82801118599004708817 - (8407957995560919*x68)/8621075391639826 - (4127107857803151*x69)/4310537695819913 - (8977404239245911*x70)/8621075391639826 - (14193657175611539456*x71)/13073860831421796129 - (80148310768499032064*x72)/82801118599004708817 - (4453553770196300*x73)/4310537695819913 - (4802331290924450*x74)/4310537695819913 - (32093776844548997120*x75)/27600372866334902939 - (84892852975933849600*x76)/82801118599004708817 - (4359264757226295*x77)/4310537695819913 - (90041593249925169152*x78)/82801118599004708817 - (4858336151197661*x79)/4310537695819913 - (4277079358747569*x80)/4310537695819913 - (8772648985220703*x66)/8621075391639826

x81 = 40011134690439554740895678387464105017378477444218558437548032/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x83)/82801118599004708817 - (8407957995560919*x84)/8621075391639826 - (4127107857803151*x85)/4310537695819913 - (8977404239245911*x86)/8621075391639826 - (14193657175611539456*x87)/13073860831421796129 - (80148310768499032064*x88)/82801118599004708817 - (4453553770196300*x89)/4310537695819913 - (4802331290924450*x90)/4310537695819913 - (32093776844548997120*x91)/27600372866334902939 - (84892852975933849600*x92)/82801118599004708817 - (4359264757226295*x93)/4310537695819913 - (90041593249925169152*x94)/82801118599004708817 - (4858336151197661*x95)/4310537695819913 - (4277079358747569*x96)/4310537695819913 - (8772648985220703*x82)/8621075391639826

x97 = 36784500454070716120471391437802063744668686531075423961285632/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x99)/82801118599004708817 - (8407957995560919*x100)/8621075391639826 - (4127107857803151*x101)/4310537695819913 - (8977404239245911*x102)/8621075391639826 - (14193657175611539456*x103)/13073860831421796129 - (80148310768499032064*x104)/82801118599004708817 - (4453553770196300*x105)/4310537695819913 - (4802331290924450*x106)/4310537695819913 - (32093776844548997120*x107)/27600372866334902939 - (84892852975933849600*x108)/82801118599004708817 - (4359264757226295*x109)/4310537695819913 - (90041593249925169152*x110)/82801118599004708817 - (4858336151197661*x111)/4310537695819913 - (4277079358747569*x112)/4310537695819913 - (8772648985220703*x98)/8621075391639826

x113 = 57360905666324438929889057962786180281142874876237518923087872/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x115)/82801118599004708817 - (8407957995560919*x116)/8621075391639826 - (4127107857803151*x117)/4310537695819913 - (8977404239245911*x118)/8621075391639826 - (14193657175611539456*x119)/13073860831421796129 - (80148310768499032064*x120)/82801118599004708817 - (4453553770196300*x121)/4310537695819913 - (4802331290924450*x122)/4310537695819913 - (32093776844548997120*x123)/27600372866334902939 - (84892852975933849600*x124)/82801118599004708817 - (4359264757226295*x125)/4310537695819913 - (90041593249925169152*x126)/82801118599004708817 - (4858336151197661*x127)/4310537695819913 - (4277079358747569*x128)/4310537695819913 - (8772648985220703*x114)/8621075391639826

x129 = 36096857092221616973199309225552200105745067872510652467261952/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x131)/82801118599004708817 - (8407957995560919*x132)/8621075391639826 - (4127107857803151*x133)/4310537695819913 - (8977404239245911*x134)/8621075391639826 - (14193657175611539456*x135)/13073860831421796129 - (80148310768499032064*x136)/82801118599004708817 - (4453553770196300*x137)/4310537695819913 - (4802331290924450*x138)/4310537695819913 - (32093776844548997120*x139)/27600372866334902939 - (84892852975933849600*x140)/82801118599004708817 - (4359264757226295*x141)/4310537695819913 - (90041593249925169152*x142)/82801118599004708817 - (4858336151197661*x143)/4310537695819913 - (4277079358747569*x144)/4310537695819913 - (8772648985220703*x130)/8621075391639826

x145 = 25200354589074405603294464622231930253184692984911587814730752/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x147)/82801118599004708817 - (8407957995560919*x148)/8621075391639826 - (4127107857803151*x149)/4310537695819913 - (8977404239245911*x150)/8621075391639826 - (14193657175611539456*x151)/13073860831421796129 - (80148310768499032064*x152)/82801118599004708817 - (4453553770196300*x153)/4310537695819913 - (4802331290924450*x154)/4310537695819913 - (32093776844548997120*x155)/27600372866334902939 - (84892852975933849600*x156)/82801118599004708817 - (4359264757226295*x157)/4310537695819913 - (90041593249925169152*x158)/82801118599004708817 - (4858336151197661*x159)/4310537695819913 - (4277079358747569*x160)/4310537695819913 - (8772648985220703*x146)/8621075391639826

x161 = 16895738603666088036565768197745533712902557562611727373990912/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x163)/82801118599004708817 - (8407957995560919*x164)/8621075391639826 - (4127107857803151*x165)/4310537695819913 - (8977404239245911*x166)/8621075391639826 - (14193657175611539456*x167)/13073860831421796129 - (80148310768499032064*x168)/82801118599004708817 - (4453553770196300*x169)/4310537695819913 - (4802331290924450*x170)/4310537695819913 - (32093776844548997120*x171)/27600372866334902939 - (84892852975933849600*x172)/82801118599004708817 - (4359264757226295*x173)/4310537695819913 - (90041593249925169152*x174)/82801118599004708817 - (4858336151197661*x175)/4310537695819913 - (4277079358747569*x176)/4310537695819913 - (8772648985220703*x162)/8621075391639826

x177 = 71219564189744677474258121962759518806012671086578153828472832/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x179)/82801118599004708817 - (8407957995560919*x180)/8621075391639826 - (4127107857803151*x181)/4310537695819913 - (8977404239245911*x182)/8621075391639826 - (14193657175611539456*x183)/13073860831421796129 - (80148310768499032064*x184)/82801118599004708817 - (4453553770196300*x185)/4310537695819913 - (4802331290924450*x186)/4310537695819913 - (32093776844548997120*x187)/27600372866334902939 - (84892852975933849600*x188)/82801118599004708817 - (4359264757226295*x189)/4310537695819913 - (90041593249925169152*x190)/82801118599004708817 - (4858336151197661*x191)/4310537695819913 - (4277079358747569*x192)/4310537695819913 - (8772648985220703*x178)/8621075391639826

x193 = 45194907725917351190768052599776405910366074938549713100163072/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x195)/82801118599004708817 - (8407957995560919*x196)/8621075391639826 - (4127107857803151*x197)/4310537695819913 - (8977404239245911*x198)/8621075391639826 - (14193657175611539456*x199)/13073860831421796129 - (80148310768499032064*x200)/82801118599004708817 - (4453553770196300*x201)/4310537695819913 - (4802331290924450*x202)/4310537695819913 - (32093776844548997120*x203)/27600372866334902939 - (84892852975933849600*x204)/82801118599004708817 - (4359264757226295*x205)/4310537695819913 - (90041593249925169152*x206)/82801118599004708817 - (4858336151197661*x207)/4310537695819913 - (4277079358747569*x208)/4310537695819913 - (8772648985220703*x194)/8621075391639826

x209 = 14515434658803833662285588421209828785670383349527753677990912/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x211)/82801118599004708817 - (8407957995560919*x212)/8621075391639826 - (4127107857803151*x213)/4310537695819913 - (8977404239245911*x214)/8621075391639826 - (14193657175611539456*x215)/13073860831421796129 - (80148310768499032064*x216)/82801118599004708817 - (4453553770196300*x217)/4310537695819913 - (4802331290924450*x218)/4310537695819913 - (32093776844548997120*x219)/27600372866334902939 - (84892852975933849600*x220)/82801118599004708817 - (4359264757226295*x221)/4310537695819913 - (90041593249925169152*x222)/82801118599004708817 - (4858336151197661*x223)/4310537695819913 - (4277079358747569*x224)/4310537695819913 - (8772648985220703*x210)/8621075391639826

x225 = 58947774962899272231569151862261798809820618163715919307410432/37226881503254587069916582681156129322543129006689830182215 - (92568112640880017408*x227)/82801118599004708817 - (8407957995560919*x228)/8621075391639826 - (4127107857803151*x229)/4310537695819913 - (8977404239245911*x230)/8621075391639826 - (14193657175611539456*x231)/13073860831421796129 - (80148310768499032064*x232)/82801118599004708817 - (4453553770196300*x233)/4310537695819913 - (4802331290924450*x234)/4310537695819913 - (32093776844548997120*x235)/27600372866334902939 - (84892852975933849600*x236)/82801118599004708817 - (4359264757226295*x237)/4310537695819913 - (90041593249925169152*x238)/82801118599004708817 - (4858336151197661*x239)/4310537695819913 - (4277079358747569*x240)/4310537695819913 - (8772648985220703*x226)/8621075391639826

You then substitute these into f*x . The resulting expression is linear, with a mix of positive and negative terms.

Since your lower bound is 0 and your upper bound is positive infinity, you can take any of the negative terms and set its associated variable to infinity, and set the remaining variables involved in the expression to non-negative values, and that will represent an optimization of the system (yielding negative infinity.)

It is tempting to say, "Take all of the variables that have positive coefficients and set the variables to zero, and take all of the variables that have negative coefficients and set the variables to infinity". It does not hurt to do the first part of that, setting the variables with associated positive coefficients to 0. However, before setting the other variables to infinity in bulk, you need to check each of the equalities, in case those equalities might involve addition and subtraction of different infinite variables, which would be undefined. Looking through them all, I find that in each case all of the coefficients involved with variables are the same sign within any one equality. Therefore, it would not be a problem to set all of the variables with negative coefficients in the resolved f*x to infinity. It isn't necessary to do so though.

In all, 153 variables have negative coefficients and 73 have positive coefficients and 30 are defined in terms of the other variables by the constraints.