How to Solve This Nonlinear Integer Program?

Question

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.

Answer 1

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.

Answer 2

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.