## 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