MATP6620 / ISYE6760 Integer and Combinatorial Optimization
Homework 4.
Solutions
Due: Thursday, March 18, 2021, by end of day.
Penalty for late homeworks: 10% for each day or part of a day.
| (1) |
When x_{2} = 1, we have the valid constraint
| (2) |
Lift the inequality to give a valid inequality for S. (Hint: consider a change of variables z_{2} := 1 - x_{2}. Make sure you convert your constraint back to the x variables.)
Solution:
With the given change of variables, (1) is equivalent to the constraint
or equivalently
| (3) |
This is now in our framework for lifting: we have a valid constraint (2) in x_{1}, x_{3}, x_{4} when z_{2} = 0. To find the lifting coefficient, we solve:
achieved by multiple solutions including x_{1} = 0, x_{3} = 1, x_{4} = 0, z_{2} = 0. Hence the lifting coefficient is 2 - ζ = 1, so the lifted constraint is
Expressing this in terms of the original variables, we have the valid constraint
or equivalently
where a,c ∈ ℤ_{+}^{n}. Assume a_{j} ≤ b for j = 1,…,n. Let S denote the set of feasible solutions.
Solution:
so a_{k} = _{i}, k ∈ N_{i}.
Assume a_{j} ≤ b - _{i} for every j ⁄∈ N_{i}. Then each j ⁄∈ N_{i} is in the valid solution {j,k}.
The incidence vectors of the given n packings are linearly independent, so they are affinely independent, so the given constraint defines a facet provided the assumption holds.
| (4) |
is a valid inequality. Let {j(i)} = C ∩ N_{i} when C ∩ N_{i}≠∅. Prove the following inequality is also valid:
Solution:
Because of the constraint that at most one item can be picked from each subset, we must have
with equality only if exactly one item j with a_{j} ≥ a_{j(i)} is chosen from each set N_{i}.
If exactly one such item is picked from each set N_{i} with |C ∩ N_{i}| = 1 then
since C is a cover. Hence it is not possible to pick exactly one item from each set N_{i} with the item j from set N_{i} satisfying a_{j} ≥ a_{j(i)}, so the constraint in the question is valid.
Solution:
Lifting on x_{1} and then x_{4} gives the facet defining inequality
Lifting in the other order gives the same inequality.
Lifting on x_{1} and then x_{3} gives the facet defining inequality
Lifting in the other order gives the same inequality.
Lifting on x_{1} and then x_{4} gives the facet defining inequality
Lifting in the other order gives the same inequality.
Solution:
There exist multipliers λ_{1},…,λ_{m}, not all zero, with
It follows that
Hence, ∑ _{i=1}^{m}λ_{i} = 0 so the vectors are affinely dependent.
John Mitchell |
Amos Eaton 325 |
x6915. |
mitchj at rpi dot edu |
Office hours: Monday and Thursday 1pm–2pm. |
webex: https://rensselaer.webex.com/meet/mitchj |