GitHub Repository: DataScienceUWL/DS775
Path: blob/main/Lessons/Lesson 09 - Integer Programming/Lesson_09.ipynb
⁸⁷¹ views

Kernel: Python 3 (system-wide)

In [3]:

# EXECUTE FIRST

# computational imports
from pyomo.environ import *

# for playing videos, customize height and width if desired
# for best results keep 16:9 ratio
def play_video(vid_name, w=640, h=360):
    from IPython.display import display, IFrame
    from IPython.core.display import HTML
    vid_path = "https://media.uwex.edu/content/ds/ds775_r19/" + vid_name + "/index.html"
    print(vid_path)
    hlink = '<a href = ' + vid_path + ' target = """_blank""">Open video in new tab</a>'
    display(IFrame(vid_path, width=w, height=h))
    display(HTML(hlink))

Lesson 09: Integer Programming

General Integer Programming

Watch the following video for a general introduction to integer programming.

In [4]:

# execute for video
play_video("ds775_lesson9_general-integer-programming-intro")

Out[4]:

Key Concepts

Decision variables constrained to integer values
- Can produce 5 or 6 cars, but not 5.72 cars
For pure integer programming (IP) problems, solutions can be obtained simply by changing the domain for the LP from NonNegativeReals to PositiveIntegers in the Pyomo coding (as seen in textbook problem 3.4-10 as a Self-Assessment back in Lesson 01)
Computationally, integer programming can be much more difficult than linear programming (this post can help you visualize why this is so)

Binary Integer Programming

Watch the following video for an introduction to binary integer programming.

11/5/2021 - I've just learned that the video gives backward instructions .... it should be that you can only invest in 3 after investing in 4, and can only invest in 1 after investing in 2. With those changes the equations will make sense.

In [5]:

# execute for video
play_video("ds775_lesson9_binary-integer-programming")

Out[5]:

Key Concepts

contain binary (boolean) variables
i.e. 0 for no, 1 for yes
effectively turns off or on each decision variable
Binary variables are considerably easier to deal with than general integer variables, so they generally can be used to solve substantially larger problems

Prototype Problem

Maximize $Z=8 x_{1}+4 x_{2}+6 x_{3}+16 x_{4}$

subject to

$5 x_{1}+3 x_{2}+2 x_{3}+8 x_{4} \leq 10$

$x_{2}+x_{3} \leq 1$

$-x_{4} + x_{3} \leq 0$

$-x_{2} + x_{1} \leq 0$

and each $x_{i}$ has to be 0 or 1

In [6]:

#Abstract Code for the Prototype Problem

decisions = ['i1', 'i2', 'i3', 'i4']
vals = [8,4,6,16]
costs = [5,3,2,8]

total_capital = 10


cts = ['ct2','ct3','ct4']
#create a matric of 1s and zeros that would match our constraints
coefs = {'ct2':dict(zip(decisions,[ 0,1,1,0])), #model.x['i2'] + model.x['i3'] <= 1
         'ct3':dict(zip(decisions,[0,0,1,-1])), #- model.x['i4'] + model.x['i3'] <= 0
         'ct4':dict(zip(decisions,[1,-1,0,0]))} #- model.x['i2'] + model.x['i1'] <= 0
rhs = dict(zip(cts,[1,0,0]))


# Concrete Model
model = ConcreteModel(name = "BiInvest2")

#Decision Variables
model.investments = Var(decisions, domain=Boolean)

#Objective
model.profit = Objective(expr=sum(vals[decisions.index(d)] * model.investments[d] for d in decisions),
                         sense=maximize)

model.constraints = ConstraintList()
model.constraints.add(sum(costs[decisions.index(d)] * model.investments[d] for d in decisions) <= total_capital)
for c in cts:
    model.constraints.add( expr = sum(coefs[c][d]*model.investments[d] for d in decisions) <= rhs[c])

# Solve
solver = SolverFactory('glpk')
solver.solve(model)


# display solution
print(f"The future profit is ${model.profit():,.2f} million.")
for d in decisions:
    print(f"Invest {d}? {['No','Yes'][int(model.investments[d]())]}" )

Out[6]:

The future profit is $22.00 million.
Invest i1? No
Invest i2? No
Invest i3? Yes
Invest i4? Yes

Self Assessment: Solving the California Manufacturing BIP

The textbook presents a prototype Binary Integer Programming Problem - the California Manufacturing Problem. (Chapter 12.1, page 476)

The mathematical formulation for this problem is:

Maximize $Z=9 x_{1}+5 x_{2}+6 x_{3}+4 x_{4}$

subject to

$6 x_{1}+3 x_{2}+5 x_{3}+2 x_{4} \leq 10$

$x_{3}+x_{4} \leq 1$

$-x_{1} + x_{3} \leq 0$

$-x_{2} + x_{4} \leq 0$

and each $x_{i}$ has to be 0 or 1

Use Pyomo in Python to find the solution to the BIP model for the California Manufacturing Company problem.

Mixed Integer Programming

Watch the following video for an introduction to mixed integer programming.

In [7]:

# execute for video
play_video("ds775_lesson9_mixed-integer-programming")

Out[7]:

Key Concepts

some variables are constrained to be integers while other are not
very common approach to many problems
mixed integer programming often uses one of two BigM approaches to enforce constraints
- Either-Or Constraints
- Fixed Cost

Good Products Example Problem

This is the Good Products example (textbook page 489), similar to the Wyndor problem, in which we have to choose which products to produce and which factories to use. The problem description is reproduced here for convenience. This is an example of a problem that implements the either-or constraint.

Problem Description

The Research and Development Division of the GOOD PRODUCTS COMPANY has developed three possible new products. However, to avoid undue diversification of the company’s product line, management has imposed the following restriction:

Restriction 1: From the three possible new products, at most two should be chosen to be produced.

Each of these products can be produced in either of two plants. For administrative reasons, management has imposed a second restriction in this regard.

Restriction 2: Just one of the two plants should be chosen to be the sole producer of the new products.

The production cost per unit of each product would be essentially the same in the two plants. However, because of differences in their production facilities, the number of hours of production time needed per unit of each product might differ between the two plants. These data are given in the table below, along with other relevant information, including marketing estimates of the number of units of each product that could be sold per week if it is produced. The objective is to choose the products, the plant, and the production rates of the chosen products so as to maximize total profit.

Mathematical Formulation

In [0]:

Maximize $Z = 5x_1 + 7x_2 + 3x_3$

Subject to:

$\begin{array}{l} 3x_1 + 4x_2 + 2x_3 \leq 30 + My_4\\ 4x_1 + 6x_2 + 2x_3 \leq 40 + M(1-y_4) \\ \\ 0 \leq x_1 \leq 7 \\ 0 \leq x_2 \leq 5 \\ 0 \leq x_3 \leq 9 \\ \\ y_1 + y_2 + y_3 \leq 2 \\ 0 \leq x_i \leq My_i, \text{ for } i=1,2,3 \\ y_i \text{ binary, for } i=1, 2, 3, 4 \end{array}$

Note that if $y_4 = 0$ we are using Plant 1 and if $y_4 = 1$ we are using Plant 2.

The complete formulation of this problem is discussed on pages 490-491 of the textbook.

Pyomo Concrete Formulation Solution

Here we'll just use individual variables $x_1, x_2,$ etc. for maximum transparency. In the homework you'll need to include abstract formulations, but we include a concrete formulation here to help you understand how binary variables work in Pyomo. The next section has the abstract formulation.

In [8]:

# concrete Good Products
m = ConcreteModel(name="Example_1")

m.x1 = Var(bounds=(0,7))
m.x2 = Var(bounds=(0,5))
m.x3 = Var(bounds=(0,9))

m.y1 = Var(domain=Boolean)
m.y2 = Var(domain=Boolean)
m.y3 = Var(domain=Boolean)
m.y4 = Var(domain=Boolean) # 0 to use Plant 1, 1 to use Plant 2

m.profit = Objective( expr = 5*m.x1 + 7*m.x2 + 3*m.x3, sense = maximize)

bigM = 10000

# Constraints:
m.cts = ConstraintList()
m.cts.add( m.y1 + m.y2 + m.y3 <= 2)
m.cts.add( 3 * m.x1 + 4 * m.x2 + 2 * m.x3 <= 30 + bigM * m.y4 )
m.cts.add( 4 * m.x1 + 6 * m.x2 + 2 * m.x3 <= 40 + bigM * (1 - m.y4))
m.cts.add( m.x1 <= bigM * m.y1)
m.cts.add( m.x2 <= bigM * m.y2)
m.cts.add( m.x3 <= bigM * m.y3)

# Solve
solver = SolverFactory('glpk')
solver.solve(m)

print(f"Maximum Profit = ${1000*m.profit():,.2f}")

print("Use "+ "Plant 2." if m.y4() else "Plant 1." )

for i,amount in enumerate([m.x1(),m.x2(),m.x3()]):
    if amount > 0:
        print(f"Produce {amount:0.1f} of product {i+1} per week")

Out[8]:

Maximum Profit = $54,500.00
Use Plant 2.
Produce 5.5 of product 1 per week
Produce 9.0 of product 3 per week

Pyomo Abstract Formulation Solution

To make the abstract formulation we add an extra binary variable, $y_5$ , so that we have one for each plant to make the plant constraints have the same format. The math formulation then replaces:

$\begin{array}{l} 3x_1 + 4x_2 + 2x_3 \leq 30 + My_4 \\ 4x_1 + 6x_2 + 2x_3 \leq 40 + M(1-y_4) \\ \end{array}$

with:

$\begin{array}{l} 3x_1 + 4x_2 + 2x_3 \leq 30 + M(1-y_4)\\ 4x_1 + 6x_2 + 2x_3 \leq 40 + M(1-y_5)\\ y_4 + y_5 = 1 \end{array}$

so if $y_4 = 1$ we are using Plant 1 and if $y_5 = 1$ we are using Plant 2.

In [9]:

# abstract Good Products

# Problem data
products = ['Product1', 'Product2', 'Product3']
unit_profit = dict(zip(products, [5, 7, 3]))

sales_potential = dict(zip(products, [7, 5, 9]))
def bounds_rule(model, product):
    return ((0, sales_potential[product]))

plants = ['Plant1', 'Plant2']
production_avail = dict(zip(plants, [30, 40]))

tpu = [[3, 4, 2], [4, 6, 2]]
time_per_unit = {
    plants[p]: dict(zip(products, tpu[p][:]))
    for p in range(len(plants))
}
bigM = 10000

max_num_products_to_choose = 2
num_plants_to_use = 1

# Instantiate concrete model
M = ConcreteModel(name="Example_1")

# Decision Variables
M.x = Var(products, domain=Reals, bounds=bounds_rule)
M.y = Var(products, domain=Boolean)
M.plant_choice = Var(plants, domain=Boolean)

# Objective:  Maximize Profit
M.profit = Objective(expr=sum(unit_profit[pr] * M.x[pr] for pr in products),
                     sense=maximize)

# Constraints:
M.constraints = ConstraintList()

for pr in products:  # produce product only if product is chosen
    M.constraints.add(M.x[pr] <= bigM * M.y[pr])

# choose 2 products
M.constraints.add(sum(M.y[pr] for pr in products) <= max_num_products_to_choose)

for pl in plants:  # production capacities
    M.constraints.add(
        sum(time_per_unit[pl][pr] * M.x[pr]
            for pr in products) <= production_avail[pl] +
        bigM * (1-M.plant_choice[pl]) )

# choose 1 plant
M.constraints.add(sum(M.plant_choice[pl] for pl in plants) == num_plants_to_use)

M.pprint()

# Solve
solver = SolverFactory('glpk')
solver.solve(M)

print(f"Maximum Profit = ${1000 * M.profit():,.2f}")

print("\nWhich plant to use:")
for pl in plants:
    print(f"Produce at {pl}? {['No','Yes'][int(M.plant_choice[pl]())]}")

print("\nWhich products and how many:")
for pr in products:
    if bool(M.y[pr]()):
        print(f"Produce {pr} at a rate of {M.x[pr]():.2f} per week")
    else:
        print(f"Do not produce {pr}" )

Out[9]:

4 Set Declarations
    constraints_index : Size=1, Index=None, Ordered=Insertion
        Key  : Dimen : Domain : Size : Members
        None :     1 :    Any :    7 : {1, 2, 3, 4, 5, 6, 7}
    plant_choice_index : Size=1, Index=None, Ordered=Insertion
        Key  : Dimen : Domain : Size : Members
        None :     1 :    Any :    2 : {'Plant1', 'Plant2'}
    x_index : Size=1, Index=None, Ordered=Insertion
        Key  : Dimen : Domain : Size : Members
        None :     1 :    Any :    3 : {'Product1', 'Product2', 'Product3'}
    y_index : Size=1, Index=None, Ordered=Insertion
        Key  : Dimen : Domain : Size : Members
        None :     1 :    Any :    3 : {'Product1', 'Product2', 'Product3'}

3 Var Declarations
    plant_choice : Size=2, Index=plant_choice_index
        Key    : Lower : Value : Upper : Fixed : Stale : Domain
        Plant1 :     0 :  None :     1 : False :  True : Boolean
        Plant2 :     0 :  None :     1 : False :  True : Boolean
    x : Size=3, Index=x_index
        Key      : Lower : Value : Upper : Fixed : Stale : Domain
        Product1 :     0 :  None :     7 : False :  True :  Reals
        Product2 :     0 :  None :     5 : False :  True :  Reals
        Product3 :     0 :  None :     9 : False :  True :  Reals
    y : Size=3, Index=y_index
        Key      : Lower : Value : Upper : Fixed : Stale : Domain
        Product1 :     0 :  None :     1 : False :  True : Boolean
        Product2 :     0 :  None :     1 : False :  True : Boolean
        Product3 :     0 :  None :     1 : False :  True : Boolean

1 Objective Declarations
    profit : Size=1, Index=None, Active=True
        Key  : Active : Sense    : Expression
        None :   True : maximize : 5*x[Product1] + 7*x[Product2] + 3*x[Product3]

1 Constraint Declarations
    constraints : Size=7, Index=constraints_index, Active=True
        Key : Lower : Body                                                                                    : Upper : Active
          1 :  -Inf :                                                         x[Product1] - 10000*y[Product1] :   0.0 :   True
          2 :  -Inf :                                                         x[Product2] - 10000*y[Product2] :   0.0 :   True
          3 :  -Inf :                                                         x[Product3] - 10000*y[Product3] :   0.0 :   True
          4 :  -Inf :                                                 y[Product1] + y[Product2] + y[Product3] :   2.0 :   True
          5 :  -Inf : 3*x[Product1] + 4*x[Product2] + 2*x[Product3] - (30 + 10000*(1 - plant_choice[Plant1])) :   0.0 :   True
          6 :  -Inf : 4*x[Product1] + 6*x[Product2] + 2*x[Product3] - (40 + 10000*(1 - plant_choice[Plant2])) :   0.0 :   True
          7 :   1.0 :                                             plant_choice[Plant1] + plant_choice[Plant2] :   1.0 :   True

9 Declarations: x_index x y_index y plant_choice_index plant_choice profit constraints_index constraints
Maximum Profit = $54,500.00

Which plant to use:
Produce at Plant1? No
Produce at Plant2? Yes

Which products and how many:
Produce Product1 at a rate of 5.50 per week
Do not produce Product2
Produce Product3 at a rate of 9.00 per week

Self-Assessment: Integer Programming

True or False: Integer programs are generally more computationally difficult than linear programs with continuous variables.

Self-Assessment: Type of Programming

The problem

Maximize $Z = 7 x_1 + 3 x_2$

Subject to:

$\begin{array}{ccccc} 5 x_1 & + & 7 x_2 & \leq & 27 \\ 4 x_1 & + & x_2 & \leq & 14 \\ 3x_1 & - & 2x_2 & \leq & 19 \end{array}$

$x_1 \geq 0$ , $x_2 \geq 0$ , $x_1$ integer

is an example of a(n)

a. nonlinear program.

b. integer program.

c. mixed integer program.

d. none of the above.

Self-Assessment: Rounding Solutions to Integers

Solving an integer programming problem by rounding off answers obtained by solving it as a linear programming problem, we find that

a. The values of the decision variables obtained by rounding are always very close to the optimal values.

b. The true value of the objective function for a maximization problem will likely be less than that found by solving the linear programming problem.

c. The true value of the objective function for a minimization problem will likely be more than that found by solving the linear programming problem.

d. The lower bound reaches zero.

e. None of the above.

Self-Assessment: Either/Or Constraints

True or False: To implement an either/or constraint where one or both of two constraints must be satisfied it is necessary add two binary variables.

Self-Assessment: Number of Solutions in BIP

True or False: There are $n^2$ solutions to consider when there are $n$ binary decision variables to be considered in an integer programming problem.

In [0]:

In [0]:

In [0]:

In [0]: