1
$\begingroup$

For part of a coding project, I am trying to solve a nonlinear integer program, but my only experience is from school solving LPs and IPs. Here is the problem in words:

I am trying to assign n (in this case n = 1000) workers to 4 different stations. Each station produces a certain number of resources per hour (y1, y2, y3, y4), which is non-linearly dependent on the number of workers assigned. Find the number of workers in each station that will provide the highest total rate of resource production.

Let x1, x2, x3, x4 be the number of workers assigned to stations 1, 2, 3, 4, respectively. A-L are constants. Note that C, F, I, L are negative.

max y1 + y2 + y3 + y4
s.t. y1 = A*x1 + B + C/x1
     y2 = D*x2 + E + F/x2
     y3 = G*x3 + H + I/x3
     y4 = J*x4 + K + L/x4
     x1 + x2 + x3 + x4 <= 1000
     x1, x2, x3, x4 are positive integers

I am considering solving this by assigning workers one at a time to the station that will provide the largest increase in resource production until either all 1000 are assign or until there is no net increase in production. I believe that this can method can achieve a near-optimal solution since each station's production is independent of other stations' productions.

My question is this: Given that I am fine with a solution that is only close to optimal, is this method good enough? If not, what should I do?

Thanks!

This is the first question that I have asked on math.stackexchange, so I apologize for any errors in formatting or clarity.

$\endgroup$
  • $\begingroup$ Do you mean "positive integers" rather than "non-negative integers"? Your y_i are undefined when x_i = 0. $\endgroup$ – Robert Israel Dec 16 '19 at 18:46
  • 1
    $\begingroup$ If $C, F, I, L \ge 0$ the objective is a convex function of $x_1, \ldots, x_4$, so (ignoring the integer requirement) the maximum will be achieved at an extreme point. $\endgroup$ – Robert Israel Dec 16 '19 at 18:49
  • $\begingroup$ @RobertIsrael Yes they should be positive integers, so I will edit my question. And C, F, I, L are negative on the order of E^-4 $\endgroup$ – Ken Bassett Dec 16 '19 at 19:19
  • $\begingroup$ If $C, F, I, L$ are negative, the objective is a concave function of $x_1, \ldots, x_4$. Ignoring the integer constraints, there should be a unique local maximum which can be found by calculus (if there is no critical point in the feasible region, use a Lagrange multiplier with the constraint $x_1 + x_2 + x_3 + x_4 \le 1000$). If that is not an integer point, search the integer points near it. $\endgroup$ – Robert Israel Dec 16 '19 at 22:04
  • $\begingroup$ @RobertIsrael Thanks, that worked for me! $\endgroup$ – Ken Bassett Dec 17 '19 at 21:17
0
$\begingroup$

Assuming my calculus below is error-free, your intuitive approach (add one to the station with the biggest bang, repeat until no workers are left) will indeed yield the optimal solution.

First, note that we can ignore $B, E, H, K$ because they amount to constant terms in the objective function. (Just add them into the final objective value.) Ignoring integrality and differentiating $y=Ax + C/x$, we have $y'=A -C/x^2$ and $y'' = 2C/x^3$. Observe that $y' > 0$ and $y'' < 0$, since $x > 0$, $A > 0$ and $C < 0$. So the contribution function of workers at station 1 is strictly increasing and concave. The same is true at the other work stations.

Since the contribution functions are increasing, you can be sure that you will allocate all 1,000 workers someplace. Here is a sketch of proof by contraction. When I say below that a (complete or partial) solution "extends" another solution, I mean that the first solution has at least as many workers at every station as the solution it extends.

Suppose that your algorithm is wrong. Identify the last partial solution ($S_1$) that was correct (meaning it could be extended to an optimal solution by adding workers to some or all stations), then identify any optimal solution ($S_2$) that extends $S_1$. Since $S_1$ was the last solution where your algorithm was valid, it must be that at $S_1$ your algorithm wanted to add a worker to some station $j$ that was at its maximum count among optimal solutions. Finally, define a partial solution ($S_3$) by taking $S_1$ and adding a worker to any station $k \neq j$ where $S_2$ has more workers than $S_1$. Since you get from $S_1$ to both $S_2$ and $S_3$ by adding workers (not subtracting), it must be that all three have the same count at station $j$.

Now suppose you were to start from the optimal solution $S_2$ and move one worker from station $k$ to station $j$. Since $S_2$ is optimal, and since by assumption no optimal solution has more workers at station $j$ than $S_1$ and $S_2$ do, the sum of the incremental increase to $y_j$ and incremental decrease to $y_k$ must be negative. Note that, because $S_1$ and $S_2$ have the same count at station $j$, the incremental change to $y_j$ from a new worker is the same at both of them. On the other hand, the incremental decrease to $y_k$ when removing a worker from station $k$ in $S_2$ is no larger than the incremental benefit of adding a worker to station $k$ at $S_3$ (due to concavity), which is strictly less than the benefit of adding a worker to station $k$ at $S_1$ (again due to concavity), which is no greater than the incremental value of adding a worker to station $j$ at $S_1$ (since that's what your algorithm wanted to do). String all that together, and it should contradict the assumption that shifting a worker from $k$ to $j$ in $S_2$ has negative benefit.

$\endgroup$
  • $\begingroup$ I believe I followed that correctly, and it makes sense to me! Thanks $\endgroup$ – Ken Bassett Dec 17 '19 at 17:28
  • $\begingroup$ Well, if you followed it, you're one up on me. :-) $\endgroup$ – prubin Dec 18 '19 at 18:24
0
$\begingroup$

You can linearize the problem as follows. For $i\in\{1,\dots,4\}$ and $j\in\{1,\dots,1000\}$, let binary decision variable $z_{i,j}$ indicate whether station $i$ has $j$ workers, and let $r_{i,j}$ be a constant parameter that captures your nonlinear rate function. For example, $r_{1,j} = A\cdot j + B + C/j$. Then the problem is to maximize $\sum_i y_i$ subject to: \begin{align} \sum_j z_{i,j} &=1 &&\text{for all $i$}\\ x_i &= \sum_j j \cdot z_{i,j} &&\text{for all $i$}\\ y_i &= \sum_j r_{i,j} z_{i,j} &&\text{for all $i$}\\ \sum_i x_i &= 1000\\ x_i &\in \mathbb{Z}^+ &&\text{for all $i$}\\ z_{i,j} &\in \{0,1\} &&\text{for all $i,j$} \end{align} Or you can eliminate $x$ and $y$ and maximize $\sum_{i,j} r_{i,j} z_{i,j}$ subject to: \begin{align} \sum_j z_{i,j} &=1 &&\text{for all $i$}\\ \sum_{i,j} j \cdot z_{i,j} &= 1000\\ z_{i,j} &\in \{0,1\} &&\text{for all $i,j$} \end{align} Note that this formulation does not rely on concavity of the rate function.

$\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.