Integer Programming-Cutting Plane

OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here. Integer programming formulation examples
Capital budgeting extension

For the integer programming problem given before related to capital budgeting suppose now that we have the additional condition that either project 1 or project 2 must be chosen (i.e. projects 1 and 2 are mutually exclusive). To cope with this condition we enlarge the IP given above in the following manner.

This condition is an example of an either/or condition "either project 1 or project 2 must be chosen". In terms of the variables we have already defined this condition is "either x1 = 1 or x2 = 1". The standard trick for dealing with either/or conditions relating to two zero-one variables is to add to the IP the constraint

x₁ + x₂ = 1

To verify that this mathematical description is equivalent to the verbal description "either x_{1 = 1 or x₂
= 1" we use the fact that x₁ and x₂ are both
zero-one variables.}

Choose any one of these two variables (x₁, say) and tabulate, for each possible value of the chosen variable, the meaning of the corresponding mathematical and verbal descriptions as below.

Variable value   Mathematical description   Verbal description 
                 x₁ + x₂ = 1                 "either x₁ = 1 or x₂ = 1"

x₁ = 0           x₂ = 1                      x₂ = 1 

x₁ = 1           1 + x₂ = 1                  x₂ = 0  

                      i.e. x₂ = 0

It is clear from this tabulation that the mathematical and verbal descriptions are equivalent with the proviso that we have interpreted the condition "either x₁ = 1 or x₂ = 1" as meaning that the case x₁ = 1 and x₂ = 1 (both projects 1 and 2 chosen) cannot occur. If this is not so (i.e. both projects 1 and 2 can be chosen) then we replace the constraint x₁ + x₂ = 1 by the constraint x₁ + x₂ >= 1 (i.e. at least one of projects 1 and 2 must be chosen).

Note here that, in general, we can regard formulating a problem as translating a verbal description of the problem into an equivalent mathematical description. What we have presented above is a similar process - translating a specific "either ... or ..." verbal description into an equivalent mathematical description. Whilst it is not usual to go to the lengths of a complete tabulation (as shown above) to verify that the verbal and mathematical descriptions are equivalent a complete tabulation is helpful in clarifying thought and detecting incorrect mathematical descriptions.
Other problems

The main areas in which IP is used in practice include:

imposition of logical conditions in lp problems (such as the either/or condition dealt with above)
blending with a limited number of ingredients
depot location
job shop scheduling
assembly line balancing
airline crew scheduling
timetabling

integer programming example

blending problem

consider the example of a manufacturer of animal feed who is producing feed mix for dairy cattle. in our simple example the feed mix contains two active ingredients and a filler to provide bulk. one kg of feed mix must contain a minimum quantity of each of four nutrients as below:

nutrient       a      b     c     d
gram           90     50    20    2

the ingredients have the following nutrient values and cost

                        a      b       c       d      cost/kg
ingredient 1 (gram/kg)  100    80      40      10     40
ingredient 2 (gram/kg)  200    150     20      -      60

what should be the amounts of active ingredients and filler in one kg of feed mix?

blending problem solution

variables

in order to solve this problem it is best to think in terms of one kilogram of feed mix. that kilogram is made up of three parts - ingredient 1, ingredient 2 and filler so: let
x₁ = amount (kg) of ingredient 1 in one kg of feed mix
x₂ = amount (kg) of ingredient 2 in one kg of feed mix
x₃ = amount (kg) of filler in one kg of feed mix
where x₁ >= 0, x₂ >= 0 and x₃ >= 0.

constraints

balancing constraint (an implicit constraint due to the definition of the variables)

x₁ + x₂ + x₃ = 1

nutrient constraints

100x₁ + 200x₂ >= 90 (nutrient a)
80x₁ + 150x₂ >= 50 (nutrient b)
40x₁ + 20x₂ >= 20 (nutrient c)
10x₁ >= 2 (nutrient d)

note the use of an inequality rather than an equality in these constraints, following the rule we put forward in the two mines example, where we assume that the nutrient levels we want are lower limits on the amount of nutrient in one kg of feed mix.

objective

presumably to minimise cost, i.e.

minimise 40x₁ + 60x₂

which gives us our complete lp model for the blending problem.

suppose now we have the additional conditions:

if we use any of ingredient 2 we incur a fixed cost of 15
we need not satisfy all four nutrient constraints but need only satisfy three of them (i.e. whereas before the optimal solution required all four nutrient constraints to be satisfied now the optimal solution could (if it is worthwhile to do so) only have three (any three) of these nutrient constraints satisfied and the fourth violated.

give the complete mip formulation of the problem with these two new conditions added.

solution

to cope with the condition that if x₂>=0 we have a fixed cost of 15 incurred we have the standard trick of introducing a zero-one variable y defined by

y = 1 if x₂>=0 
  = 0 otherwise

and

add a term +15y to the objective function

and add the additional constraint

x₂ <= [largest value x₂ can take]y

in this case it is easy to see that x₂ can never be greater than one and hence our additional constraint is x₂<= y.

to cope with condition that need only satisfy three of the four nutrient constraints we introduce four zero-one variables z_i (i=1,2,3,4) where

z_i = 1 if nutrient constraint i (i=1,2,3,4) is satisfied
   = 0 otherwise

and add the constraint

z₁+z₂+z₃+z₄ >= 3 (at least 3 constraints satisfied)

and alter the nutrient constraints to be

100x₁ + 200x₂ >= 90z₁
80x₁ + 150x₂ >= 50z₂
40x₁ + 20x₂ >= 20z₃
10x₁ >= 2z₄

the logic behind this change is that if a z_i=1 then the constraint becomes the original nutrient constraint which needs to be satisfied. however if a z_i=0 then the original nutrient constraint becomes

same left-hand side >= zero

which (for the four left-hand sides dealt with above) is always true and so can be neglected - meaning the original nutrient constraint need not be satisfied. hence the complete (mip) formulation of the problem is given by

minimise 40x₁ + 60x₂ + 15y 
subject to 
x₁ + x₂ + x₃ = 1
100x₁ + 200x₂ >= 90z₁ 
80x₁ + 150x₂ >= 50z₂ 
40x₁ + 20x₂ >= 20z₃ 
10x₁ >= 2z₄ 
z₁ + z₂ + z₃ + z₄ >= 3
x₂ <= y
z_i = 0 or 1    i=1,2,3,4 
y = 0 or 1
x_i >= 0    i=1,2,3

integer programming example

in the planning of the monthly production for the next six months a company must, in each month, operate either a normal shift or an extended shift (if it produces at all). a normal shift costs £100,000 per month and can produce up to 5,000 units per month. an extended shift costs £180,000 per month and can produce up to 7,500 units per month. note here that, for either type of shift, the cost incurred is fixed by a union guarantee agreement and so is independent of the amount produced.

it is estimated that changing from a normal shift in one month to an extended shift in the next month costs an extra £15,000. no extra cost is incurred in changing from an extended shift in one month to a normal shift in the next month.

the cost of holding stock is estimated to be £2 per unit per month (based on the stock held at the end of each month) and the initial stock is 3,000 units (produced by a normal shift). the amount in stock at the end of month 6 should be at least 2,000 units. the demand for the company's product in each of the next six months is estimated to be as shown below:

month   1     2     3     4     5     6 
demand  6,000 6,500 7,500 7,000 6,000 6,000

production constraints are such that if the company produces anything in a particular month it must produce at least 2,000 units. if the company wants a production plan for the next six months that avoids stockouts, formulate their problem as an integer program.

hint: first formulate the problem allowing non-linear constraints and then attempt to make all the constraints linear.

solution

variables

the decisions that have to be made relate to:

whether to operate a normal shift or an extended shift in each month; and
how much to produce each month.

hence let:

x_t = 1 if we operate a normal shift in month t (t=1,2,...,6) 
   = 0 otherwise

y_t = 1 if we operate an extended shift in month t (t=1,2,...,6) 
   = 0 otherwise

p_t (>= 0) be the amount produced in month t (t=1,2,...,6)

in fact, for this problem, we can ease the formulation by defining three additional variables - namely let:

z_t = 1 if we switch from a normal shift in month t-1 to an extended 
       shift in month t (t=1,2,...,6) 
   = 0 otherwise

i_t be the closing inventory (amount of stock left) at the end 
   of month t (t=1,2,...,6)

w_t = 1 if we produce in month t, and hence from the production 
       constraints p_t>= 2000 (t=1,2,...,6) 
   = 0 otherwise (i.e. p_t = 0)

the motivation behind introducing the first two of these variables (z_t, i_t) is that in the objective function we will need terms relating to shift change cost and inventory holding cost. the motivation behind introducing the third of these variables (w_t) is the production constraint "either p_t = 0 or p_t >= 2000", which needs a zero-one variable so that it can be dealt with using the standard trick for "either/or" constraints.

in any event formulating an ip tends to be an iterative process and if we have made a mistake in defining variables we will encounter difficulties in formulating the constraints/objective. at that point we can redefine our variables and reformulate.

constraints

we first express each constraint in words and then in terms of the variables defined above.

only operate (at most) one shift each month

x_t + y_t <= 1    t=1,2,...,6

note here that we could not have made do with just one variable (x_t say) and defined that variable to be one for a normal shift and zero for an extended shift (since in that case what if we decide not to produce in a particular month?).

although we could have introduced a variable indicating no shift (normal or extended) operated in a particular month this is not necessary as such a variable is equivalent to 1-x_t-y_t.

production limits not exceeded

p_t <= 5000x_t + 7500y_t    t=1,2,...,6

note here the use of addition in the right-hand side of the above equation where we are making use of the fact that at most one of x_t and y_t can be one and the other must be zero.

no stockouts

i_t >= 0    t=1,2,...,6

we have an inventory continuity equation of the form

closing stock = opening stock + production - demand

where i₀ = 3000. hence letting d_t = demand in month t (t=1,2,...,6) (a known constant) and assuming

that opening stock in period t = closing stock in period t-1 and
that production in period t is available to meet demand in period t

we have that

i_t = i_t-1 + p_t - d_t    t=1,2,...,6

as noted above this equation assumes that we can meet demand in the current month from goods produced that month. any time lag between goods being produced and becoming available to meet demand is easily incorporated into the above equation. for example for a 2 month time lag we replace p_t in the above equation by p_t-2 and interpret i_t as the number of goods in stock at the end of month t which are available to meet demand i.e. goods are not regarded as being in stock until they are available to meet demand. inventory continuity equations of the type shown are common in production planning problems.

the amount in stock at the end of month 6 should be at least 2000 units

i₆ >= 2000

production constraints of the form "either p_t = 0 or p_t >= 2,000".

here we make use of the standard trick we presented for "either/or" constraints. we have already defined appropriate zero-one variables w_t (t=1,2,...,6) and so we merely need the constraints

p_t <= mw_t       t=1,2,...,6

p_t >= 2000w_t    t=1,2,...,6

here m is a positive constant and represents the most we can produce in any period t (t=1,2,...,6). a convenient value for m for this example is m = 7500 (the most we can produce irrespective of the shift operated).

we also need to relate the shift change variable z_t to the shifts being operated

the obvious constraint is

z_t = x_t-1y_t    t=1,2,...,6

since as both x_t-1 and y_t are zero-one variables z_t can only take the value one if both x_t-1 and y_t are one (i.e. we operate a normal shift in period t-1 and an extended shift in period t). looking back to the verbal description of z_t it is clear that the mathematical description given above is equivalent to that verbal description. (note here that we define x₀ = 1 (y₀ = 0)).

this constraint is non-linear. however we are told that we can first formulate the problem with non-linear constraints and so we proceed. we shall see later how to linearise (generate equivalent linear constraints for) this equation.

objective

we wish to minimise total cost and this is given by

sum{t=1,...,6}(100000x_t + 180000y_t + 15000z_t + 2i_t)

hence our formulation is complete.

note that, in practise, we would probably regard i_t and p_t as taking fractional values and round to get integer values (since they are both large this should be acceptable). note too here that this is a non-linear integer program.

comments

in practice a model of this kind would be used on a "rolling horizon" basis whereby every month or so it would be updated and resolved to give a new production plan.

the inventory continuity equation presented is quite flexible, being able to accommodate both time lags (as discussed previously) and wastage. for example if 2% of the stock is wasted each month due to deterioration/pilfering etc then the inventory continuity equation becomes i_t = 0.98i_t-1 + p_t - d_t.note that, if necessary, the objective function can include a term related to 0.02i_t-1 to account for the loss in financial terms.

in order to linearise (generate equivalent linear constraints) for our non-linear constraint we again use a standard trick. note that that equation is of the form

a = bc

where a, b and c are zero-one variables. the standard trick is that a non-linear constraint of this type can be replaced by the two linear constraints

a <= (b+c)/2 and
a >= b+c-1

to see this we use the fact that as b and c take only zero-one values there are only four possible cases to consider:

b   c   a = bc     a <= (b+c)/2    a >= b+c-1 
        becomes    becomes         becomes 
0   0   a = 0      a <= 0          a >= -1 
0   1   a = 0      a <= 0.5        a >= 0 
1   0   a = 0      a <= 0.5        a >= 0 
1   1   a = 1      a <= 1          a >= 1

then, recalling that a can also only take zero-one values, it is clear that in each of the four possible cases the two linear constraints (a <= (b+c)/2 and a >= b+c-1) are equivalent to the single non-linear constraint (a=bc).

returning now to our original non-linear constraint

z_t = x_t-1y_t

this involves the three zero-one variables z_t, x_t-1 and y_t and so we can use our general rule and replace this non-linear constraint by the two linear constraints

    z_t <= (x_t-1 + y_t)/2    t=1,2,...,6
and z_t >= x_t-1 + y_t - 1    t=1,2,...,6

making this change transforms the non-linear integer program given before into an equivalent linear integer program.

integer programming example 1996 mba exam

a toy manufacturer is planning to produce new toys. the setup cost of the production facilities and the unit profit for each toy are given below. :

toy   setup cost (£)   profit (£)
1     45000            12
2     76000            16

the company has two factories that are capable of producing these toys. in order to avoid doubling the setup cost only one factory could be used.

the production rates of each toy are given below (in units/hour):

            toy 1   toy 2
factory 1   52      38
factory 2   42      23

factories 1 and 2, respectively, have 480 and 720 hours of production time available for the production of these toys. the manufacturer wants to know which of the new toys to produce, where and how many of each (if any) should be produced so as to maximise the total profit.

introducing 0-1 decision variables formulate the above problem as an integer program. (do not try to solve it).
explain briefly how the above mathematical model can be used in production planning.

solution

variables

we need to decide whether to setup a factory to produce a toy or not so let f_ij = 1 if factory i (i=1,2) is setup to produce toys of type j (j=1,2), 0 otherwise

we need to decide how many of each toy should be produced in each factory so let x_ijbe the number of toys of type j (j=1,2) produced in factory i (i=1,2) where x_ij >=0 and integer.

constraints

at each factory cannot exceed the production time available

x₁₁/52 + x₁₂/38 <= 480
x₂₁/42 + x₂₂/23 <= 720

cannot produce a toy unless we are setup to do so

x₁₁ <= 52(480)f₁₁x₁₂ <= 38(480)f₁₂x₂₁ <= 42(720)f₂₁x₂₂ <= 23(720)f₂₂

objective

the objective is to maximise total profit, i.e.

maximise 12(x₁₁+ x₂₁) + 16(x₁₂+ x₂₂) - 45000(f₁₁ + f₂₁) - 76000(f₁₂ + f₂₂)

note here that the question says that in order to avoid doubling the setup costs only one factory could be used. this is not a constraint. we can argue that if it is only cost considerations that prevent us using more than one factory these cost considerations have already been incorporated into the model given above and the model can decide for us how many factories to use, rather than we artificially imposing a limit via an explicit constraint on the number of factories that can be used.

the above mathematical model could be used in production planning in the following way:

enables us to maximise profit, rather than relying on an ad-hoc judgemental approach
can be used for sensitivity analysis - for example to see how sensitive our production planning decision is to changes in the production rates
enables us to see the effect upon production of (say) increasing the profit per unit on toy 1
enables us to easily replan production in the event of a change in the system (e.g. a reduction in the available production hours at factory one due to increased work from other products made at that factory)
can use on a rolling horizon basis to plan production as time passes (in which case we perhaps need to introduce a time subscript into the above model)

integer programming example 1995 mba exam

a project manager in a company is considering a portfolio of 10 large project investments. these investments differ in the estimated long-run profit (net present value) they will generate as well as in the amount of capital required.

let p_j and c_j denote the estimated profit and capital required (both given in units of millions of £) for investment opportunity j (j=1,...,10) respectively. the total amount of capital available for these investments is q (in units of millions of £)

investment opportunities 3 and 4 are mutually exclusive and so are 5 and 6. furthermore, neither 5 nor 6 can be undertaken unless either 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 maximise the total estimated long-run profit subject to the restrictions described above.

formulate this problem using an integer programming model and comment on the difficulties of solving this model. (do not actually solve it).

what are the advantages and disadvantages of using this model for portfolio selection?

solution

variables

we need to decide whether to use an investment opportunity or not so let x_j = 1 if we use investment opportunity j (j=1,...,10), 0 otherwise

constraints

total amount of capital available for these investments is q

sum{j=1,...,10}c_jx_j <= q

investment opportunities 3 and 4 are mutually exclusive and so are 5 and 6

x₃ + x₄ <= 1
x₅ + x₆ <= 1

neither 5 nor 6 can be undertaken unless either 3 or 4 is undertaken

x₅ <= x₃+ x₄
x₆ <= x₃+ x₄

at least two and at most four investment opportunities have to be undertaken from the set {1,2,7,8,9,10}

x₁ + x₂ + x₇ + x₈ + x₉ + x₁₀ >= 2
x₁ + x₂ + x₇ + x₈ + x₉ + x₁₀ <= 4

objective

the objective is to maximise the total estimated long-run profit i.e.

maximise sum{j=1,...,10}p_jx_j

the model given above is a very small zero-one integer programming problem with just 10 variables and 7 constraints and should be very easy to solve. for example even by complete (total) enumeration there are just 2¹⁰ = 1024 possible solutions to be examined.

the advantages and disadvantages of using this model for portfolio selection are:

enables us to maximise profit, rather than relying on an ad-hoc judgemental approach
can be easily extended to deal with a larger number of potential investment opportunities
can be used for sensitivity analysis, for example to see how sensitive our portfolio selection decision is to changes in the data
the model fails to take into account any statistical uncertainly (risk) in the data, it is a completely deterministic model, for example project j might have a (known or estimated) statistical distribution for its profit p_j and so we might need a model that takes this distribution into account

integer programming example 1994 mba exam

a food is manufactured by refining raw oils and blending them together. the raw oils come in two categories:

vegetable oil:

veg1
veg2

non-vegetable oil:

oil1
oil2
oil3

the prices for buying each oil are given below (in £/tonne)

veg1  veg2  oil1  oil2  oil3
115   128   132   109   114

the final product sells at £180 per tonne. vegetable oils and non-vegetable oils require different production lines for refining. it is not possible to refine more than 210 tonnes of vegetable oils and more than 260 tonnes of non-vegetable oils. there is no loss of weight in the refining process and the cost of refining may be ignored.

there is a technical restriction relating to the hardness of the final product. in the units in which hardness is measured this must lie between 3.5 and 6.2. it is assumed that hardness blends linearly and that the hardness of the raw oils is:

veg1  veg2  oil1  oil2  oil3
8.8   6.2   1.9   4.3   5.1

it is required to determine what to buy and how to blend the raw oils so that the company maximises its profit.

formulate the above problem as a linear program. (do not actually solve it).
what assumptions do you make in solving this problem by linear programming?

the following extra conditions are imposed on the food manufacture problem stated above as a result of the production process involved:

the food may never be made up of more than 3 raw oils
if an oil (vegetable or non-vegetable) is used, at least 30 tonnes of that oil must be used
if either of veg1 or veg2 are used then oil2 must also be used

introducing 0-1 integer variables extend the linear programming model you have developed to encompass these new extra conditions.

solution

variables

we need to decide how much of each oil to use so let x_ibe the number of tonnes of oil of type i used (i=1,...,5) where i=1 corresponds to veg1, i=2 corresponds to veg2, i=3 corresponds to oil1, i=4 corresponds to oil2 and i=5 corresponds to oil3 and where x_i >=0 i=1,...,5

constraints

cannot refine more than a certain amount of oil

x₁ + x₂ <= 210
x₃ + x₄ + x₅ <= 260

hardness of the final product must lie between 3.5 and 6.2

(8.8x₁ + 6.2x₂ + 1.9x₃ + 4.3x₄ + 5.1x₅)/(x₁ + x₂ + x₃ + x₄ + x₅) >= 3.5
(8.8x₁ + 6.2x₂ + 1.9x₃ + 4.3x₄ + 5.1x₅)/(x₁ + x₂ + x₃ + x₄ + x₅) <= 6.2

objective

the objective is to maximise total profit, i.e.

maximise 180(x₁ + x₂ + x₃ + x₄ + x₅) - 115x₁ - 128x₂ - 132x₃ - 109x₄ - 114x₅

the assumptions we make in solving this problem by linear programming are:

all data/numbers are accurate
hardness does indeed blend linearly
no loss of weight in refining
can sell all we produce

integer program

variables

in order to deal with the extra conditions we need to decide whether to use an oil or not so let y_i = 1 if we use any of oil i (i=1,...,5), 0 otherwise

constraints

must relate the amount used (x variables) to the integer variables (y) that specify whether any is used or not

x₁ <= 210y₁
x₂ <= 210y₂
x₃ <= 260y₃
x₄ <= 260y₄
x₅ <= 260y₅

the food may never be made up of more than 3 raw oils

y₁ + y₂ + y₃ + y₄ + y₅ <= 3

if an oil (vegetable or non-vegetable) is used, at least 30 tonnes of that oil must be used

x_i >= 30y_i i=1,...,5

if either of veg1 or veg2 are used then oil2 must also be used

y₄ >= y₁y₄ >= y₂

objective

the objective is unchanged by the addition of these extra constraints and variables.

integer programming example 1985 ug exam

a factory works a 24 hour day, 7 day week in producing four products. since only one product can be produced at a time the factory operates a system where, throughout one day, the same product is produced (and then the next day either the same product is produced or the factory produces a different product). the rate of production is:

product                                 1   2   3   4 
no. of units produced per hour worked   100 250 190 150

the only complication is that in changing from producing product 1 one day to producing product 2 the next day five working hours are lost (from the 24 hours available to produce product 2 that day) due to the necessity of cleaning certain oil tanks.

to assist in planning the production for the next week the following data is available:

         current   demand (units) for each day of the week 
product  stock     1     2     3     4     5     6     7 
         (units) 
1        5000      1500  1700  1900  1000  2000  500   500 
2        7000      4000  500   1000  3000  500   1000  2000 
3        9000      2000  2000  3000  2000  2000  2000  500
4        8000      3000  2000  2000  1000  1000  500   500

product 3 was produced on day 0. the factory is not allowed to be idle (i.e. one of the four products must be produced each day). stockouts are not allowed. at the end of day 7 there must be (for each product) at least 1750 units in stock.

if the cost of holding stock is £1.50 per unit for products 1 and 2 but £2.50 per unit for products 3 and 4 (based on the stock held at the end of each day) formulate the problem of planning the production for the next week as an integer program in which all the constraints are linear.

solution

variables

the decisions that have to be made relate to the type of product to produce each day. hence let:

x_it = 1 if produce product i (i=1,2,3,4) on day t (t=1,2,3,4,5,6,7) = 0 otherwise

in fact, for this problem, we can ease the formulation by defining two additional variables - namely let:

i_it be the closing inventory (amount of stock left) of product i (i=1,2,3,4) on day t (t=1,2,...,7)
p_it be the number of units of product i (i=1,2,3,4) produced on day t (t=1,2,...,7)

constraints

only produce one product per day

x_1t + x_2t + x_3t + x_4t = 1    t=1,2,...,7

no stockouts

i_it >= 0    i=1,...,4 t=1,...,7

we have an inventory continuity equation of the form

closing stock = opening stock + production - demand

letting d_it represent the demand for product i (i=1,2,3,4) on day t (t=1,2,...,7) we have

i₁₀ = 5000 
i₂₀ = 7000 
i₃₀ = 9000 
i₄₀ = 8000

representing the initial stock situation and

i_it = i_it-1 + p_it - d_it    i=1,...,4 t=1,...,7

for the inventory continuity equation.

note here that we assume that we can meet demand in month t from goods produced in month t and also that the opening stock in month t = the closing stock in month _t-1.

production constraint

let r_i represent the work rate (units/hour) for product i (i=1,2,3,4) then the production constraint is

p_it = x_it[24r_i]    i=1,3,4 t=1,...,7

which covers the production for all except product 2 and

p_2t = [24r₂]x_2t - [5r₂]x_2tx_1t-1    t=1,...,7

i.e. for product 2 we lose 5 hours production if we are producing product 2 in period t and we produced product 1 the previous period. note here that we initialise by

x₁₀ = 0

since we know we were not producing product 1 on day 0. plainly the constraint involving p_2t is non-linear as it involves a term which is the product of two variables. however we can linearise it by using the trick that given three zero-one variables (a,b,c say) the non-linear constraint

a = bc

can be replaced by the two linear constraints

a <= (b + c)/2 and
a >= b + c - 1

hence introduce a new variable z_t defined by the verbal description

z_t = 1 if produce product 2 on day t and product 1 on day t-1
   = 0 otherwise

then

z_t = x_2tx_1t-1    t=1,...,7

and our non-linear equation becomes

p_2t = [24r₂]x_2t - [5r₂]z_t    t=1,...,7

and applying our trick the non-linear equation for z_t can be replaced by the two linear equations

z_t <= (x_2t + x_1t-1)/2    t=1,...,7

z_t >= x_2t + x_1t-1 - 1    t=1,...,7

closing stock

i_i7 >= 1750    i=1,...,4

all variables >= 0 and integer, (x_it) and (z_t) zero-one variables

note that, in practise, we would probably regard (i_it) and (p_it) as taking fractional values and round to get integer values (since they are both quite large this should be acceptable).

objective

we wish to minimise total cost and this is given by

sum{t=1,...,7}(1.50i_1t + 1.50i_2t + 2.50_i3t + 2.50i_4t)

note here that this program may not have a feasible solution, i.e. it may simply not be possible to satisfy all the constraints. this is irrelevant to the process of constructing the model however. indeed one advantage of the model may be that it will tell us (once a computational solution technique is applied) that the problem is infeasible.

integer programming example 1987 ug exam

a company is attempting to decide the mix of products which it should produce next week. it has seven products, each with a profit (£) per unit and a production time (man-hours) per unit as shown below:

product   profit (£ per unit)   production time (man-hours per unit)
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

the company has 720 man-hours available next week.

formulate the problem of how many units (if any) of each product to produce next week as an integer program in which all the constraints are linear.

incorporate the following additional restrictions into your integer program (retaining linear constraints and a linear objective):

if any of product 7 are produced an additional fixed cost of £2000 is incurred.
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 (e.g. producing 101 units of product 2 requires 100(2.0) + 1(3.0) man-hours).
if both product 3 and product 4 are produced 75 man-hours are needed for production line set-up and hence the (effective) number of man-hours available falls to 720 - 75 = 645.

solution

let x_i (integer >=0) be the number of units of product i produced then the integer program is

maximise

10x₁ + 22x₂ + 35x₃ + 19x₄ + 55x₅ + 10x₆ + 115x₇

subject to

1.0x₁ + 2.0x₂ + 3.7x₃ + 2.4x₄ + 4.5x₅ + 0.7x₆ + 9.5x₇ <= 720

x_i >= 0 integer i=1,2,...,7

let

z₇ = 1 if produce product 7 (x₇ >= 1) 
   = 0 otherwise

then

subtract 2000z₇ from the objective function and
add the constraint x₇ <= [most we can make of product 7]z₇

hence

     x₇ <= (720/9.5)z₇i.e. x₇ <= 75.8z₇so   x₇ <= 75z₇ (since x₇ is integer)

let y₂ = number of units of product 2 produced in excess of 100 units then add the constraints

x₂ <= 100
y₂ >= 0 integer
and amend the work-time constraint to be 1.0x₁ + [2.0x₂ + 3.0y₂] + 3.7x₃ + 2.4x₄ + 4.5x₅ + 0.7x₆ + 9.5x₇ <= 720
and add +22y₂ to the objective function.

this will work because x₂ and y₂ have the same objective function coefficient but y₂ requires longer to produce so will always get more flexibility by producing x₂ first (up to the 100 limit) before producing y₂.

introduce

z = 1 if produce both product 3 and product 4 (x₃ >= 1 and x₄ >= 1) 
  = 0 otherwise 

z₃ = 1 if produce product 3 (x₃ >= 1) 
   = 0 otherwise 

z₄ = 1 if produce product 4 (x₄ >= 1) 
   = 0 otherwise

and

subtract from the rhs of the work-time constraint 75z

and add the two constraints

x₃ <= [most we can make of product 3]z₃
x₄ <= [most we can make of product 4]z₄

i.e.

x₃ <= 194z₃ and x₄ <= 300z₄

and relate z to z₃ and z₄ with the non-linear constraint

z = z₃z₄

which we linearise by replacing the non-linear constraint by the two linear constraints

z >= z₃ + z₄ - 1
z <= (z₃ + z₄)/2

Theoretical Paper

Practical Paper

Industrial Training

Enroll now!

Theoretical Paper

Practical Paper

Industrial Training

Integer Programming-Cutting Plane

integer programming example

blending problem

blending problem solution

solution

integer programming example

solution

variables

constraints

objective

comments

integer programming example 1996 mba exam

solution

variables

constraints

objective

integer programming example 1995 mba exam

solution

variables

constraints

objective

integer programming example 1994 mba exam

solution

variables

constraints

objective

integer program

variables

constraints

objective

integer programming example 1985 ug exam

solution

variables

constraints

objective

integer programming example 1987 ug exam

solution