Using Modern Tools for Operations Research: Concepts & Codes

Abigail Lindner Regent University

Egbe-Etu 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 supply-chain 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:

1. A set of variables,
   x = [x₁, ..., x_n]^T, x ∈ Rⁿ
   

2. A linear objective function to minimize or maximize
   f(x) = c^Tx, c ∈ Rⁿ
   

3. A set of linear constraints of the form
   a^Tx ≥ b or a^Tx ≤ b or a^Tx = b
   where a ∈ Rⁿ and b ∈ R

• Introduction to linear programming with Python

• Linear programming example in R

• Linear programming and regression analysis in Python

• Linear programming and optimization in Python

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₁, S₂, ..., 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₁, v₂, ..., v_n and weights w₁, w₂, ..., 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 0-1 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 the Greedy Algorithm in R

• The set cover problem using a method other than the Greedy Algorithm in Python

• The knapsack problem using the cvxpy package in Python

• The knapsack problem using PuLP in Python with Jupyter Notebooks

Figure 2: Solution for IP problem (Source: Eudoxus Systems Ltd.)

Mixed-Integer Programming
Mixed-integer 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:

1. A linear objective function to minimize or maximize
   z = c^Tx
   

2. A set of linear constraints of the form
   Ax ≤ b, x ≥ 0 and integer
   where x = [x₁, ..., x_n]^T is the decision variable vector (i.e., the unknowns)
   c = [c₁, ..., c_n]^T is the objective function coefficient vector
   b = [b₁, ..., b_m]^T are the constraint bounds (i.e., the right-hand side)

• Mixed integer programming example with stock investment in Python

• Mixed integer linear programming in R

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ⁿ 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 R for the knapsack problem

• A branch and bound solution in Python for the Traveling Salesman Problem (another classic algorithmic problem)

Figure 3: Tree-like structure for BB problem

Transportation Problems
To discuss transportation problems, we must first consider network-flow 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 network-flow 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.

• Transportation problem in Python using the spaghetti package

• Transportation problem in Python using PuLP

• Transportation problem in R using lp.solve

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.
Multiple-criteria decision analysis (MCDA) is a sub-discipline 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.

• Management decision analysis using Python

• Multi-criteria decision analysis

Figure 4: Decision Tree Analysis (Source: Prachi M. (2019))

References:

1. Bradley, S., Hax, A., and Magnanti, T. (1977). “8 Network Models.” Applied Mathematical Programming. Addison-Wesley Publishing Company. http://web.mit.edu/15.053/www/AMP-Chapter-08.pdf  
2. 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.
3. Howard, R. A. (1988). Decision analysis: practice and promise. Management science, 34(6), 679-695.
4. Trevisan, Luca. (2011). Lecture 8 [PDF]. Stanford University CS261. http://theory.stanford.edu/~trevisan/cs261/lecture08.pdf.

Image Sources:

1. Eudoxus Systems Ltd. (n.d.). How to make integer programming go faster. Eudoxus Systems Ltd., http://www.eudoxus.co.uk/mp-in-action/how-to-use-mp/mpac9702.
2. User: Prachi M. (2019). Decision tree analysis. The Investors Book, https://theinvestorsbook.com/decision-tree-analysis.html.
3. Shokry, S., Tanaka, S., Nakamura, F. Ariyoshi, R. (2018). Bandwidth maximization approach for displaced left-turn crossovers coordination under heterogeneous traffic conditions. Journal of Traffic and Transportation Engineering, 6, 183-196. https://www.researchgate.net/publication/327414612_Bandwidth_Maximization_Approach_for_Displaced_Left-Turn_Crossovers_Coordination_under_Heterogeneous_Traffic_Conditions.
4. Stojiljkovic, Mirko. (2020). Hands-on linear programming: Optimization with Python. Real Python, https://realpython.com/linear-programming-python/.