CHAPTER 1: Modelling

Question 1

LINEAR PROGRAMMING PROBLEM

Answer 1

optimization problem/ function max min and constraints with LINEAR function of vars

Question 2

EXAMPLE 1.1: Simple LPP

Answer 2

Example 1.1. A simple LPP may go like the following: Find the maximum of function
z = 5x_1 + 6x_2 + 2x_3

subject to constraints:
x_1 + x_2 + x_3 ≤ 10
2x_1 + 4x_2 + 7x_3 ≤ 6
x_1, x_2, x_3 ≥ 0

The function z is the objective function or cost function

Question 3

EXAMPLE 1.2:

Example 1.2 (Product-Mix Problem, aka the Reddy-Mikks problem). A paint factory makes 2 types of paints, of exterior (E) and interior (I) quality, respectively.

Two types of raw materials, A and B, are used in each paint.
The following information is known:

1. Availability of A is 6 tons/day, and of B is 8 tons/day.
2. Producing 1 ton of paint E needs one ton of A and 2 tons of B.
3. Producing 1 ton of paint I needs two tons of ingredient A and one ton of B.
4. The daily production for paint I should not exceed that for paint E by more than 1 ton (according to a market survey).
5. Maximum demand for paint I is 2 tons/day.
6. The net selling prices are £300 per ton for paint E and £200 per ton for paint I.

Determine the daily production strategy (that is, how much E and I to be produced each day?) to maximise the revenue.

Answer 3

Solution. Let x_1 be the amount of paint E produced per day, x_2 that of paint I, and z be the revenue per day,

we can derive the LPP:

max z = 3x_1 + 2x_2 (unit £100)
subject to
x_1 + 2x_2 ≤ 6
2x_1 + x_2 ≤ 8
−x_1 + x_2 ≤ 1
x_2 ≤ 2

with x_1, x_2 ≥ 0

Question 4

Example 1.3 (The diet problem). Suppose a dietician wishes to design a diet, which minimizes the cost of
meeting our daily requirements of calcium, vitamin C, and iron, with foods restricted to apples, bananas,
carrots, dates, and eggs. The nutrient values and cost of a unit of each of these foods are given in the following
table.

**Calcium, Vit C and iron in (mg/unit), Cost in (pence/unit)
          Calcium Vit C Iron Cost
Food 
Apples    0.4  6  0.4   8
Bananas 1.2  10  0.6  10
Carrots   0.6  3   0.4   3
Dates     0.6   1   0.2  20
Eggs     12.2   0  2.6  15

The daily diet requires at least 900 mg of calcium, 50 mg of vitamin C, and 12 mg of iron. We assume that the supply of these foods is unlimited. How should the dietician determine the optimal way to meet the three daily requirements?

Answer 4

Solution. The five types of foods are denoted by A, B, C, D, and E, respectively. Let xi be the number of units
of food i (i = A, B, C, D, E). The cost in pence is
z =
8x_A+10x_B+3x_C+20x_D+15x_E.

The constraints are
0.4x_A + 1.2x_B + 0.6x_C + 0.6x_D + 12.2x_E ≥ 900

6x_A + 10x_B + 3x_C + x_D ≥ 50
0.4x_A + 0.6x_B + 0.4x_C + 0.2x_D + 2.6x_E ≥ 12

The optimal combination is found as the solution of this LPP where we minimise z subject to the constraints.

*for each apple there is 0.4 mg calcium, for each banana 1.2,…

Question 5

EXAMPLE 1.4:
(The dual problem of the diet problem). A salesman selling nutrient tablets tries to convince the
dietician to use tablets to replace the diet. Each tablet contains only one nutrient, and only one mg of that nutrient.
The dietician will not be interested if the tablets are more expensive than the foods. Specifically, he needs the cost of buying the tablets providing all the nutrients in one unit of one type of foods to be NO greater than the unit cost of that type of foods. This stringent requirement gives him more flexibility in using the tablets to design other diets if it is needed.

How should the salesman set the prices for the tablets to maximise his profit while meeting both the dietician
requirement and the daily nutritional requirements?

Answer 5

*for each vitamin cost is governed by costs of the foods providing the amounts of vitamin: for an apple 0.4 of cost of calcium, 6 for vit c,… less than cost of apple
Solution.

• we assume selling maximum number for daily nutrition
  ****
  Let us assume that the unit prices for the tablets chosen by the salesman are y_1 for calcium, y_2 for VC,
  and y_3 for iron tablets, respectively. The total daily profit from selling the tablets is
  v = 900y_1 + 50y_2 + 12y_3.

The coefficients come from the minimum daily requirements for the nutrients. The cost to provide the nutrients
in a unit of apple is (using the data in the first row in the table above):
0.4y_1 + 6y_2 + 0.4y_3
which has to be less than the unit cost of apples as required by the dietician. Therefore, the 1st constraint is

0.4y_1 + 6y_2 + 0.4y_3 ≤ 8

We may obtain four more constraints in a similar way. Finally the whole set of the constraints is

0. 4y_1 + 6y_2 + 0.4y_3 ≤ 8
1. 2y_1 + 10y_2 + 0.6y_3 ≤ 10
2. 6y_1 + 3y_2 + 0.4y_3 ≤ 3
3. 6y_1 + y_2 + 0.2y_3 ≤ 20
4. 2y_1 + 2.6y_3 ≤ 15

The salesman will attempt to maximise v subject to the above constraints

Question 6

NOTES:

2 diet problem examples

Answer 6

The LPP in Ex. 1.4 is symmetrical to the LPP in Ex. 1.3 in several aspects. The coefficient matrices in
the constraints in the two problems are conjugate to each other. The numbers on the right-hand sides of the
constraints in one LPP appear as the coefficients in the cost function of the other. We say the LPP in Ex. 1.4 is
the dual problem of the one in Ex. 1.3, and vice versa; the two LPPs are dual to each other.

Question 7

INTEGER PROGRAMMING PROBLEMS

Answer 7

Integer programming problems (IPP) are optimization problems in which some of the variables can take only integer values. Technically speaking, the functions involved in an IPP can be nonlinear

Question 8

EXAMPLE 1.5:

(Knapsack problem). An aeroplane can carry up to W kg of cargo on a scheduled flight. There
are n different items that could be transported with item i weighing aikg and providing a profit of £ci
if transported. What items should be shipped to maximise the profit?

Answer 8

Solution. Define n binary integer variables yi such that
y_i =
{1 if the i th item is shipped
{0 if the i th item not shipped

The corresponding Integer Programming model is
Maximise
n
∑
i=1
[c_iy_i]

subject to
n
∑
i=1
[a_iy_i]
 ≤ W.

Question 9

Example 1.6 (Extension to the knapsack problem). Suppose that two additional restrictions are added to the
problem:
• Item 2 cannot be shipped unless Item 1 is also shipped
• Items 3 and 4 cannot be shipped together.
What is the best strategy now?

Answer 9

Solution. We have to add the following constraints:
y_2 ≤ y_1 and y_3 + y_4 ≤ 1

y_i is binary. Thus y_2 ≤ y_1 is true only in the following three cases:

y_1 = 1, y_2 = 0 or y_1 = 1, y_2 = 1 or y_1 = 0, y_2 = 0

Thus y_2 cannot be 1 if y_1 is not 1, which is exactly the same as the first restriction. As for the 2nd restriction,
y_3 + y_4 ≤ 1 means only one of the two can be 1, which means the two items cannot be shipped together, as required.

• this is not 1 can’t be shipped unless 2 is

Question 10

EXAMPLE: Example 1.7 (Capital budgeting). Five projects are being evaluated over a 3-year planning horizon. The following table gives the expected returns for each project, the associated yearly expenditures, and the available funds in each year (all numbers are in million pounds).

columns:
Project: 1/2/3/4/5/6/
Expenditure  in Y1: 5/4/3/7/8/ Expenditure in Y2:1/7/9/4/6/
Expenditure in Y3: 8/10/2/1/10/
Return: 20/40/20/15/30/

Available funds: 25 for Y1, 30 for Y2, 30 for Y3

Which projects should be selected over the 3-year horizon to maximise the total return?

Answer 10

Introduce binary variables:
y_i =
{1 if project i is selected
{0 o/w

i=1,2,3,4,5

cost funct
z =
20y_1+40y_2+20y_3+15y_4+30y_5

found from returns of the vars

constraints for functs in each year

Total invest in year 1:
5y_1+4y_2+3y_3+7y_4+8y_5 ≤ 25
Total invest in year 2:
y_1+7y_2+9y_3+4y_4+6y_5 ≤ 30
etc

Question 11

Example 1.8 (Set-covering problem). The University is in the process of installing emergency telephones at
selected locations around the campus. It wants to install the minimum number of phones provided each main street
is served by at least one phone box. Fig. 1.1 gives a schematic of the layout of the streets. It is logical to install the
phones at street intersections so that each phone can serve at least two streets. Therefore there are 8 possible
phone locations as is marked in the figure. Which locations should the University choose?

Remark. In general, set-covering problems deal with the situation where certain services are provided to several
sites by a number of service hubs. The objective is to minimize the number of service hubs. The service hubs
should cover all the sites, hence the name ‘set-covering problem’.

Answer 11

GIVEN MAP with streets and any intesections numbered

Introduce binary variables:
y_i =
{1 if location i is chosen
{0 o/w

i=1,2,3,4,5,6,7,8

Minimize

z= sum from i=1 to 8 of y_i

(number of phones minimized)

(from map)
#phones serving street A:
y_1+y_2 ⩾ 1
#phones serving street B:
y_2+y_3 ⩾ 1

etc
y_4+y_3 ⩾ 1
y_7+y_8 ⩾ 1
y_6+y_7 ⩾ 1
y_2+y_6 ⩾ 1
y_4+y_7 ⩾ 1
y_2+y_4 ⩾ 1
y_3+y_8 ⩾ 1
y_3+y_5 ⩾ 1
setting vars vs locations vs how many phones
(more than or equal to)

Question 12

Example 1.9 (Travelling salesman problem (TSP)). Starting from his home, a salesman wishes to visit each of
n − 1 other cities and return home at minimum cost. He must visit each city exactly once and it costs cij to
travel from city i to city j. What route should he select?

Answer 12

WON’T BE ON EXAM

a tour visiting each city once is a hamiltonian cycle we want one which minimises the cost

Let x_ij=
{1 if salesman travels i to j
{0 o/w

we minimize
z= Σ over {i,j=1 , n}of [c_ijx_ij]
= Σ{i=1,n}Σ{j=1,n}c_ijx_ij

subject to:

1)Σ{j=1,n} of x_ij =1 for i=1,2,…,n
ie can visit only one city starting from city i

2)Σ{i=1,n} of x_ij =1 for j=1,2,…,n
ie each city can be visited once and only once

(For each j only one i, city is i

We eliminate tours which arent hamiltonan cycles)

3)
To remove a subtour sol:
Σ{j=1,n}

x_14+x_15+….+… is bigger than equal to 1

3 forces a link

(one in and one out and all visited)

if no constraint then we are allowed to visit more than once and conditions imposed on each J don’t allow this

subtour examples: 1 to 2 to 3 to 1… and 5 to 4 to 6 to 5…

In graph theories, such a route (or tour) is called a Hamiltonian cycle. The objective of the TSP is to
find the Hamiltonian cycle with minimum cost.

Question 13

EITHER-OR PROBLEMS
Example 1.11 (Either-or problem). Suppose that we maximize or minimize z (the expression of z is not important here) such that

EITHER
g^T_1x ≤ b_1 is imposed, (1.1)
OR
g^T_2x ≤ b_2 is imposed, (1.2)

where x ≥ 0. g1, g2 and x are vectors, whereas b1, b2 ≥ 0 are two numbers.
Find a set of simultaneous constraints that is equivalent to the above “either-or” constraint.

Answer 13

*The constraints can be written as
g^T_1x − b_1 ≤ 0
and
g^T_2x − b_2 ≤ 0.

We introduce a 0-1 variable y. The two simultaneous inequalities below then are equivalent to the above either-or constraint:
g^T_1x − b_1 ≤ My
g^T_2x − b_2 ≤ M(1 − y)

where M > 0 is a sufficiently large number

• even if a constraint is NOT imposed, it could still be satisfied by a given feasible solution.
• as M is a large number means that constraint isnt imposed if RHS is non-zero
• if one is false the other must be true (converse not true)
• constraints are Active or inactive depending on the solution and we use binary variables to switch between

Question 14

Example 1.10 (Either-or problem). A machine is used to produce two products. The daily capacity of the
machine can produce at most 20 units of product 1 and 10 units of product 2. Alternatively, the machine can
be adjusted to produce at most 12 units of product 1 and 25 units of product 2 daily. Market analysis shows
that the maximum daily demand for the two products combined is 35 units. Given that the unit profits for the
two products are £10 and £12, respectively, which of the two machine settings should be chosen? Formulate
the problem as a mixed ILP.

Answer 14

Let x_i (i=1,2) be the #products i to be made

maximize
z=10x_1+12x_2

subject to

1) x_1+x_2 ≤ 35

2)
x_1≤ 20, x_2≤ 10 (SETTING 1)
OR
x_1≤ 12, x_2≤ 25 (SETTING 2)

thus introduce binary variable y=
{1 if setting 2
{0 if setting 1

where M is suitably largy positive #
x_1-20≤ My, x_2-10≤ My
x_1-12 ≤ M(1-y), x_2-25≤M(1-y)

constraints become:
x_1-20≤ My, 
x_2-10≤ My
x_1-12 ≤ M(1-y), 
x_2-25≤M(1-y)
x_1+x_2 ≤  35

Question 15

Example 1.12 (If-then problem). Three products are manufactured in a plant. The labour and raw material
requirements for the products are given in the following table.
Product / Required daily labour/ Required daily raw material

(hr/unit) (kg/unit)

1 /3/ 4
2/ 4/ 3
3/ 5/ 6

Daily availability 100 100
The profits per unit for the three products are £25, £30 and £45, respectively. If product 3 is to be manufactured
at all, then its production level must be at least 5 units daily. Formulate an MILP to find the production
schedule to maximise the total profit.

Answer 15

we maximise total profit

Z=25X_1+30X_2+45X_3

defined binary X_i ie 1 if products i to be made

subject to

2x_1+4x_2+5x_3 ≤100
4x_1+3x_2+6x_3 ≤100

if x_3 bigger than 0
then x_3 ≥ 5
becomes

x_3 ≤ My
5-x_3 ≤M(1-y)

where y is a binary var and M a suitably large #

Question 16

PIECEWISE LP PROBLEMS

Answer 16

some of the functions in the formulation are piecewise linear. On the other
hand, in some optimisation problems we might have to introduce nonlinear functions. In this case, we may use piece-wise linear functions to approximate the nonlinear functions, hence again obtain piecewise linear
programming problems

suitable binary variables to identify each linear ‘pieces’.

Question 17

Example 1.14. Consider maximisation problem max z = min(M, x), subject to x ≤ b and x ≥ 0, where M > 0
is a number. For simplicity, we assume x and b are numbers. The function min(M, x) is piecewise linear in x:
it equals x when x ≤ M, and equals M when x > M. We can find an equivalent LPP to this piecewise LPP.

Answer 17

Solution. If we introduce an auxiliary variable e ≥ 0 and let e = min(M, x), then obviously the original problem
is the same as

max z = e,

subject to
e = min(M, x),
e ≥ 0, and
x ≤ b.

However, this problem is not an LPP (yet). Fortunately, without changing the optimal solution, the constraint
e = min(M, x)

can be relaxed to the weaker constraints e ≤ M and e ≤ x.

To summarize, the piecewise LPP is equivalent to the following LPP:
max z = e, 
subject to 
e ≤ M, 
e ≤ x, 
e ≥ 0, and 
x ≤ b,
where e is the auxiliary variable. 

The two problems are obviously different, but they are equivalent in the sense
that, if (e∗, x∗) is an optimal solution of the latter (the LPP) with
zmax = z∗, then x∗
is an optimal solution of
the former (the piecewise LPP) with same zmax = z∗

We use the following heuristic argument to show that the conversion makes sense. The first two constraints in the LPP are equivalent to one single inequality:
e ≤ min(M, x).

Since we will maximize e and there is no
other constraint on e, e must reach its upper bound at the optimum, hence
e∗ = min(M, x∗).

Thus the relation e = min(M, x) is recovered at the optimum.

Question 18

Example 1.15.
Consider min z =
∑ from i=1 to N of
[|bi − xi|]

with constraint
Ax ≤ b
and
x ≥ 0.

The absolute value function
is a piecewise linear function, therefore this is a piecewise LPP. We can find an equivalent LPP to this piecewise LPP.

Answer 18

Solution. Note the absolute value function can be converted to a maximum function: |x| = max(x, −x). The
max function can be dealt with in the same way as in the previous example.

We introduce auxiliary variables
ei ≥ 0 (i = 1, 2, …, N).

The equivalent LP problem is:
min z = ∑i [ei]

subject to
e_i ≥ b_i − x_i
e_i ≥ −(b_i − x_i), 
e_i ≥ 0, Ax ≤ b,
x ≥ 0 

(i = 1, 2, …, N).

Question 19

Example 1.16 (Job Sequencing Model). A factory uses a single machine to process three jobs. The machine can
only process one job at a time. The processing time, the due date (in days), and the late penalty per-day for
each job are given in the following table. The due dates are measured from zero, the assumed starting time of
the first job.

Job/ Processing time pi (days)/ Due date d_i (Days) /Late penalty l_i £/day

1/5/25/19
2/ 20/ 22/ 12
3/ 15/ 35/ 34
In the table we have used di, p_i, and l_i
to denote the due date, processing time, and daily late penalty for job
i (i = 1, 2, 3). The objective of the problem is to determine the minimum late-penalty sequence for processing
the jobs. Formulate the problem as a mixed ILP.

Answer 19

we define the job sequence by the starting dates of the jobs.

let x_i be the starting date of job i. (i=1,2,3)
then x_1,x_2,x_3 define the job sequence

For example (x_1,x_2,x_3) = (10,1,6) means job 2 Starts first, then job 3 then job 1 as
x_2 is less than x_3  is less than x_1

Let p_i =processing days for job i
d_i=due date
l_i= late penalty per day

then the late penalty associated with job i is:

(x_i + p_i -d_i) l_i

( as x_i +p_i is finishing date and delay in days is x_i +pi- d_i)

however there is only a penalty when the job is delayed i e only when x_i +pi- d_i is bigger than 0

penalty should be:
max{0, (x_i +pi- d_i)l_i}

and total late penalty:

Z= sum from i=1 to 3 of
[max{0, (x_i +pi- d_i)l_i}]

the cost function is piecewise linear. We will deal with this later. The only constraint is that the machine can process only one job.before a job can be started only when the previous job has finished.consider job i and job j. There are two possibilities:

***if job i starts before job j, then the starting date of job j needs to be larger than the finishing date of job i thus,
x_j ≥ x_i +p_i
start date for j ≥ finishing date for i

i ≠j

(because dates are measured from 0 finishing date of x_i is x_i +p_i -1)

***if job j starts before job i,
x_i ≥ x_j +p_j
i ≠j

Thus, it’s either x_i +p_i - x_j ≤0 or x_j +p_j - x_n ≤ 0.

introducing binary variables y_ij , i ≠j
the either-or constraint becomes:
x_i +p_i - x_j ≤ M y_ij
x_j +p_j - x_n ≤ M(1 - y_ij)

for x_i ≥0, x_j ≥0
i ≠j
i=1,2,3
j=1,2,3

continued

Question 20

JOB SEQUENCING PROBLEM

SOLUTION CONT

Answer 20

the problem is equivalent to LPP:

min z = sum from i=1 to 3 of [e_i]

subject to
*e_i ≥ l_i (x_i +p_i - d_i)
(i=1,2,3)
*e_i ≥0
(i=1,2,3)
*x_i +p_i - x_j ≤ M y_ij
i ≠j, i=1,2,3 j=1,2,3
*x_j +p_j - x_n ≤ M(1 - y_ij)
i ≠j, i=1,2,3 j=1,2,3

For given data, there are 3 pairs:

(1,2), (1,3),(2,3)
min z =e_1 +e_2+e_3

e_1 ≥19(x_1 -20)
e_1 ≥12(x_2 -2)
e_1 ≥34(x_3 -20)

x_1 + 5 -x_2 ≤My_{1,2}
x_2 + 20 -x_1 ≤M(1-y_{1,2})
x_1 + 5 -x_3 ≤My_{1,3}
x_3 + 15 -x_1 ≤M(1-y_{1,3})
x_2 + 20 -x_3 ≤My_{2,3}
x_3 + 15 -x_2 ≤M(1-y_{2,3})

with x_i≥ 0, e_i ≥0 and y_12, y_13, y_23 being binary

Question 21

IF THEN PROBLEM

Answer 21

(If-then problem). Max (or min) z such that
if f^Tx − b_1 > 0
then g^Tx − b_2 ≥ 0 .

Introduce binary variable
TRUE TRUE
FALSE TRUE
FALSE FALSE

f^Tx − b_1 ≤ M(1-y)
b_2 - g^Tx ≤My

if x_3 bigger than 0
then x_3 ≥ 5
becomes

x_3 ≤ My
5-x_3 ≤M(1-y)