Scribd
Upload
93 views

Integer Programming

The document discusses integer programming and provides an example problem. Integer programming deals with optimization problems where the variables must take on integer values rather than fractional/continuous values. The example problem aims to minimize the total cost of purchasing 150 contracts from three dealers, where the quantities purchased from each dealer and a binary variable determining if an order is placed are the optimization variables. The document sets up the integer programming model for this example using the PuLP package in Python to define the variables and objective function.

Uploaded by

hachan
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
93 views

Integer Programming

The document discusses integer programming and provides an example problem. Integer programming deals with optimization problems where the variables must take on integer values rather than fractional/continuous values. The example problem aims to minimize the total cost of purchasing 150 contracts from three dealers, where the quantities purchased from each dealer and a binary variable determining if an order is placed are the optimization variables. The document sets up the integer programming model for this example using the PuLP package in Python to define the variables and objective function.

Uploaded by

hachan
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

Integer programming

In the simple optimization problem we investigated earlier, A maximization example with


linear programming, the variables were allowed to be continuous or fractional. What if the
use of fractional values or results is not realistic? This problem is called the linear integer
programming problem, where all the variables are restricted as integers. A special case of
an integer variable is a binary variable that can either be 0 or 1. Binary variables are
especially useful in model decision-making when given a set of choices.

Integer programming models are frequently used in operational research to model real-
world working problems. More often than not, stating nonlinear problems in a linear or
even binary fashion requires more art than science.

A minimization example with


integer programming
Suppose we must go for 150 contracts in a particular over-the-counter exotic security from
three dealers. Dealer X quoted $500 per contract plus handling fees of $4,000, regardless of
the number of contracts sold. Dealer Y charges$450 per contract plus a transaction fee
of $2,000. Dealer Z charges $450 per contract plus a fee of $6,000. Dealer X will sell at most
100 contracts, dealer Yat most 90, and dealer Z at most 70. The minimum transaction
volume from any dealer is 30 contracts if any are transacted with that dealer. How should
we minimize the cost of purchasing 150 contracts?

Using the pulp package, let's set up the required variables:

In [ ]:
"""
An example of implementing an integer
programming model with binary conditions
"""
import pulp

dealers = ['X', 'Y', 'Z']


variable_costs = {'X': 500, 'Y': 350, 'Z': 450}
fixed_costs = {'X': 4000, 'Y': 2000, 'Z': 6000}

# Define PuLP variables to solve


quantities = pulp.LpVariable.dicts('quantity',
dealers,
lowBound=0,
cat=pulp.LpInteger)
is_orders = pulp.LpVariable.dicts('orders',
dealers,
cat=pulp.LpBinary)
The dealers variable simply contains the dictionary identifiers that are used to reference
lists and dictionaries later on. The variable_costs andfixed_costs variables are dictionary
objects that contain the respective contract cost and fees charged by each dealer. The Pulp
solver solves for the values ofquantities and is_orders, which are defined by
the LpVariable function. Thedicts() method tells Pulp to treat the assigned variable as a
dictionary object, using the dealers variable for referencing. Note that
the quantities variable has a lower boundary (0) that prevents us from entering a short
position in any securities. The is_orders values are treated as binary objects, indicating
whether we should enter into a transaction with any of the dealers.

What is the best approach to modeling this integer programming problem? At first glance,
it seems fairly straightforward by applying this equation:

Where the following is true:


The equation simply states that we want to minimize the total costs with the binary
variable, isOrderi, to determine whether to account for the costs

You might also like