Consider the problem: max −x2 1 − x2 2 −3x1 − x2 ≤ −15 x1, x2 ≥ 0 and integral Suppose that the best known feasible solution for the problem is (x1, x2) = (4, 3). The continuous relaxation has the...

Consider the problem:

max −x2

1 − x2

2

−3x1 − x2 ≤ −15

x1, x2 ≥ 0 and integral

Suppose that the best known feasible solution for the problem is (x1, x2) =

(4, 3). The continuous relaxation has the optimal solution (x1, x2) = (4.5, 1.5)

with a Lagrange multiplier of 3 corresponding to the first constraint. Derive

an inequality that must be satisfied by any optimal solution. (Round up the

right-hand side, because the coefficients and variables are integral.)