Scribd
Upload
17 views3 pages

IPexercises

The document contains exercises on Integer Linear Programming (ILP) that involve modeling various project selection scenarios to maximize returns, capital investment portfolios with constraints, and product production optimization for profit maximization. It also includes exercises on the branch-and-bound method for solving ILP problems and an application of ILP in solving Sudoku puzzles. Each exercise requires formulating the problem as an ILP and implementing solutions using computational tools like ZIMPL and LP solvers.

Uploaded by

Minh Đức Nguyễn
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
17 views3 pages

IPexercises

The document contains exercises on Integer Linear Programming (ILP) that involve modeling various project selection scenarios to maximize returns, capital investment portfolios with constraints, and product production optimization for profit maximization. It also includes exercises on the branch-and-bound method for solving ILP problems and an application of ILP in solving Sudoku puzzles. Each exercise requires formulating the problem as an ILP and implementing solutions using computational tools like ZIMPL and LP solvers.

Uploaded by

Minh Đức Nguyễn
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Exercises on

Integer Linear Programming

Modeling as integer linear programs


Exercise 1. There are four possible projects, which each run for 3 years and
have the following characteristics (the money unit in the table is 1.000.000 USD).

Capital requirements
Project Return
Year 1 Year 2 Year 3
Project 1 0.2 0.5 0.3 0.2
Project 2 0.3 1.0 0.8 0.2
Project 3 0.5 1.5 1.5 0.3
Project 4 0.1 0.1 0.4 0.1
Available capital 3.1 2.5 0.4

Table 1: Parameters for Exercise 1.

(i) Formulate the following problem as an integer linear programming: Which


projects would you choose in order to maximize the total return?
(ii) Assume an additional condition that either project 1 or project 2 must be
chosen (i.e., project 1 and project 2 are mutually exclusive). Re-formulate the
problem as an integer linear programming.

Exercise 2. A project manager in a company is considering a portfolio of 10 large


project investments. Let pi and ci denote the estimated profit and capital required
for investment opportunity i(i = 1, . . . , 10) respectively. The total amount of
capital available for these investments is Q. Investment opportunities 3 and
4 are mutually exclusive and so are 5 and 6. Furthermore, neither investment
opportunity 5 nor 6 can be undertaken unless either investment opportunity 3 or 4
is undertaken. At least two and at most four investment opportunities have to be
undertaken from the set {1, 2, 7, 8, 9, 10}. The project manager wishes to select
the combination of capital investments that will maximize the total estimated
profit subject to the restrictions described above. Formulate this problem using
an integer linear programming model.

Exercise 3. A company is attempting to decide the mix of products which it


should produce next week. It has seven products, each with a profit (USD) per
unit and a production time (man-hours) per unit as shown in Table 2.

1
2

Product Profit Production time


1 10 1.0
2 22 2.0
3 35 3.7
4 19 2.4
5 55 4.5
6 10 0.7
7 115 9.5

Table 2: Parameters for Exercise 3.

The company has 720 man-hours available next week.


(i) Formulate the following problem as an integer linear program: How many
units of each product should be produced next week in order to have maximum
profit?
(ii) Incorporate the following additional restrictions into your integer linear
program (retaining linear constraints and a linear objective):
• (C1) If any of product 7 are produced an additional fixed cost of 2000 USD
is incurred.
• (C2) Each unit of product 2 that is produced over 100 units requires a
production time of 3.0 man-hours instead of 2.0 man-hours (for example,
producing 101 units of product 2 requires 100 * 2.0 + 1 * 3.0 = 203 man-
hours).
• (C3) If both product 3 and product 4 are produced, then 75 man-hours
are needed for production line set-up and hence the (effective) number of
man-hours available falls to 720 - 75 = 645.

Branch-and-bound method in 2D
Exercise 4. Illustrate the branch-and-bound algorithm at the IP

max x1 + x2
s.t. 4x1 − 2x2 ≥ 1
4x1 + 2x2 ≤ 11
2x2 ≥ 1
x1 , x 2 ∈ N

Exercise 5. Illustrate the branch-and-bound algorithm at the IP

max x1 + 2x2
s.t. 2x1 + x2 ≤ 8
− x1 + 2x2 ≤ 5
x1 , x 2 ∈ N
3

IP solver
Exercise 6. Implement the problems in Exercise 1 and Exercise 3 to your com-
puter by using ZIMPL and then solve them by using some LP solver (e.g. SCIP).

Exercise 7. This exercise is to show an application of integer linear programming


in solving Sudoku puzzles. A Sudoku puzzle can be described as follows. Give a
grid consisting of 9 × 9 squares (cells), which can also be viewed as a composition
of nine 3 × 3 blocks (so-called sub-grids). The puzzle rules are:

(1) each cell of grid must be filled by exactly one digit from 1 to 9;

(2) each digit in {1, . . . , 9} appears exactly once in each column, each row, and
each 3 × 3-block.

Usually, a Sudoku puzzle is provided with a partially complete grid, and the
objective is to completely fill the grid.
(i) Model the problem of solving a Sudoku puzzle as an integer linear program.
Hint: use the binary variables
{
1 if k is filled in the cell (i, j) of the grid,
xijk =
0 otherwise.

(ii) Implement your model into compute by using ZIMPL, and then use some
IP solver (e.g. SCIP) to solve the model for the puzzle given in Figure 1. Show
your obtained solution in form of a completely filled Sudoku grid.

8 9
1 3 9
5 2 4
2 6 8
9 7 6 5
3 6 5
1 3 5
8 7 1
4 5

Figure 1: Sudoku puzzle as a test instance for Exercise 7.

You might also like