Using Modern Tools for Operations Research: Concepts & Codes
Share:

Abigail Lindner Regent University 

EgbeEtu Etu Wayne State University 

Evrim Dalkiran, Ph.D. Wayne State University 
Operations research (OR) has been an academic and industry focus that has gained prominence since World War II, being used to optimize, predict and solve challenging problems across many sectors. To help introduce new OR students to the implementation of key optimization techniques, this article reviews several main optimization concepts, as well as implementations in Python and R.
Linear Programming
Linear Programming (LP) is both a fundamental and commonplace form of optimization: many, many problems may be expressed as linear programs (see Figure 1). For example, resource allocation problems and many others from business supplychain applications may be modeled as LPs. We briefly introduce the basics of an LP problem as well as several repositories that may be helpful for implementing a LP:
A set of variables,
x = [x_{1}, ..., x_{n}]^{T}, x ∈ R^{n}A linear objective function to minimize or maximize
f(x) = c^{T}x, c ∈ R^{n}A set of linear constraints of the form
a^{T}x ≥ b or a^{T}x ≤ b or a^{T}x = b
where a ∈ R^{n} and b ∈ R
Figure 1: Graphical overview of LP (Source: Stojiljkovic, (2020)) 
Integer Programming
Integer Programming (IP) operates similarly to LP in that it seeks to optimize a function involving various variables with certain constraints, with the additional restriction that variables assume integer values (see Figure 2). Thus the restriction on variable values determines whether IP or LP should be employed: variables with discrete values (e.g., age) can be assessed via IP; and variables with continuous values (e.g., medicine dosages) can be assessed via LP.
A common problem in IP is set covering. Set covering involves a finite set U and a collection of subsets of U : S_{1}, S_{2}, ..., S_{n}. As an example, facility location problems employ the idea of set covering.
The goal is to identify the fewest number of subsets such that their union is U. Integer programming is employed to solve a set covering problem by considering a binary variable x_{i} for each subset S_{i}, where x_{i} = 1 when S_{i} is selected for inclusion in the union and x_{i} = 0 otherwise (Trevisan, 2011). A solution is obtained thusly:

The objective function minimizes the number of subsets comprising the union, while the constraint specifies that each element of U must appear in at least one of the subsets S_{i}.
Another simple problem that may be solved via IP is the knapsack problem. Consider a knapsack with maximum weight constraint W. Then consider n types of items with corresponding values v_{1}, v_{2}, ..., v_{n} and weights w_{1}, w_{2}, ..., w_{n}. The goal is to pack the knapsack such that the value of the packed items is maximized while respecting the weight capacity of the knapsack. In the 01 IP version of this problem, either one item of a given type may be taken or no items of a given type may be taken. A general knapsack problem allows the "packer" to take more than one item for a given type. For delivery companies, the issue of cargo loading is a knapsack problem.
Given time and perseverance, a student could calculate the solutions for simple examples of either of these problem types but solving by hand becomes unwieldy as the number of variables increases. The links below provide implementations for both the set covering and knapsack problems.
The set cover problem using a method other than the Greedy Algorithm in Python
The knapsack problem using PuLP in Python with Jupyter Notebooks
Figure 2: Solution for IP problem (Source: Eudoxus Systems Ltd.) 
MixedInteger Programming
Mixedinteger programming (MIP) involves problems where some of the decision variables are constrained to be integers (e.g., 0, 1, 2), while other variables take continuous values. Although solution techniques for MIPs have existed for many years, recent advances in computing power, algorithms, and data availability have made it possible to model and solve the world's most complex business problems as increasingly tractable MIPs. A basic mathematical representation of MIP is given as follows:
A linear objective function to minimize or maximize
z = c^{T}xA set of linear constraints of the form
Ax ≤ b, x ≥ 0 and integer
where x = [x_{1}, ..., x_{n}]^{T} is the decision variable vector (i.e., the unknowns)
c = [c_{1}, ..., c_{n}]^{T} is the objective function coefficient vector
b = [b_{1}, ..., b_{m}]^{T} are the constraint bounds (i.e., the righthand side)
Branch and Bound Method
Branch and bound, often abbreviated BB or B&B, is an algorithm that seeks an optimal solution to a variety of mathematical optimization problems (see Figure 3). The technique improves upon the idea of a complete enumeration, wherein each possible solution of the decision variables is considered and represented in an enumeration tree. For a problem with n variables, a tree that completely enumerates all solutions will have 2^{n} leaves. For multivariate problems, complete enumeration quickly becomes unwieldy. Rather than fully exploring solutions, B&B uses a routine called pruning to eliminate the vast majority of solutions quickly and effectively.
To begin, B&B relaxes any integrality constraints for the variables in order to solve for the LP relaxation of the problem, using typical LP techniques. The result provides bounds for subsequent steps. The first node of our branch and bound diagram for a maximization problem, LP(1), will contain the upper bound solution z_{LP}^{*}(1), with variable values z_{LP}^{*}(1), found through the LP relaxation and possibly a lower bound solution z_{IP}^{*}(1) found by a search algorithm, such as rounding down/up each variable value from the LP solution. Whereas z_{LP}^{*}(1) is a relaxed solution, z_{IP}^{*}(1) is a feasible solution to the problem. The optimal integer solution exists between these bounds.
Upon completing the bounding step, the branching process continues: one variable is identified (e.g., having the largest fractional part in x_{LP}^{*}(1)) as the branching variable and two child nodes are created. Suppose the variable x_{k} is selected, having the value x_{k}^{*} in x_{LP}^{*}(1). Two child nodes from node 1 are then created, each with an additional constraint: x_{k} ≥ ceiling(x_{k}^{*}) in one; and x_{m} ≤ floor(x_{k}^{*}) in the other. The resultant LP relaxations for nodes 2 and 3 are solved and z_{LP}^{*}(2) and z_{LP}^{*}(3) are obtained, along with possibly integer solutions z_{IP}^{*}(2) and z_{IP}^{*}(3) through a search algorithm. When new integer solutions, x_{IP}^{*}(2) and x_{IP}^{*}(3), are found, we update the incumbent solution and lower bound LB = max {z_{IP}^{*}(1), z_{IP}^{*}(2), z_{IP}^{*}(3)}. The nodes that have already been explored (branched on), or provide an integer solution to the LP relaxation, or for which z_{LP}^{*} ≤ LB are all fathomed, or pruned from the search tree. As new node problems are solved, we update the upper bound, i.e., UB = max {z_{LP}^{*}(k), k is unfathomed}. Once the bounds are updated, the branching step continues. The process ends when all unfathomed nodes have been explored.
A branch and bound solution in Python for the Traveling Salesman Problem (another classic algorithmic problem)
Figure 3: Treelike structure for BB problem 
Transportation Problems
To discuss transportation problems, we must first consider networkflow problems, as the former are a special case of the latter.
Consider an industrial good produced at various plants and desired at various markets. Each plant has a given capacity and each market has a given need. Transportation from plant to market  from origin to destination  may also pass through intermediate points, rather than going directly from the plant to market. The origins, destinations, and intermediate points may be viewed as nodes in a network. The goal of a networkflow problem is to minimize the cost of production and shipment while satisfying the demands of each destination.
The transportation problem removes the intermediate locations. It may be formulated as follows (Bradley, Hax, and Magnanti, 1977):

The objective minimizes the total cost of transportation for all units, while the constraints ensure that the supply capacity at each origin is respected and the demand at each location is satisfied. This basic formulation assumes that supply meets demand, though this is not always the case.
Decision Analysis
Decision analysis is a formalized method for selecting optimal choices that have uncertain outcomes. This outcome uncertainty can be characterized by probability distributions for variables that represent the key consequences of the considered actions (Howard, 1988). The decision maker's relative preference for the various possible outcomes can then be described by a utility function that also captures the decision maker's attitude toward risk. A logical decision maker thus prefers the action that maximizes a particular mathematical combination of the derived probabilities and utilities. Figure 4 is a graphical illustration of a decision tree.
Multiplecriteria decision analysis (MCDA) is a subdiscipline of operations research that explicitly evaluates multiple conflicting criteria in decision making. Conflicting criteria are typical in evaluating options: cost or price is usually one of the main criteria, and some measure of quality is typically another criterion.
Figure 4: Decision Tree Analysis (Source: Prachi M. (2019)) 
References:
 Bradley, S., Hax, A., and Magnanti, T. (1977). “8 Network Models.” Applied Mathematical Programming. AddisonWesley Publishing Company. http://web.mit.edu/15.053/www/AMPChapter08.pdf
 Cornuéjols, G., Trick, M. Saltzman, M. (1995). A tutorial on integer programming. Clemson University, http://www.math.clemson.edu/~mjs/courses/mthsc.440/integer.pdf.
 Howard, R. A. (1988). Decision analysis: practice and promise. Management science, 34(6), 679695.
 Trevisan, Luca. (2011). Lecture 8 [PDF]. Stanford University CS261. http://theory.stanford.edu/~trevisan/cs261/lecture08.pdf.
Image Sources:
 Eudoxus Systems Ltd. (n.d.). How to make integer programming go faster. Eudoxus Systems Ltd., http://www.eudoxus.co.uk/mpinaction/howtousemp/mpac9702.
 User: Prachi M. (2019). Decision tree analysis. The Investors Book, https://theinvestorsbook.com/decisiontreeanalysis.html.
 Shokry, S., Tanaka, S., Nakamura, F. Ariyoshi, R. (2018). Bandwidth maximization approach for displaced leftturn crossovers coordination under heterogeneous traffic conditions. Journal of Traffic and Transportation Engineering, 6, 183196. https://www.researchgate.net/publication/327414612_Bandwidth_Maximization_Approach_for_Displaced_LeftTurn_Crossovers_Coordination_under_Heterogeneous_Traffic_Conditions.
 Stojiljkovic, Mirko. (2020). Handson linear programming: Optimization with Python. Real Python, https://realpython.com/linearprogrammingpython/.