Description
Problem 1 (30pts).
Use the branch-and-bound method to solve the following integer program.
maximize 2x + y
subject to −3x + 2y ≤ 5
−x − 2y ≤ −2
5x + 2y ≤ 17
x, y ∈ Z.
You are allowed to use an LP solver to solve each of the relaxed linear program. Please specify the
branch-and-bound tree and what you did at each node .
Problem 2 (30pts).
Consider a seller who sells m different products. For product j, there are Bj units in inventory.
There are n customers, each customer i is interested in buying a bundle of the product Si
, where
Si ⊆ {1, …, m} and is willing to pay a price vi for it. For each customer, the seller can only decide
to accept his entire request Si or reject him. The objective of the seller is to maximize the revenue.
• Formulate this problem as an integer program.
• Consider the following example B1 = 1, B2 = 2, B3 = 3, S1 = {1, 2}, v1 = 2, S2 = {3},
v2 = 1, S3 = {1, 3}, v3 = 3, S4 = {2, 3}, v4 = 2, S5 = {2}, v5 = 2. What is one of the optimal
solution to the LP (Linear programming) and IP respectively? What is the integrality gap?
Problem 3 (40pts).
Suppose we have a set of n many items and a set of m different knapsacks. For each item i and
knapsack j, the following information is given:
1
• The item i has value (preference) vi
.
• The weight of item i is ai
.
• The capacity of knapsack j is at most Cj .
a) Formulate an integer program to maximize the total value of items that can be packed in the
different knapsack while adhering to the capacity constraint (i.e., the total weight of items in
each bag j is not allowed to be larger than Cj ).
Hint: You can introduce variables xij to denote whether item i is placed in knapsack j.
b) Consider the following list of items and bags:
Item Laptop T-Shirt Swim. Trunks Sunglasses Apples Opt. Book Water
Value 2 1 3 2 1 4 2
Weight 2 0.5 0.5 0.1 0.5 1 1.5
Knapsack 1 Knapsack 2
C1 = 3 C2 = 2
Formulate the corresponding IP in that case. What are the optimal solutions to the IP and
its LP relaxation (you can use MATLAB or CVX to solve the problems)? Is there an integrality
gap in this case?
2
