APPLICATIONS OF LINEAR PROGRAMMING
Transportation Model and Its Variants(Chapter 5, Taha)
The transportation model is a special class of linear programs that deals with shipping a commodity from sources (for example factories) to destinations (for example warehouses). The objective is to determine the shipping schedule that minimizes the total shipping cost while satisfying supply and demands limits. The application of the transportation model can be extended to other areas of operation, including inventory control (Example 5.2-1, Taha, p. 201-202), employment scheduling, and personnel assignment.
The steps of the transportation algorithm are precisely those of the simplex method. We notice that the special transportation tableau is useful in modeling a class of problems in a concise manner (as opposed to the LP model with explicit objective function and constraints), simplifies the solution of the problem by Excel Solver, and provides interesting ideas about how the basic theory of LP is exploited to produce shortcuts in computations.
Figure 5.1(Taha, p.194) Representation of the transportation model with nodes and arcs
The general problem is represented by a network with m sources and n destinations, each represented by a node, whereas the arcs represent the routes linking the sources and the destinations. Arc arc (i,j) joining source i to destination j carries two pieces of information: the transportation cost per unit, cij, and the amount shipped, xij. The amount of supply at source i is ai and the amount of demand at destination j is bj. The objective of the model is to determine the unknowns xij that will minimize the total transportation cost while satisfying all the supply and demand restrictions. Basic assumption for the transportation algorithm is that the model is balanced, meaning that the total demand equals the total supply. If the model is not balanced, we can always add a dummy source or a dummy destination to restore balance.
The application of the transportation model is not limited to transporting commodities between geographic sources and destinations.
Summary of the Transportation Algorithm
Step 1. Determine a starting feasible solution, and go to step 2.
Step 2. Use the optimality condition of the simplex method to determine the entering variable from all the nonbasic variables.If the optimality condition is satisfied, stop. Otherwise, go to step 3.
Step 3. Use the feasibility condition of the simplex method to determine the leaving variable from among all the current basic variables, and find the new basic solution. Return to step 2.
The Assignment Model
“The best person for a job” is an apt description of the assignment model. The situation can be illustrated by the assignment of workers with varying degrees of skill to jobs. A job that happens to match a worker’s skill costs less than one in which the operator is not as skillful. The objective of the model is to determine the minmum-cost assignment of workers to jobs.
The general assignment model with nworkers andn jobs is represented in Table 5.31 (Taha, 222). The element cij represents the cost of assigning worker i to job j (i, j= 1, 2, …, n). We assume w.l.g. that the number of workers equals the number of jobs, because we can always add fictitious workers or fictitious jobs to satisfy this assumption.
Notice that the assignment model is actually a special case of the transportation model in which the workers represent the sources, and the jobs represent the destinations. The supply (demand) amount at each source (destination) equals 1. The cost of “transporting” worker i to job j is cij. Define xij = 1 if worker i is assigned to job j, and xij = 0 otherwise.
In fact, the assignment model can be solved as a regular transportation model. However, a simple algorithm, called the Hungarian method,is available for solving assignment problems (using hand computations); this algorithm is rooted in the simplex method , just as the transportation model is. Assignment problems can be solved as regular LP using highly efficient computer codes.
The LP model for an assignment problem with n workers and n jobs is given as
Minimize z = ∑i∑j cijxij
subject to
∑j xij = 1, i = 1, 2, …, n
∑i xij = 1, j = 1, 2, …, n
xij = 0 or 1.
The Transshipment Model
The transshipment model recognizes that it may be cheaper to ship through intermediate or transient nodes before reaching the final destination. This model can be converted to (and solved as) a regular model using the idea of a buffer(B = Total supply (or demand))( Example 5.5-1 (Taha, p. 229-230).
Each node of the network with both input and output arcs acts as both a source and a destination and is referred to as a transshipment node. The remaining nodes are either pure supply nodes or pure demand nodes. Supply at a transshipment node equals the sum of the original supply and the buffer amount; demand at a transshipment node equals the sum of the original demand and the buffer amount.
Network Models(Chapter 6, Taha)
The network models include the traditional applications of:
- finding the most efficient way to link a number of locations directly or indirectly;
- finding the shortest route between two cities;
- determining the maximum flow in a pipeline network;
- determining the minimum-cost flow in a network that satisfies supply and demand requirements at different locations;
- scheduling the activities of a project (i.e. determination of start and completion dates for the activities);
- designing a pipeline network with minimum cost of constructing the pipeline.
Some nontraditional applications of these models:
- The shortest-route model can be used to determine the optimal equipment replacement policy;
- The maximum-flow model can be used to determine the optimum number of ships that meet a specific shipment schedule.
The solution of such situations, and others like them, is accomplished through a variety of network optimization algorithms, such as: minimal spanning tree algorithm, shortest-route algorithms (Dijkstra’s algorithm, Floyd’s algorithm), maximal-flow algorithm, critical path (CPM) algorithm.
Here, the formulation and solution of a network model as an LP is emphasized. Most commercial codes solve network problems as mere linear programs. Additionally, some formulations require imposing side constraints, which can be implemented only if the problem is solved as an LP. Excel Solver can be used for large-scale problems.
A multitude of OR situations can be modeled and solved as networks (nodes connected by branches)
Real-Life applications -- Saving Federal Travel Dollars
U.S. Federal Government employees are required to attend development conferences and training courses in different locations around the country. Because the federal employees are located in offices scattered around the United States, the selection of the host city impacts travel cost. Currently, the selection of the city hosting conference/training events is done without consideration of the incurred travel cost. The problem seeks the determination of the optimal location of the host city. For Fiscal Year 1997, the developed model was estimated to save at least $400,000. (Case 24 in Chapter 24 (Taha) on the CD provides the details of the study.)
Linear Programming Formulation of the Shortest-Route Problem
Suppose that the shortest-route network includes n nodes and that we desire to determine the shortest route between any two nodes s and t in the network. The PL assumes that one unit of flow enters the network at node s and leaves at node t.
Define
xij = amount of flow in arc (i, j). Then, xij = 1 if arc (i, j)is on the shortest route and equal 0 otherwise.
cij = length of arc (i, j).
The objective function of the LP is
Minimize z = ∑ cijxij
(i,j)
The constraints represent the conservation-of-flow equation(total input flow = total output flow) at each nodej:
External input into node j + ∑i xij = External output from node j + ∑k xjk
All defined (i, j) All defined (j, k)
Notice that the column xij has exactly one “1” entry in row i and one “−1”entry in row j, a typical property of a network LP.
Linear Programming Formulation of Maximal Flow Model
Define xij as the amount of flow in arc (i, j) with capacity Cij. The objective is to determine xij for all i and j what will maximize the flow between start node s and terminal node t subject to flow restrictions (input flow = output flow) at all but nodes s and t.
Linear Programming Formulation of CPM
A CPM problem can be though of as the opposite of the shortest-route problem, in the sense that we are interested in finding the longest route of a unit flow entering at the start node and terminating at the finish node, We can thus apply the shortest-route LP formulation to CPM in the following manner. Define
xij = amount of flow in activity (i, j), for all defined i and j
Dij = Duration of activity (i, j), for all defined i and j.
Maximize z = ∑ Dijxij
( i, j)
subject to
total input flow at node j = total out flow at node j, for each j; all xij ≥ 0.
INTEGER LINEAR PROGRAMMING(Chapter 9, Taha)
Integer linear programs (ILPs) are LPs with some or all the variables restricted to inter (or discrete) values.
We start with a number of applications that demonstrate the rich use of ILP in practice.
The applications generally fall into two categories: direct and transformed.
In the direct category, the variables are naturally integer and may assume binary (0 or 1) or general discrete values. For example, the problem may involve determining whether or not a project is selected for execution (binary) or finding the optimal number of machines needed to perform a task (general discrete values).
In the transformed category, the original problem, which may not involve any integer variables, is analytically intractable. Auxiliary integer variables (usually binary) are used to make it tractable. For example, in sequencing two jobs, on a single machine, job A may precede job B or the way around. The “or” nature of the constraints is what makes the problem analytically intractable, because all mathematical programming algorithms deal with “and” constraints only. The situation is remedied by using auxiliary binary variables to transform the “or” constraints” in “and” constraints.
For convenience, a pure ILP is defined to haveall integer variables. Otherwise a problem is a mixed ILP if it deals with both continuous and integer variables.
ILLUSTRATIVE APPLICATIONS
- Capital Budgeting
It deals with decisions regarding whether or not investments should be made in individual projects. The decision is made under limited-budget considerations as
well as priorities in the execution of the projects.
Example 9.1-1 (Project Selection) (Taha, p. 350-351)
- Set-Covering Problem
In this class of problems, overlapping services are offered by a number of installations to a number of facilities. The objective is to determine the minimum number of installations that will cover (i.e. satisfy the needs) of each facility. For example, water treatment plants can be constructed at various locations, which each plant serving different sets of cities. The overlap arises when a given city can receive service from more than one plant.
Example 9.1-2 (Installing Security Telephones) (Taha, p. 354-355)
- Fixed-Charge Problem
This problem deals with situations in which the economic activity incurs two types of costs: an initial “flat” fee that must be incurred to start the activity and a variable cost that is directly proportional to the level of the activity. For example, the initial tooling of a machine prior to starting production incurs a fixed setup cost regardless of how many units are manufactured. Once the setup is done, the cost of labor and material is proportional to the amount produced. Given that F is the fixed charge, c is the variable unit cost, and x is the level of production, the cost function is expressed as C(x) = F + cx, if x > 0 and equals 0 otherwise. The function C(x) is intractable analytically at x = 0. Binary variables can be used to remove this intractability.
Example 9.1-3 (Choosing a Telephone Company) (Taha, p.360-361)
- Either-Or and IF-Then Constraints
Models in which constraints are not satisfied simultaneously (either-or) or are dependent (if-then) can be dealt with by using binary variables to obtain the desired format of “and” constraints.
Example 9.1-4 (Job Sequencing Model) (Taha, p. 364-366)
Real-Life Application – Optimizing Trailer Payloads at PFG Glass
PFG uses specially equipped (fifth-wheel) trailers to deliver packs of sheets of flat glass to customers. The packs vary in both size and weight, and a single trailer load may include different packs, depending on received orders. Government regulations set maximum limits on axle weights, and the actual positioning of the packs on the trailer is crucial in determining these weights. The problem deals with determining the optimal loading of the packs on the trailer bed to satisfy axle-weight limits. The problem is solved as an ILP. (Case 7 in Chapter 24, Taha, on the CD provides the details of the study.)
Integer Programming Algorithms
We present two prominent algorithms of ILP: branch and bound (B&B) and cutting plane. Of the two algorithms, B&B is decidedly more efficient computationally. Practically, all commercial codes are rooted in B&B. A drawback of ILP algorithms is their lack of consistency in solving ILPs. Although these algorithms are proven theoretically to converge in a finite number of iterations, their implementation on the computer (with its inherent machine round-off error) is a different experience. The algorithms are based on exploiting the tremendous computational success of LP. The strategy of these algorithms involves three steps.
Step 1. Relax the solution space of the ILP by deleting the integer restrictions on all integer variables and replacing any binary variable y with the continuous range 0 ≤ y ≤ 1. The result of the relaxation is a regular LP.
Step 2. Solve the LP, and identify its continuous optimum.
Step 3.Starting from the continuous optimum point, add special constraints that iteratively modify the LP solution space in a manner that will eventually render an optimum extreme point satisfying the integer requirements.
Two general methods have been developed for generating the special constraints in step 3:
- Branch-and-bound (B&B)
- Cutting-plane method
Summary of the B&B Algorithm (developed by A. Land and G. Doig for the general mixed and pure ILP problem in 1960).Assuming a maximization problem, set an initial lower bound z = −∞ on the optimum objective value of ILP. Set i = 0.
Step 1. (Fathoming/bounding) Select LPithe next subproblem to be examined. Solve LPi, and attempt to fathom it using one of three conditions:
(a)The optimal z-value of LPi cannot yield a better objective value than the current lower bound.
(b)LPi yields a better feasible integer solution than the current lower bound.
(c)LPi has no feasible solution.
Two cases will arise:
(a)If LPi is fathomed and a better solution is found, update the lower bound. If all subproblems have been fathomed, stop; the optimum ILP is associated with the current finite lower bound. If no finite lower bound exists, the problem has no feasible solution. Else, set i = i + 1, and repeat step 1.
(b)If LPi is not fathomed, go to step 2 for branching.
Step 2. (Branching) Select one of the integer variables xj, whose optimum value xj* in the LPi solution is not integer. Eliminate the region
[xj*] < xj < [xj*] + 1
(where [v] defines the largest integer ≤ v) by creating two LP subproblems that correspond to
xj ≤ [xj*] and xj ≥ [xj*] + 1.
Set i = i + 1, and go to step 1.
Example 9.2-1(Taha, p. 370-375) (to be studied during Lab hours)
Remark. For minimization problems, we replace the lower bound with an upper bound whose initial value is z = +∞.
The B&B algorithm can be extended directly to mixed problems (in which only some of the variables are integer). If a variable is continuous, we simply never select it asa branching variable. A feasible subproblem provides a new bound on the objective value if the values of the discrete variables are integer and the objective value is improved relative to the current bound.
In 1965, E. Balas developed the additive algorithm for solving ILP problems with pure binary variables. It was shown to be but a special case of the general B&B algorithm.
Cutting-Plane Algorithm
As the B&B algorithm, the cutting-plane algorithm also starts at the continuous optimum LP solution. Special constraints (called cuts) are added to the solution space in a manner that renders an integer optimum extreme point.
Example 9.2-2 (Taha, p. 379-383) (to be studied during Lab hours)
Computational Considerations in ILP
B&B is more reliable. In most cases,the cutting-plane method is used in a secondary capacity to improve B&B performance at each subproblem by eliminating a portion of the solution space associated with a subproblem.
The most important factor affecting computations in ILP is the number of integer variables and the feasibility range in which they apply. It may be advantageous to reduce the number of integer variables in the ILP model as much as possible. Suggestions:
- Approximate integer variables by continuous ones wherever possible.
- For integer variables, restrict their feasible ranges as much as possible,
- Avoid the use of nonlinearity in the model.
Traveling Salesperson (TSP) Problem
Historically, the TSP problem deals with finding the shortest (closed) tour in an n-city situation where each city is visited exactly once. The problem, in essence, is an assignment model that excludes subtours.