Maximizing an expression with multiple constraints

Question

I'm asked to write a function solvelinear[k_,m_] using LinearProgramming that maximizes the expression $$\sum_{i=1}^4\left(i-\frac{k^2}{m}\right)^2x_i$$ subject to constraints

• $x_1+x_2+x_3+x_4=m$
• $x_1+2x_2+3x_3+4x_4=k^2$
• $x_1+x_3\leq k$
• $x_1,x_2,x_3,x_4$ are integers.

I'm reading the tutorial on LinearProgramming but it seems to minimize things? Following the tutorial I came up with this:

solvelinear[k_, m_] := 
 LinearProgramming[{(1 - k^2/m)^2, (2 - k^2/m)^2, (3 - k^2/m)^2, (4 - 
      k^2/m)^2}, {{1, 1, 1, 1}}, {{m, 0}}, {{1, 2, 3, 4}}, {{k^2, 
    0}}, {{1, 0, 1, 0}}, {{k, -1}}, Integers]

It doesn't work and I should maximize things anyway. Is there a way to do this with LinearProgramming or should I just use Maximize?

Answer 1

Three ways.

Method 1.

Clear[k, m, x, c1, c2, c3, sum, max]

Define the constraints:

c1 = x[1] + x[2] + x[3] + x[4] == m;
c2 = x[1] + 2 x[2] + 3 x[3] + 4 x[4] == k^2;
c3 = x[1] + x[3] <= k;

Define the sum to be maximized:

sum = Sum[(i - k^2/m)^2 x[i], {i, 1, 4}]

Define a function that attempts to maximize the sum for given m, k:

max[k_, m_] := 
 Evaluate @ Maximize[{sum, c1, c2, c3, x[1] >= 0, x[2] >= 0, x[3] >= 0, x[4] >= 0},
    {x[1], x[2], x[3], x[4]}, Integers]

Test:

Quiet @ max[6, 10]

{42/5, {x[1] -> 1, x[2] -> 0, x[3] -> 1, x[4] -> 8}}

Quiet @ max[7, 10]

{-∞, {x[1] -> Indeterminate, x[2] -> Indeterminate, x[3] -> Indeterminate, x[4] -> Indeterminate}}

Quiet is used because in the second case there are no instances that fulfill the conditions, so there's a bunch of warnings.

Method 2.

Clear[k, m, x, c1, c2, c3, sum, con]

Put the constraints into Solve:

con[k_, m_] := 
 Solve[{x[1] + x[2] + x[3] + x[4] == m, 
   x[1] + 2 x[2] + 3 x[3] + 4 x[4] == k^2, x[1] + x[3] <= k, 
   x[1] >= 0, x[2] >= 0, x[3] >= 0, x[4] >= 0}, {x[1], x[2], x[3], x[4]}, Integers]

E.g.

con[6, 10]

{{x[1] -> 0, x[2] -> 0, x[3] -> 4, x[4] -> 6}, {x[1] -> 0, x[2] -> 1, x[3] -> 2, x[4] -> 7}, {x[1] -> 0, x[2] -> 2, x[3] -> 0, x[4] -> 8}, {x[1] -> 1, x[2] -> 0, x[3] -> 1, x[4] -> 8}}

Define the sum as a function:

sum[k_, m_] := Sum[(i - k^2/m)^2 x[i], {i, 1, 4}]

and

sum[6, 10] /. con[6, 10]

{12/5, 22/5, 32/5, 42/5}

The last number, 42/5, is the greatest and corresponds to {x[1] -> 1, x[2] -> 0, x[3] -> 1, x[4] -> 8} - the same as in the previous method.

This can be wrapped into

MaximalBy[Transpose@{sum[6, 10] /. con[6, 10], con[6, 10]}, First]

{{42/5, {x[1] -> 1, x[2] -> 0, x[3] -> 1, x[4] -> 8}}}

which can be given a name

max2[k_, m_] := MaximalBy[Transpose@{sum[k, m] /. con[k, m], con[k, m]}, First]

---

Both methods work for k = 8 and m = 26, giving 552/13 for {x[1] -> 8, x[2] -> 8, x[3] -> 0, x[4] -> 10}.

Method 3.

As showed by J. M. in the comment, LinearProgramming can be employed as as follows:

max3[k_, m_] := 
 LinearProgramming[-Table[(m i - k^2)^2, {i, 4}], {{1, 1, 1, 1}, {1, 
    2, 3, 4}, {1, 0, 1, 0}}, {{m, 0}, {k^2, 0}, {k, -1}}, 
  Table[0, {4}], Integers]

with

max3[8, 26]

{8, 8, 0, 10}

with a warning:

LinearProgramming::lpip: Warning: integer linear programming will use a machine-precision approximation of the inputs.