A question recently posted to
sci.op-research offered me a welcome respite from some tedious work that I’d rather not think about and you’d rather not hear about. We know that the greedy heuristic solves the continuous knapsack problem
to optimality. (The proof, using duality theory, is quite easy.) Suppose that we add what I’ll call a count constraint, yielding
where
. Can it be solved by something other than the simplex method, such as a variant of the greedy heuristic?
The answer is yes, although I’m not at all sure that what I came up with is any easier to program or more efficient than the simplex method. Personally, I would link to a library with a linear programming solver and use simplex, but it was amusing to find an alternative even if the alternative may not be an improvement over simplex.
The method I’ll present relies on duality, specifically a well known result that if a feasible solution to a linear program and a feasible solution to its dual satisfy the complementary slackness condition, then both are optimal in their respective problems. I will denote the dual variables for the knapsack and count constraints
and
respectively. Note that
but
is unrestricted in sign. Essentially the same method stated below would work with an inequality count constraint (
), and would in fact be slightly easier, since we would know a priori the sign of
(nonnegative). The poster of the original question specified an equality count constraint, so that’s what I’ll use. There are also dual variables (
) for the upper bounds. The dual problem is
This being a blog post and not a dissertation, I’ll assume that (2) is feasible, that all parameters are strictly positive, and that the optimal solution is unique and not degenerate. Uniqueness and degeneracy will not cause invalidate the algorithm, but they would complicate the presentation. In an optimal basic feasible solution to (2), there will be either one or two basic variables — one if the knapsack constraint is nonbinding, two if it is binding — with every other variable nonbasic at either its lower or upper bound. Suppose that
is an optimal solution to the dual of (2). The reduced cost of any variable
is
. If the knapsack constraint is nonbinding, then
and the optimal solution is
If the knapsack constraint is binding, there will be two items (
,
) whose variables are basic, with
. (By assuming away degeneracy, I’ve assumed away the possibility of the slack variable in the knapsack constraint being basic with value 0). Set
and let
and
. The two basic variables are given by
The algorithm will proceed in two stages, first looking for a solution with the knapsack nonbinding (one basic
variable) and then looking for a solution with the knapsack binding (two basic
variables). Note that the first time we find feasible primal and dual solutions obeying complementary slackness, both must be optimal, so we are done. Also note that, given any
and any
, we can complete it to obtain a feasible solution to (3) by setting
. So we will always be dealing with a feasible dual solution, and the algorithm will construct primal solutions that satisfy complementary slackness. The stopping criterion therefore reduces to the constructed primal solution being feasible.
For the first phase, we sort the variables so that
. Since
and there is a single basic variable (
), whose reduced cost must be zero, obviously
. That means the reduced cost
of
is nonnegative for
and nonpositive for
. If the solution given by (3) is feasible — that is, if
and
— we are done. Moreover, if the right side of either constraint is exceeded, we need to reduce the collection of variables at their upper bound, so we need only consider cases of
for
; if, on the other hand, we fall short of
units, we need only consider cases of
for
. Thus we can use a bisection search to complete this phase. If we assume a large value of
, the initial sort can be done in O(
) time and the remainder of the phase requires
iterations, each of which uses
time.
Unfortunately, I don’t see a way to apply the bisection search to the second phase, in which we look for solutions where the knapsack constraint is binding and
. We will again search on the value of
, but this time monotonically. First apply the greedy heuristic to problem (1), retaining the knapsack constraint but ignoring the count constraint. If the solutions happens by chance to satisfy the count constraint, we are done. In most cases, though, the count constraint will be violated. If the count exceeds
, then we can deduce that the optimal value of
in (4) is positive; if the count falls short of
, the optimal value of
is negative. We start the second phase with
and move in the direction of the optimal value.
Since the greedy heuristic sorts items so that
, and since we are starting with
, our current sort order has
. We will preserve that ordering (resorting as needed) as we search for the optimal value of
. To avoid confusion (I hope), let me assume that the optimal value of
is positive, so that we will be increasing
as we go. We are looking for values of
where two of the
variables are basic, which means two have reduced cost 0. Suppose that occurs for
and
; then
It is easy to show (left to the reader as an exercise) that if
for the current value of
, then the next higher (lower) value of
which creates a tie in (7) must involve consecutive a consecutive pair of items (
). Moreover, again waving off degeneracy (in this case meaning more than two items with reduced cost 0), if we nudge
slightly beyond the value at which items
and
have reduced cost 0, the only change to the sort order is that items
and
swap places. No further movement in that direction will cause
and
to tie again, but of course either of them may end up tied with their new neighbor down the road.
The second phase, starting from
, proceeds as follows. For each pair
compute the value
of
at which
; replace that value with
if it is less than the current value of
(indicating the tie occurs in the wrong direction). Update
to
, compute
from (7), and compute
from (5) and (6). If
is primal feasible (which reduces to
and
), stop:
is optimal. Otherwise swap
and
in the sort order, set
(the reindexed items
and
will not tie again) and recompute
and
(no other
are affected by the swap).
If the first phase did not find an optimum (and if the greedy heuristic at the start of the second phase did not get lucky), the second phase must terminate with an optimum before it runs out of values of
to check (all
). Degeneracy can be handled either with a little extra effort in coding (for instance, checking multiple combinations of
and
in the second phase when three-way or higher ties occur) or by making small perturbations to break the degeneracy.
