Operation Research II

Integer Programming

Posted by Pritish Roy on July 12, 2020

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear.
Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.
If some decision variables are not discrete the problem is known as a mixed-integer programming problem.
Mixed integer programming (MIP) can be successfully implemented to optimize the operational efficiency of a complex organization while considering resource demand and capacity constraints, and critical business rules. Application of MIP models is in 

  • Supply Chain Optimization: SAP Advanced Planning and Optimization and SAP HANA help solve complex optimization problems. 
  • Electrical Power Optimization: NYISO managed New York's wholesale electrical power market ($7.5 billion in annual transactions) to optimize 500 power-generation units and 11,000 miles of transmission lines with consumer demand in real-time. 
  • Government: The Federal communication commission (FCC) used optimization to generate the first two-sided spectrum, generating $20 billion in revenue.
MIP models have been applied in a variety of business realms, often resulting in cost savings of tens or even hundreds of millions of dollars. It allows us to combine predicate logic with optimization. This means several rules can be embedded in the mathematical planning formulation. For example. a production planning model might include a rule that says if product A is produced, the product B must be produced and product C cannot be produced.
Application of MIP models is relevant to data scientists, for example 
  • Marketing Campaign which contains a set of products and a set of customers. The problem is to identify which product to advertise to which customer, maximizing the advertised product return on investment and staying within a budget. 
  • Price optimization with a set of inventories of various retail products. The problem is to determine at which price each retail product should be sold in order to maximize profits while considering a minimum level return on investment and market share and other business rules.
  • Resource Management Optimization with a set of resources along with various qualifications and there is a set of jobs with specific requirements regarding resource qualifications.


We will look at a running example from my last post for a better explanation...

Cyclone Cyril was quite severe but our planning was effective and we successfully distributed relief supplies to affected areas. However, the experience gave us some ideas for how we can improve our plans for any future disaster.
We have started by investigating four new sites for possible FSDs and transport costs from the potential FSD sites to the DDPs. We want to have no more than five FSDs but can now choose from the nine possible sites (the original five and these new four sites). For the purposes of our new planning, it is no longer necessary that no more than half of the demand at each DDP is coming from a single FSD. We will also have no information about scenarios until the next cyclone approaches. Which sites should we choose as FSDs to minimize the overall costs? We have realized that changing the sites of too many FSDs will be disruptive. Could you revise your proposal so that we select at most one of the new FSD sites? During our relief efforts after Cyclone Cyril, we noticed that the trucks transporting our supplies were not always being used very efficiently. Each truck has a capacity of 60 tonnes for a trip, either from the CDRD to an FSD or from an FSD to a DDP.
We need to pay the full trip cost for that 60-tonne capacity, even if the truck only ends up carrying 1 tonne of supplies. Now that we can take into account the individual trucks, we’ve realized it would also be desirable to allocate trucks to each FSD before the cyclone. Having the trucks ready at the FSDs will mean our deliveries of relief supplies to the DDPs can be more timely. To support this, each truck we assign to an FSD will be expected to do no more than three trips to DDPs during the relief efforts. Can you help us plan how many trucks we will need and where we should position them? Each truck will cost us $20,000 to allocate to an FSD. Our initial suggestion for a limit of no more than three trips to DDPs per truck during the relief efforts was rather crude. In practice, each truck can be driven for up to 12 hours, and the number of minutes required for a return trip from an FSD to a DDP is 3 times the dollar transport costs we initially provided. Can you help us plan how many trucks we will need and where we should position them? Each truck will still cost us $20,000 to allocate to an FSD and we would not want more than six trucks allocated to a single FSD.


SETS

I       Set of supply depot (FSD)
J       Set of demand depot (DDP)
K       Set of trucks


DATA

demand_{j}           Demand per DDP depot for j in J
Cost_FSD_{i}         Cost of transporting relief goods from CDRD to FSD for i in I
Cost_DDP_{ij}        Cost of transporting relief goods from FSD for i in I to DDP for j in J
relief_good_cost     Price of relief goods
maximum_capacity     Maximum capacity at FSD node
truck_capacity       Capacity of truck for a trip
Cost_Truck           Cost of truck allocated per FSD
truck_allocated_FSD  Number of truck allocated per FSD
td_min               Number in minuted a Truck can be driven
open_FSD             Number of FSD depot that can be open at a time
M                    Big co-efficient default value


VARIABLES

O_{i}      Decision to open or close a FSD depot for i in I
DDP_{ijk} Amount of relief supplies to transport from FSD i in I to DDP j in J in truck k in K
T_F_{i} Trips for transporting relief goods to FSD i in I
T_D_{ijk} Trips for transporting relief goods from FSD i in I to DDP j in J in truck k in K
T_{ik} Decision to allocate a truck at FSD i in I and the number of trucks k in K allocated

OBJECTIVE

min sum Cost_FSD_{i} * truck_capacity * T_F_{i} + sum  Cost_DDP_{ij} * truck_capacity * T_D_{ijk} + sum  Cost_Truck * T_{ik}

CONSTRAINTS

  • At most five FSDs depot can be open at a given time.
sum O_{i} <= open_FSD
  • At least one depot from the new nodes added to FSD must be open
O_{5} + O_{6} + O_{7} + O_{8} = 1 
  • Each FSD should have a maximum capacity limit
sum {j in J, k in K}DDP_{ijk} <= maximum_capacity for every i in I
  • The decision to open or close the FSD depot by the big M co-efficient to avoid infeasibility.
sum {j in J, k in K} DDP_{ijk} <= M * O_{i} for every i in I
  • The number of trips required by FSD given its truck capacity limit.
sum {j in J, k in K} DDP_{ijk} <= T_F_{i} * truck_capacity for every i in I
  • Truck assigned per FSD should be less than six.
sum {k in K} T_{ik} <=  truck_allocated_FSD for every i in I
  • The number of trucks allocated at FSD should be less than the truck driven minutes which is 3 times the cost and the number of trips from FSD to DDP in each truck.
T_{ik} * td_min >= sum{j in J} * Cost_DDP_{ij} * T_D_{ijk} for every i in I, for every k in K
  • Supply at each DDP node should be equal to demand.
sum {j in J, k in K} DDP_{ijk} = demand_{j} for every j in J
  • The number of trips required per DDP depot in each truck given its truck capacity.
sum{k in K} DDP_{ijk} <= sum{k in K} * T_D_{ijk} * truck_capacity or every i in I, for every j in J 
  • The binary constraint that says FSD can be either open or closed, whether a truck can be allocated and the number of trucks that can be allocated to FSD.
O_{i} in {0, 1}, T_{ik} in {0, 1} for every i in I, for every k in K
  • Non-negativity constraints.
DDP_{ijk}, T_F_{i}, T_D_{ijk} or every i in I, for every j in J, for every k in K

The price of purchasing relief supplies is added with the objective value.


Final Code:

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Mar 11 12:21:12 2020

@author: Pritish Roy
"""

from gurobipy import *

# Sets
I = range(0, 9)

J = range(0, 10)

K = range(0, 6)

# Data
demand = [112, 254, 117, 272, 135, 125, 133, 223, 257, 201]

Cost_FSD = [91, 71, 94, 52, 30, 73, 50, 104, 58]

Cost_DDP = [
    [50, 46, 35, 85, 151, 98, 140, 54, 31, 121],
    [67, 57, 42, 79, 144, 90, 132, 54, 50, 115],
    [70, 67, 57, 103, 168, 115, 157, 74, 48, 139],
    [74, 56, 41, 37, 98, 45, 86, 31, 70, 71],
    [100, 81, 67, 47, 94, 47, 80, 55, 95, 72],
    [143, 123, 114, 64, 50, 49, 35, 95, 145, 50],
    [101, 82, 70, 31, 71, 25, 57, 53, 101, 48],
    [182, 163, 154, 102, 64, 87, 57, 134, 185, 80],
    [123, 103, 93, 46, 58, 33, 42, 74, 124, 45]
]

relief_good_cost = 145

maximum_capacity = 790

truck_capacity = 60

Cost_Truck = 20000

truck_allocated_FSD = 6

td_min = 720

open_FSD = 5

M = 10000
########################################################

# Model
m = Model("Pacific Paradise")

# Variables
O = {}
DDP = {}
T_F = {}
T_D = {}
T = {}
for i in I:
    for j in J:
        for k in K:
            O[i] = m.addVar(vtype=GRB.BINARY)
            DDP[i, j, k] = m.addVar(vtype=GRB.INTEGER)
            T_F[i] = m.addVar(vtype=GRB.INTEGER)
            T_D[i, j, k] = m.addVar(vtype=GRB.INTEGER)
            T[i, k] = m.addVar(vtype=GRB.BINARY)

# Objective
# cost of transferring to FSD and DDP nodes, plus the cost of truck
m.setObjective(
    quicksum(
        Cost_FSD[i] * T_F[i] * truck_capacity
        for i in I
    ) +
    quicksum(
        Cost_DDP[i][j] * T_D[i, j, k] * truck_capacity
        for i in I for j in J for k in K
    ) +
    quicksum(
        Cost_Truck * T[i, k]
        for i in I for k in K
    ),
    GRB.MINIMIZE
)

# Set constraints

# at most five FSDs node can be open
m.addConstr(
    quicksum(
        O[i] for i in I) <= open_FSD
                )

# at least one node from the new nodes added to FSD should be open
m.addConstr(
        O[5] + O[6] + O[7] + O[8] == 1
    )

for i in I:
    # each FSD node should have a maximum capacity limit
    m.addConstr(
        quicksum(
            DDP[i, j, k] for j in J for k in K) <= maximum_capacity
    )

    # decision to open or close the FSD nodes by the forcing constraint to avoid infeasibility
    m.addConstr(
        quicksum(DDP[i, j, k] for j in J for k in K) <= M * O[i]
    )

    # number of trips required by FSD nodes given the trucks capacity
    m.addConstr(
        quicksum(
            DDP[i, j, k] for j in J for k in K) <= T_F[i] * truck_capacity
    )

    # truck assigned to an FSD should be less than six
    m.addConstr(
        quicksum(
            T[i, k] for k in K) <= truck_allocated_FSD
    )

    for k in K:
        # each return trip is three times the transportation cost
        # time required for a return trip by a truck should be less than the driven time limit
        m.addConstr(
            T[i, k] * td_min >=
            quicksum(
                3 * Cost_DDP[i][j] * T_D[i, j, k] for j in J
            )
        )

for j in J:
    # supply at each DDP node should be equal to demand
    m.addConstr(
        quicksum(
            DDP[i, j, k] for i in I for k in K) == demand[j]
                )

    for i in I:
        # number of trips required per truck given the truck capacity limit to DDP
        m.addConstr(
                quicksum(
                    DDP[i, j, k] for k in K) <= quicksum(
                    T_D[i, j, k] for k in K
                ) * truck_capacity
        )

# cost of purchasing relief supply
purchase_cost = sum(relief_good_cost * demand[j] for j in J)

# Optimize
m.optimize()

assert not m.isQP | m.isQCP, "Quadratic constraints in formulation"

# Answer
if m.Status == GRB.INFEASIBLE:
    print('Model is Infeasible')

print(f'\nOptimal cost of Transport + Purchase: {m.objVal + purchase_cost}')

print('--------------------------------------------------')

print('\t\t\tFSD ----> DDP')
for i in I:
    print(f'FSD {i} --> TRIP per DDP')
    for k in K:
        print(f"TRUCK {k + 1} ---- {[int(DDP[i, j, k].x) for j in J]}")

print('--------------------------------------------------')

print('Number of TRIP required per FSD')
print(f"{0} ---- {[int(T_F[i].x) for i in I]}")

print('--------------------------------------------------')

print('Number of TRIP required per DDP per TRUCK')
for i in I:
    print(f'FSD {i} --> TRIP per DDP')
    for k in K:
        print(f"TRUCK {k + 1} ---- {[int(T_D[i, j, k].x) for j in J]}")
print('--------------------------------------------------')

print('Number of TRUCK allocated per FSD')
for i in I:
    print(f"FSD {i} ---- {[int(T[i, k].x) for k in K]}")

Runtime

Optimize a model with 192 rows, 2700 columns and 3919 nonzeros

Variable types: 0 continuous, 2700 integer (1080 binary)

Presolve removed 18 rows and 1999 columns

Presolved: 174 rows, 701 columns, 1529 nonzeros

Variable types: 0 continuous, 701 integer (170 binary)

Root relaxation: objective 2.861962e+05, 338 iterations, 0.00 seconds

Explored 38631 nodes (650559 simplex iterations) in 36.41 seconds