Last update: May 5, 2023

The Libre-Office ILP solver
An company has the opportunity of investing in n ∈ N+ different projects, if aproject j ( j ∈ {1, 2, . . . , n}) is selected it generates a profit p j ∈ R+ and it has a costs
w j ∈ R+ . The company has a total budget c ∈ R+ and its goal is to determine asubset of projects of maximum total profit that respects its budget.

Questions
1. Write a integer linear programming (ILP) model to determine a subset of projects of maximum total profit which can be selected by the company, i.e,. a subset of projects of total
cost no larger than the budget. Identify the decisions that must be taken and the corresponding decision variables. Identify and comment the objective function of the problem
and the constraints.
2. Consider now the instance in which there are five projects (n = 5) with the following profits and costs:
j

1

2

3

45

pj

8

6

1462

wj

33952

The budget of the company is c = 11.
Write the ILP model for this instance and find an optimal solution and the optimal solution value using the ILP solver of Libre-Office.
3. Consider now these additional constraints to be added to the ILP model of the previous
instance:• at most two out of the five projects can be selected;• if project 2 is selected, then project 4 must also be selected;• if project 1 is selected, then project 3 cannot be selected.
Find an optimal solution and the optimal solution value using the ILP solver of Libre-Office.

1

Solution
1. We introduce the following n binary variables:

xj =(1 if project j is selected∀ j ∈ {1, 2, . . . , n},0 otherwise

Using these variables, an ILP model for the problem reads as follows:

maxnX

pj xj

(1a)

w j x j ≤ c,(1b)j =1subject ton
Xj =1x j ∈ {0, 1},j ∈ {1, 2, . . . , n}.

(1c)The objective function (1a) maximizes the total profit of the selected projects. Constraint(1b) ensures that the budget is respected. Finally constraints (1c) define the variables ofthe ILP model.
2. The ILP model (1) for the specific instance reads as follows:max

8 x1+ 6 x2+ 14 x 3+ 6 x4+ 2 x5

3 x1+ 3 x2+ 9 x3+ 5 x4+ 2 x5≤

11x1 ,x2 ,x3 ,x4 ,x5∈{0, 1}

We now show how to compute an optimal solution of the ILP model for the previous instance using the ILP solver of Libre-Office. The spreadsheet of the model is presented
by the following figure, the yellow cells represent the values of the five variables of the ILPmodel.

2Using the SUMPRODUCT function, we can compute the objective function value of the problem in function of the values given to the variables and the objective-function vector asfollows:

Using again the SUMPRODUCT function, we can also compute the left-hand-side of the constraint in function of the values given to the variables and the constraint vector as follows:

The ILP solver of Libre-Office is then called as follows:3

The information of the model are given to the solver in the following manner:• the cell of the objective function value is put into the “Target cell”• the sense of the objective function is determined in “Optimize results to” (“Maximum” in this case)• the cells representing the values of the variables of the problem are put into “Bychanging cells”• the information related to the constraints of the model are given to the solver in thepart “Limiting conditions”. Each constraint is inserted by giving two cells, i.e., theleft-hand-side of the constraint and the right-and-side of the constraint. Then thetype of the constraint is imposed (in this case “≤”).
• finally, since all the variables are binary, the cells of the values of the variables are set
as “Binary”

4Pressing the button“Solve”, the solver computes an optimal solution and the optimal solution value of the ILP model as shown in the following figure:An optimal solution is:
x 1∗ = 1, x 2∗ = 1, x 3∗ = 0, x 4∗ = 1, x 5∗ = 0.
The optimal solution value is z( ILP ) = 20
3. The ILP model with the additional constraints reads as follows:max

8 x1+ 6 x2+ 14 x 3+ 6 x4+ 2 x53 x1+ 3 x2+ 9 x3+ 5 x4+ 2 x5≤

11x1+ x2+ x3+ x4+ x5

≤

2≤0≤

1

∈

{0, 1}

x2x1x1 ,− x4+ x3x2 ,x3 ,5x4 ,x5The spreadsheet of the model is presented by the following figure:

The constraints can be inserted altogether as follows:6And this is the new optimal solution and the optimal solution value of the ILP model withthe additional constraints:

A new optimal solution is:
x 1∗ = 0, x 2∗ = 0, x 3∗ = 1, x 4∗ = 0, x 5∗ = 1
The new optimal solution value is z( ILP ) = 16.

7