A useful bound need not be a feasible solution
For a maximization problem, a feasible selection gives a lower bound on the optimum. To prove it is optimal, we also need an upper bound on every feasible selection. Relaxing a difficult constraint can make the remaining optimization easier, provided its violation is priced with the correct sign.
Let for finitely many items, with integer weights , integer values , and integer capacity . The original problem maximizes subject to . The empty selection is feasible. We use exact arithmetic.
Price the capacity
Definition 3.3.1
(Lagrangian and dual function)
For a multiplier and a binary vector , the Lagrangian of the capacity constraint is
The dual function is , a maximum over all binary vectors, feasible or not. Only multipliers are used for bounds.
Theorem 3.3.2
(Lagrangian weak duality for the knapsack constraint)
For every ,
and every feasible satisfies . In particular the optimum of the original problem is at most .
Proof
(Drop the constraint, keep its price)
Write . The coordinates of can then be chosen independently: include item when its coefficient is positive, exclude it when negative, and either choice gives the same value at zero. This gives the displayed formula for .
For a feasible , the factor is nonnegative and , so the added term is nonnegative and . Since is one of the binary vectors over which maximizes, . Combining the two inequalities proves the bound, and it holds for every simultaneously.
Proof X-ray
Where the upper-bound direction comes from
The proof uses each ingredient once. The sign condition enters only in the first inequality, where it makes the price of unused capacity nonnegative; the binary restriction is kept on both sides; and the second inequality holds only because dropping the capacity constraint enlarges the set being maximized over. A negative multiplier reverses the first inequality and need not give an upper bound. With one item , and , the relaxed maximum is ; this number happens to be an upper bound, but the argument is invalid. With the same item and , it becomes , below the feasible value one.
The independent choices in the proof may exceed capacity. That does not invalidate the upper bound, because a larger set of choices was used; it does mean that a maximizer of is not automatically a feasible knapsack solution. A bound becomes a proof of optimality only when a feasible selection meets it.
Corollary 3.3.3
(An integer rounding certificate)
Suppose every is an integer, is feasible with value , and for some . Then is optimal.
Proof
(Integer objectives below the next integer)
Every feasible objective value is an integer, because the and are integers, and by weak duality it is at most . An integer smaller than is at most , which attains.
A numerical certificate
Worked example 3.3.4
(Certifying a two-item optimum)
Take two items of weights and values , with capacity . Choosing item 2 alone is feasible and has value four. At ,
Thus every feasible value is at most . Since all values are integers, every feasible objective is an integer, so it is at most . The feasible item-2 selection attains four and is optimal; in the language of the corollary, .
Counterexample mode
The relaxed maximizer need not be feasible
At , item 1 has positive adjusted value and item 2 has adjusted value zero. Selecting both is a valid maximizer of , but their weight is five, exceeding capacity three. The upper bound remains valid; this relaxed maximizer cannot itself serve as the feasible lower-bound witness.
Rounding is justified by integrality of the objective, not merely by integrality of the decision variables.
Common mistake
(Rounding a bound when the values are not integers)
Change the second value in the example to . Item 2 alone is still feasible, with value , and at
Rounding down would claim that every feasible value is at most , which the feasible value contradicts. With real values the bound may be used only as it stands.
Choosing a multiplier
Every nonnegative multiplier gives a valid bound. A smaller upper bound is stronger, but finding one good multiplier does not prove that it minimizes . The pointwise expression is piecewise linear in ; its minimum can retain a gap from the integer optimum before an additional argument such as objective rounding. The method is useful in a certificate or branch-and-bound calculation, but the model, multiplier sign and retained constraints must be stated.
Worked example 3.3.5
(The best multiplier can leave a gap)
For the two-item example, , with breakpoints at and . On each piece,
The first piece decreases and the other two increase, so the minimum over is . Even the best Lagrangian bound exceeds the optimum four by . The certificate in the previous example needed the rounding step; no choice of multiplier removes it.
Worked example 3.3.6
(A multiplier that closes the gap)
Take two items with each and , so the optimum is one. Here , which equals on and for . The minimum is , equal to the optimum, so a single feasible item is certified without rounding. At both adjusted values are zero, so every binary vector maximizes ; among these maximizers, each singleton happens to be feasible.
Exercises
Quick check
(For the two-item example, calculate and compare it with the feasible value four.)
Solution · Answer
, an upper bound above the feasible value four.
Quick check
(At , calculate for and explain why it is not an original feasible selection.)
Solution · Answer
Its original value is seven and its weight is five. Thus ; weight five violates capacity three.
Quick check
(With , a single item of weight one and value two, compute and .)
Solution · Answer
and . The only feasible selection is empty, of value zero, so the second bound is exact.
Quick check
(Why can we round down in the example, and why is the same step unsafe for arbitrary real values?)
Solution · Answer
Every original objective is an integer when all and are integers. A real-valued objective can lie strictly between four and , so rounding down could eliminate a valid value.