Integer Optimization and the Network Models
Standard linear program assumes that decision variables are continuous. However, in many applications, fractional values may be of little use as shown in some presented useful applications.
To search the site, try Edit | Find in page [Ctrl + f]. Enter a word or phrase in the dialogue box, e.g. "parameter " or "linear " If the first appearance of the word/phrase is not what you are looking for, try Find Next.
MENU
- Introduction to Network Models
- Transportation Problems
- Assignment Problems
- Shortest Path Problems
- Maximum Flow Problems
- Critical Path in Project Plan Networks
- Minimum Cost Flow Problems
- Sensitivity Analysis for the Network Models
- References and Further Readings
General Integer Linear Programs
- Introduction & Summary
- Integer LP Programs by LINDO
- Mixed Integer Programs Application: "Either-Or" Constraints
- Conditional Relations Among Constraints
- Off-On Constraints
- Off-On Intervals
- A Case of Discrete Finite Valued Variable
- 0 - 1 Integer Linear Programs (binary LP): The Knapsack Problem
- Traveling Salesperson Problem
- Capital Budgeting Applications
- Scheduling Problems
- Marketing Application
- The Cutting Stock Problem
- An Engineering Application: Mixing Substances
Companion Sites:
- Linear Optimization Solvers to Download
- Success Science
- Leadership Decision Making
- Linear Programming (LP) and Goal-Seeking Strategy
- Artificial-variable Free LP Solution Algorithms
- Tools for LP Modeling Validation
- The Classical Simplex Method
- Zero-Sum Games with Applications
- Computer-assisted Learning Concepts and Techniques
- Linear Algebra and LP Connections
- From Linear to Nonlinear Optimization with Business Applications
- Sensitivity Region for LP Models
- Zero Sagas in Four Dimensions
- Probabilistic Modeling
- Systems Simulation
- Keywords and Phrases
- Collection of JavaScript E-labs Learning Objects
- Compendium of Web Site Review
- Decision Science Resources
Introduction to Network Models
Network models are applicable to an enormous variety of decision problems that can be modeled as networks optimization problems and solved efficiently and effectively. Some of these decision problems are really physical problems such as transportation or flow of commodities. However, many network problems are more of an abstract representation of processes or activities such as the critical path activity network in project management.
The family of network optimization problems includes the following prototype models: assignment, critical path, max flow, shortest path, transportation, and min cost flow problems. These problems are easily stated by using a network of arcs, and nodes.
What is a node? Often called a vertex, or point. It is normally represented by a circle. In a transportation Network, these might be locations or cities on a map.
What is an arc? Often called an edge, or arrow. It may be either directed or undirected. The head is the destination, the tail is the origin. The head and tail are Nodes that are at either end. In a transportation network, the Arcs might be roads, or navigation channels in rivers, or aircraft flight patterns. They supply connectivity between the Nodes. A one-way street might be represented by a directed arc. A two-way street might be an undirected arc or by two directed arcs that point in opposite directions.
A network with n nodes could have as many as n! /[(n-2)! 2!] = n(n-1)/2 arcs. If directed, this number might be doubled. This large number of possible arcs is one of the reasons why there are special solution algorithms for special types of network problems.
Transportation Problem
Transportation models play an important role in logistics and supply chain management for reducing cost and improving service. Therefore, the goal is to find the most cost effective way to transport the goods.A shipper having m warehouses with supply ai of goods at his ith warehouse must ship goods to n geographically dispersed retail centers, each with a given customer demand ej, which must be met. The objective is to determine the minimum possible transportation costs given the unit cost of transportation between the ith warehouse and the jth retail center is Cij.
In the following problem the goal is to find the most effective way to transport the goods. The supply at each source is designated and the demand at each destination is also given. For example, source 3 has 800 units available and destination 1 needs at least 1100 units. Each route from one source to one destination is assigned a unit transportation cost.
Using any LP package, the solution tells the quantity to be shipped from one source to a destination. The results are:
Send 850 units from source 1 to destination 1
Send 350 units from source 1 to destination 2
Send 250 units from source 2 to destination 1
Send 750 units from source 2 to destination 4
Send 50 units from source 3 to destination 2
Send 750 units from source 3 to destination 3
The total shipment cost is $84000.
The Dual of the Transportation Problem:
The dual problem for the above numerical example is:
Max 1200U1 + 1000U2 + 800U3 + 1100V1 + 400V2 + 750V3 + 750V4
subject to:
U1 + V1 £ 35, U1 + V2 £ 30, U1 + V3 £ 40, U1 + V4 £ 32
U2 + V1 £ 37, U2 + V2 £ 40, U2 + V3 £ 42, U2 + V4 £ 25
U3 + V1 £ 40, U3 + V2 £ 15, U3 + V3 £ 20, U3 + V4 £ 28
all Ui and Vj are unrestricted in sign.
The dual formulation suggests that we try to ship the goods in such a way that the difference in unit price Ui at the ith origin and unit price Vj at the jth destination does not to exceed the unit transportation cost between the ith origin and jth destination.
The interpretation of dual constraints as the aim that origin-destination difference in price does not exceed transport price is equivalent to the principle of equilibrium with a sound economic meaning. Moreover, one can interpret the dual objective as the aim of a shipper to maximize the profit when purchasing at origin and selling at destination.
To solve the dual problem, you may like to try the Algebraic Method.
Discrete Transportation Problem: In the discrete transportation problem the entire supply from a given source must be sent to only one of the available destinations, therefore it is an instance of the Generalized Assignment Problem (GAP). The GAP model can be formulated as a discrete (0-1) generalized network problem with supplies of 1 at the source, and multipliers known as the gain- factors on the arcs. Each arc can carry a flow of only 0 or 1, but the amount of flow delivered to the destination equals the value of the multiplier on the arc.
Assignment Problem
Typically, we have a group of n "applicants" applying for n "jobs," and the non-negative cost Cij of assigning the ith applicant to jth job is known. The objective is to assign one job to each applicant in such a way as to achieve the minimum possible total cost. Define binary variables Xij with value of either 0 or 1. When Xij = 1, it indicates that we should assign applicant i to job j. Otherwise (Xij = 0), we should not assign applicant i to job j.A special case of the transportation problem is the assignment problem, which occurs when each supply is 1 and each demand is 1. In this case, the integrality implies that every supplier will be assigned one destination and every destination will have one supplier. The costs give the basis for assigning a supplier and destination to each other.
Suppose we want to impose the condition that either person i should not perform job j OR person k should not perform job m. That is Xij.Xkm = 0. This nonlinear condition is equivalent to the linear constraint Xij + Xkm £ 1. This constraint should be added to the set of constraints as a side constraint. With this additional constraint, the AP becomes a binary ILP, which could be solved by many software packages such as LIND or QSB.
In the following problem the goal is to assign people to particular tasks while minimizing total cost. The objective function takes into account the cost involved for each person to do a particular task. The constraints say that each person must be assigned to a task, and each task must be given to a person.
After running the problem on any LP solver, the results are:
Person 1 should do job 3
Person 2 should do job 4
Person 3 should do job 5
Person 4 should do job 1
Person 5 should do job 2
The total cost is $55.
The Dual of the Assignment Problem:
The dual problem for the above numerical example is:
Max U1 + U2 + U3 + U4 + U5 + V1 + V2 + V3 + V4 + V5
subject to:
U1 + V1 £ 10, U1 + V2 £ 4, U1 + V3 £ 6, U1 + V4 £ 10, U1 + V5 £ 12
U2 + V1 £ 11, U2 + V2 £ 7, U2 + V3 £ 7, U2 + V4 £ 9, U2 + V5 £ 14
U3 + V1 £ 13, U3 + V2 £ 8, U3 + V3 £ 12, U3 + V4 £ 14, U3 + V5 £ 15,
U4 + V1 £ 14, U4 + V2 £ 16, U4 + V3 £ 13, U4 + V4 £ 17, U4 + V5 £ 17
U5 + V1 £ 19, U5 + V2 £ 11, U5 + V3 £ 17, U5 + V4 £ 20, U5 + V5 £ 19
all Ui and Vj are free-variables.
The dual formulation suggests that we try to assign in such a way that the sum of value Ui of the ith person and added value Vj to perform the jth job, not to exceed the cost of assigning ith person to the jth job.
To solve the dual problem, you may like to try the Algebraic Method.
Visit also the Web site Assignment Problem Software.
Shortest Path Problem
The problem is to determine the best way to traverse a network to get from an origin to a given destination as cheaply as possible. Suppose that in a given network there are m nodes and n arcs (i.e. edges) and a cost Cij associated with each arc (i to j) in the network. Formally, the Shortest Path (SP) problem is to find the shortest (least cost) path from the start node 1 to the finish node m. The cost of the path is the sum of the costs on the arcs in the path. Define binary variables Xij, where Xij =1 if the arc (i to j) is on the SP and Xij = 0 otherwise. There are two special nodes, called the origin and destination. The objective is to find a shortest path between the origin and destination.In the following network various costs are assigned for the path from one node to another. For example, the cost from node 2 to node 4 is 6. The objective function considers the cost to move from each node to another from source to destination. The constraints are broken into three groups. The constraint for the origin node says that you must leave node 1 and go to node 2 or 3. The intermediate node constraints say that if you ever come into a node you must leave that node. The destination node is similar to origin node in that you must reach to this node from one of the neighboring node.
Consider the following directed network (for an undirected network, make each arc directed in both directions, then apply the same formulation. Note that in this case you have Xij and Xji variables). The aim is to find the shortest path from node 1 to node 7.
After running this problem on any LP solver, the results are:
Go from 1 to 3
Go from 3 to 5
Go from 5 to 6
Go from 6 to 7
This is the shortest path with total of 22 length (cost) units.
Construct the dual problem for the above numerical example and provide an interpretation. Solve the dual problem by the Algebraic Method.
Notice that, the output of LP software packages with respect to sensitivity analysis for the network problems could be misleading. Therefore, for the shortest-path sensitivity analysis, read the following article:
Arsham H., Stability analysis for the shortest path problems, Journal of Congressus Numerantium, Vol. 133, No. 1, 171-210, 1998.
Maximum Flow Problem
In a network with flow capacities on the arcs, the problem is to determine the maximum possible flow from the source to the sink while honoring the arc flow capacities. Consider a network with m nodes and n arcs with a single commodity flow. Denote the flow along arc (i to j) by Xij. We associate with each arc a flow capacity, kij. In such a network, we wish to find the maximum total flow in the network, F, from node l to node m.In the LP formulation, the objective is to maximize F. The amount that leaves the origin by various routes. For every intermediate node, what comes in must be equal to what goes out. In some routes the flow can go both ways. The capacity amount that can be sent in a particular direction is also shown on the each route.
After solving this LP problem using say LINDO, the results are as follow:
Send 10 units from 1 to 2
Send 7 units from 1 to 3
Send 3 units from 2 to 6
Send 7 units from 2 to 4
Send 4 units from 3 to 6
Send 6 units from 3 to 5
Send 7 units from 4 to 7
Send 8 units from 5 to 7
Send 3 units from 6 to 3
Send 2 units from 6 to 5
Send 2 units from 6 to 7
The maximum flow is F = 17 units.
The Dual of the Maximum Flow Problem:
The dual problem for the above numerical example is:
Min 10Y12 + 10Y13 + Y23 + Y32 + 6Y26 + 4Y36 + 4Y63 + 8Y24
3Y64 + 3Y46 + 12Y35 + 2Y65 + 2Y56 + 8Y75 + 7Y47 + 2Y67
subject to:
X2 - X1 + Y12 ³ 0, X3 - X1 + Y13 ³ 0, X3 - X2 + Y23 ³ 0,
X3 - X2 + Y32 ³ 0,
X6 - X2 + Y26 ³ 0,
X6 - X3 + Y36 ³ 0,
X3 - X6 + Y63 ³ 0,
X4 - X2 + Y24 ³ 0,
X4 - X6 + Y64 ³ 0
X6 - X4 + Y46 ³ 0,
X5 - X3 + Y35 ³ 0,
X5 - X6 + Y65 ³ 0,
X6 - X5 + Y56 ³ 0,
X5 - X7 + Y75 ³ 0,
X7 - X4 + Y47 ³ 0,
X7 - X6 + Y67 ³ 0,
X1 - X7 ³1, and
Yij ³ 0, and all Xi are free-variables.
The dual formulation suggests that we try to assign flow to arcs in such a way that for each arc, the difference in values at the beginning node and the end node exceeds the added value.
To solve the dual problem, you may like to try the Algebraic Method.
Visit also the Web site Maximum Flow Problem.
Critical Path in Project Plan Network
The successful management of large projects, be they construction, transportation, or financial, relies on careful scheduling and coordinating of various tasks. Critical Path Method (CPM) attempts to analyze project scheduling. This allows for better control and evaluation of the project. For example, we want to know how long will the project take? When will we be able to start a particular task? If this task is not completed on time, will the entire project be delayed? Which tasks should we speed up (crash) in order to finish the project earlier?Given a network of activities, the first problem of interest is to determine the length of time required to complete the project and the set of critical activities that control the project completion time. Suppose that in a given project activity network there are m nodes, n arcs (i.e. activities) and an estimated duration time, Cij, associated with each arc (i to j) in the network. The beginning node of an arc corresponds to the start of the associated activity and the end node to the completion of an activity. To find the Critical Path (CP), define the binary variables Xij, where Xij = 1 if the activity i j is on the CP and Xij = 0 otherwise. The length of the path is the sum of the duration of the activities on the path. The length of the longest path is the shortest time needed to complete the project. Formally, the CP problem is to find the longest path from node 1 to node m.
Each arc has two roles: it represents an activity and it defines the precedence relationships among the activities. Sometimes it is necessary to add arcs that only represent precedence relationships. These dummy arcs are represented by dashed arrows. In our example, the arc from 2 to 3 represents a dummy activity.
The first constraint says that the project must start. For each intermediate node, if we ever reach it we have to leave that node. Finally, the last constraint enforces the completion of the project.
Running the LP formulation on any LP solver, the critical path is:
From node 1 to 2
From node 2 to 3
From node 3 to 4
From node 4 to 5
From node 5 to 6
The duration of the project is, therefore 38 time units.
The Dual of the Critical Path Problem:
The dual problem for the above numerical example is:
Min Z
subject to:
-T1 + T2 ³ 9,
-T1 + T3 ³ 6,
-T2 + T3 ³ 0,
-T3 + T4 ³ 7,
-T3 + T5 ³ 8,
-T4 + T5 ³ 10,
-T5 + T6 ³ 6,
-T6 + Z ³ 6,
and all variables are ³ 0
The dual formulation suggests that for any activity, the difference between finish and starting times exceeds the duration of the activity.
To solve the dual problem, you may like to try the Algebraic Method.
Read also Critical Path Method
Minimum Cost Flow Problem
All the above network problems are special cases of the minimum cost flow problem. Like the maximum flow problem, it considers flows in networks with capacities. Like the shortest path problem, it considers a cost for flow through an arc. Like the transportation problem, it allows multiple sources and destinations. Therefore, all of these problems can be seen as special cases of the minimum cost flow problem.The problem is to minimize the total cost subject to availability and demand at some nodes, and upper bound on flow through each arc.
The optimal solution is: X12 = 12, X13 = 8, X23 = 8, X24 = 4, X34 = 11, X35 = 5, X45 = 10, all other Xij = 0. The optimal cost is $150.
The Dual of the Minimum Cost Flow Problem:
The dual problem for the above numerical example is:
Max 15Y12 + 8Y13 + 5Y35 + 4Y24 + 15Y34 + 10Y25 + 4Y53 + 10Y25
subject to:
X2 - X1 + Y12 £ 4, X3 - X1 + Y13 £ 4,
X3 - X2 + Y23 £ 2,
X4 - X2 + Y24 £ 2, X5 - X2 + Y25 £ 6, X4 - X3 + Y34 £ 1,
X5 - X3 + Y35 £ 3, X5 - X4 + Y45 £ 2, X3 - X5 + Y5 £ 1,
Yij £ 0,
and all Xi are free-variables.
The dual formulation suggests that we try to assign flow to the arcs in such a way that for each arc the difference in values at the beginning node and the end node as well as added value not to exceed the cost assigned to that arc.
To solve the dual problem, you may like to try the Algebraic Method.
Sensitivity Analysis for the Network Models
The family of classical network optimization problems includes the following prototype models: assignment, critical path, max flow, shortest path, and transportation. Although it is long known that these problems can be modeled as linear programs, it is generally not done. Due to the relative inefficiency and complexity of the simplex methods (primal, dual, and other variations) for network models, these problems are usually treated by one of over 400 specialized algorithms.This leads to several difficulties. The solution algorithms are not unified and each algorithm uses a different strategy to exploit the special structure of a specific problem. Furthermore, small variations in the problem such as the introduction of side constraints, or multi-index, destroy the special structure and requires restarting the algorithm. Also, these algorithms obtain solution efficiency at the expense of managerial insight, as the final solutions from these algorithms do not have sufficient information to perform sensitivity analysis.
Another approach is to adapt the simplex to network optimization problems through network simplex. This provides unification of the various problems but maintains all the inefficiencies of simplex as well as most of the network inflexibility to handle changes such as side constraints. Even ordinary sensitivity analysis (OSA), long available in the tabular simplex, has been only recently transferred to network simplex.
Warning: Computer solutions for the network problems are valid, however the produced sensitivity results may not be valid. This is due to the facts that, among other things, these problems are Integer-LPs, and any one constraint in any of these models is a redundant constraint.
Since the "path" taken by Branch-and-bound and Branch-and-Cut and other methods can be very different for small changes in the value of the parameter, we have developed, see the references, new solution algorithms, which allow us to perform various forms of sensitivity analysis.
Cost Perturbation Analysis: General Perturbation Set, Parametric Sensitivity Analysis, Ordinary Sensitivity Analysis, The 100% Rule, Tolerance Analysis
Arc Capacity Perturbation Analysis: General Perturbation Set, Parametric Sensitivity Analysis, Ordinary Sensitivity Analysis, The 100% Rule, Tolerance Analysis
Supply and Demand Perturbation Analysis: General Perturbation Set, Parametric Sensitivity Analysis, Ordinary Sensitivity Analysis, The 100% Rule, Tolerance Analysis
References and Further Readings
For full treatments of various forms of sensitivity analysis for the network models, read the following articles:
Arsham, H., Stability Analysis of the Critical Path in Project Activity Networks, Civil Engineering and Environmental Systems, Vol. 15, No. 4, 305-334, 1999.
Arsham, H., A Warm-start Dual Simplex Solution Algorithm for the Minimum Flow Network with Postoptimality Analysis, Mathematical and Computer Modelling, Vol. 27, No. 12, 85-115, 1998.
Arsham H., Distribution-routes Stability Analysis of the Transportation Problem, Optimization, Vol. 43, No. 1, 47-72, 1998.
Arsham H., Managing Cost Uncertainties in Transportation and Assignment Problem, Journal of Mathematics & Decision Sciences, Vol. 2, No. 1, 65-102, 1998.
Arsham H., A Comprehensive Simplex-Like Algorithm for Network Optimization and Perturbation Analysis, Optimization, Vol. 32, No. 3, 211-267, 1995.
Arsham H., Managing Project Activity-Duration Uncertainties, Omega: Journal of Management Science, Vol. 21, No. 2, 111-122, 1993.
Arsham H., Postoptimality Analysis for the Transportation Problem, Journal of the Operational Research Society, Vol. 43, No. 1, 121-139, 1992.
Kerzner H., Project Management: A Systems Approach to Planning, Scheduling, and Controlling, Wiley, 2003.
Pallottino S., and M. Scutella, A New Algorithm for Reoptimizing Shortest Paths When the Arc Costs Change, Operations Research Letters, Vol. 31, No. 2, 149-160, 2003.
More recent references may be found at Bibliography for Optimization with Sensitivity Analysis
Visit also the Web sites:
Network Flows Resources
Traveling Salesman Problem
General Integer Linear Programs
Standard LP assumes that decision variables are continuous. However, in many applications, fractional values may be of little use (e.g., 2.5 employees). On the other hand, as you know by now, since integer linear programs are more difficult to solve, you might ask why bother. Why not simply use a standard linear program and round the answers to the nearest integers? Unfortunately, there are two problems with this:
- The rounded solution may be infeasible; and
- Rounding may not give an optimal solution.
Doing Integer LP by Excel Solver: Using the Constraint menu, for the LP Problem, select Normal Constraint and then the icon for “< = “ to obtain the Add Constraint window. Then we can designate any variable (e.g. , inter the variable, say $B$5 in the Cell Reference) as Integer in the Add Constraint window.
For example, in the Wilson problem if you change cell F7 t0 3299 sq ft. Baseball dozens(B4) and softball dozens(C4) come up to 209.5 and 375.25 respectively. Then when you change B4 and C4 to int, the answer comes up to 211 and 374. When you change to Binary Cells C4 and B4 go to 1 if any anser is greater than 0. They go to 0 if the answer is 0.
Max 11X1 + 10X2
S.T. 2X1 + X2 £ 12
X1 - 3X2 ³ 1
END
GIN X1
GIN X2
The output after 7 iterations is:
OBJECTIVE FUNCTION VALUE
1) 66.00000
VARIABLE VALUE REDUCED COST
X1 6.000000 -11.000000
X2 0.000000 -10.000000
ROW SLACK OR SURPLUS
2) 0.000000
3) 5.000000
Had we not specified X1 and X2 to be general integers in this model, LINDO would not have found the optimal solution of X1 = 6 and X2 = 0. Instead, LINDO would have treated X1 and X2 as continuous and returned the solution of X1 = 5.29 and X2 = 1.43.
Note also, that simply rounding the continuous solution to the nearest integer values does not yield the optimal solution in this example. In general, rounded continuous solutions may be non optimal and, at worst, infeasible. Based on this, one can imagine that it can be very time consuming to obtain the optimal solution to a model with many integer variables. In general this is true, and you are best off utilizing the GIN feature only when absolutely necessary.
As a final note, the GIN command also accepts an integer value argument in place of a variable name. The number corresponds to the number of variables you want to be general integers. These variables must appear first in the formulation. Thus, in this simple example, we could have replaced our two GIN statements with the single statement: GIN 2.
Most commercial solvers use the "branch and bound" or "branch and cut" method in solving IP. The first step is usually is to relax the IP to an LP problem, However, some software, such as CPLEX will then automatically execute heuristic methods to round the LP solution to get a good (and feasible) solution to the IP. The difference between your doing this yourself and letting an IP solver do it is that the IP solver is likely to consider the payback constraint sacrosanct and reject any rounded solution that violates it.
Integer LP Programs by LINDO
Suppose in the Carpenter’s Problem ever table needs four chairs; then the LP formulation is:
Max 5X1+3X2
S.T.
2X1+X2 £ 40
X1 + 2X2 £50
4X1 - X2 = 0
X1 ³ 0
X2 ³ 0
End
GIN X1
GIN X2
GIN stands for general integer variable.
The optimal solution is (X1 = 5, X2 = 20) with optimal value of 85.
Special case of binary variables (X= 0 or 1) is also permitted in LINDO, the command to make the variable X a binary variable is INT X1.
Mixed Integer Programming Application: "Either-Or" Constraints
Suppose a bakery sells eight varieties of doughnuts. The preparation of varieties 1, 2, and 3 involves a rather complicated process, and so the bakery has decided that it would rather not bake these varieties unless it can bake and sell at least 10 dozen doughnuts of varieties 1, 2, and 3 combined. Suppose also that the capacity of the bakery prohibits the total number of doughnuts baked from exceeding 30 dozens, and that the per unit profit for a variety j doughnut is Pj dollars. If we let Xj, j = 1, 2, … ,6 denote the number of dozens of doughnut variety j to be baked, then the maximum profit can be found by solving the following problem (assuming the bakery can sell everything it bakes):
Maximize Z = S Pj Xj
Subject to the constraints: S Xj £ 30
X1 + X2 + X3 = 0, OR, X1 + X2 + X3 ³ 10
Where all variables are nonnegative. The above "either-or" constraint can be handled as such: Let y be a 0-1 variable. Then an equivalent problem is:
Maximize Z = S Pj Xj
Subject to: S Xj £ 30
X1 + X2 + X3 - 30y £ 0,
X1 + X2 + X3 - 10y³ 10
Xj ³ 0, y = 0, or 1.
Conditional Relations Among Constraints
Suppose that, in order for a certain variable X to be positive, it is necessary that another variable Y exceed a certain threshold value. This conditional statement can be reformulated as:
Since a conditional statement can be expressed as and either-or statement by negating the hypotheses. The either-or statement can be expressed as:
Where M is a very large positive number.
Off-On Constraints
Suppose we wish a variable to take on the value a or else to be 0. It is easy to accomplish this by means of the following conditions: X = da; 0 £ d £1 and d an integer.Clearly, that if d satisfies the last two conditions the only possible values it can take on are 0 and 1. So if d = 0, then x = 0, and if d = 1, then X = a, as required.
Off-On Intervals
Suppose we want x either to be 0 or else to be in a fixed interval between a and b. The following inequalities accomplish these requirements: da £ X £ db; 0 < d < 1 and d integer.Clear that if d = 0, then x = 0, and if d = 1, then x satisfies a £X £ b. These are the only possible values for d.
A Case of Discrete Finite Valued Variable
Suppose a variable X takes only one of a finite number of values a1, a2,……, and an. Set:X = a1d1 + a2d2 + … + andn , S di = 1, 0 < di < 1 and di is an integer.
Notice that the conditions on the di's require that exactly one of them should be 1 and the rest 0. And if di = 1, then X = ai.
0 - 1 Integer Linear Programs
Suppose there are n items to be considered for inclusion in a Knapsack. Each item has certain per unit value to the traveler who is packing the knapsack. Each item has a per unit weight that contributes to the overall weight of the knapsack. There is a limitation on the total weight that can be carried. The objective is to maximize the total value of what is packed into the knapsack subject to the total weight limitation. We can use Binary LP to solve this problem.
Using the INT command in LINDO restricts a variable to being either 0 or 1. These variables are often referred to as binary variables. In many applications, binary variables can be very useful in modeling all-or-nothing situations. Examples might include such things as taking on a fixed cost, building a new plant, or buying a minimum level of some resource to receive a quantity discount.Example: Consider the following Knapsack Problem
Maximize 11X1 + 9X2 + 8X3 + 15X4
Subject to: 4X1 + 3X2 + 2X3 + 5X4 £ 8, and any Xi is either 0 or 1.
Since is this very small size problem there are 4 variables each can have either of 2 values, there are 24 = 16 possibilities. Trying all 16 possibilities in order to identify an optimal solution (if it exists) is tedious. Therefore, one must use any one of ILP software packages to solve even this or any larger-scale problem.
Using LINDO, the problem statement is:
Max 11X1 + 9X2 + 8X3 + 15X4 S.T. 4X1 + 3X2 + 2X3 + 5X4 £ 8 END INT X1 INT X2 INT X3 INT X4
Then click on SOLVE. The output shows the optimal solution and the optimal value after 8 Branch-and-Bound Iterations.
Note that instead of repeating INT four times, one can use INT 4. The first four variables appeared in the objective function.
OBJECTIVE FUNCTION VALUE
1) 24.00000
VARIABLE VALUE REDUCED COST
X1 0.000000 -11.000000
X2 1.000000 -9.000000
X3 0.000000 -8.000000
X4 1.000000 -15.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 0.000000
NO. ITERATIONS= 8
Traveling Salesperson Problem
A salesperson has to visit cities 1, 2,..n, and his/her trip begins at, and must end in, Home City. Let Cij be the cost of traveling from city i to city j, which is given. The problem is to determine an optimal order for traveling the cities so that the total cost is minimized.Consider the following Traveling Salesperson Problem:
Min 30x01 + 45x02 +65x03+80x04 + 25x12 + 50x13+ 50x14 + 40x23+ 40x24 + 35x34 +30X10 +45X20+25X21 +65X30 + 50X31 + 40X32 + 80X40+ 50X41+ 40X42 +35X43 Subject to: X01+X02+X03+X04=1 X01+X02+X03+X04=1 x10+x12+x13+x14=1 x20+x21+x23+x24=1 x30+x31+x32+x34=1 x40+x41+x42+x43=1 X10+X20+X30+X40=1 X01+X21+X31+X33=1 x02+X12+X32+X42=1 X03+X13+X23+X43=1 X04+X14+X24+X34=1 All Xij = 0, or 1The solution to this LP problem produces a sub-tours (0, 1, 2). We need to introduce a tour breaker that is
X01 + X10 + X12 + X21+ X02 + X20 £ 2
Adding this new constraint and resolving, we need another tour breaker, which is:
X01 + X10 £ 1,
Adding this, the optimal path is: Home to 1, 1 to 2, 2 to 4, 4 to 3, and 3 to home, with a total length of 195 units.
Capital Budgeting Applications
Suppose a Research & Development company has a sum of money, D dollars, available for investment. The company has determined that there are N projects suitable for investment and at least dj dollars must be invested in project j if it is decided that project j is worthy of investment. The company net profit that can be made by an investment in project j is Pj dollars. The company's dilemma is that it cannot invest in all N projects, becauseS dj > D. Thus, the company must decide in which of the projects it wishes to invest in order to maximize its profit. To solve this problem the counselor formulates the following problem:
Let Xj = 1, if the company invests in project j, and
Xj = 0 if the company does not invest in project j.
The total amount that will be invested is then
S dj Xj, and since this amount cannot exceed D dollars, we have the constraint:
The total profit will be S Pj Xj. Thus the company desires the 0-1 problem:
Maximize Z= S Pj Xj
Hospitals routinely face the problem of scheduling nurses' working hours. A scheduling model is an integer programming problem of minimizing the total number of workers subject to the specified number of nurses during each period of the day.
Subject to: S dj Xj £ D, Xj = 0, OR 1.
Scheduling Problems
To utilize labor as efficiently as possible, it is important to analyze manpower requirements during various times of the day. This is especially true in large service organizations in which customer demand is repetitive, but changes significantly during different hours. For example, many more telephone operators are required during the period noon to 2:00 p.m. then from midnight to 2:00 a.m. Nevertheless, some operators must be on duty during the early morning hours. Since nurses usually work an eight-hour shift, it may be possible to schedule operators' working hours so that a single shift covers two or more "peak periods" of demand. By devising intelligent schedules, the productivity of the operators is increased, resulting in a smaller staff and, thus, a reduction in payroll costs. Other examples in which employee scheduling models have proved useful include bus drivers, air traffic controllers, and nurses. We now give an example problem and develop an integer programming model for scheduling nurses' working hours.
|
Since each nurse works eight hours, he/she can start working at the beginning of any one of the first five shifts: 8:00, 10:00, 12:00, 2:00 or 4:00. In this application, we do not consider any shift starting at 9:00, 11:00, etc. Also, there is no need to have any nurse begin working after 4:00, since his/her shift would then run past midnight when no nurses are needed. Each period is two hours long, so each nurse who reports for work in period t will also work during periods t + 1, t+ 2, and t + 3 --- eight consecutive hours. The question is: "How many nurses should report for work during each time period to meet the resource requirements specified in the above Table." To model this problem, let Xt be a decision variable denoting the number of nurses who will begin work in period t . The total work force, which we wish to minimize, is S Xt. During time period 1, at least 10 agents must be on duty, so we must have X1 ³ 10. Similarly, the requirements in time period 2 can only be met by X1 + X2 ³ 8. In this manner, we write the requirements for the remaining periods. These are:
X1 + X2 + X3 ³ 9,
X1 + X2 + X3 + X4 ³ 11,
X2 + X3 + X4 + X5 ³ 13,
X3 + X4 +X5 ³ 8,
X4 + X5 ³ 5,
X5 ³ 3,
All variable are integer.
Notice that X1 is not included in the constraint for time period 5, since workers beginning in period 1 are no longer on the job by time period 5. Also, observe that it may be necessary to have more than the required number of agents working in some periods. For example we see from the first constraint that the number of nurses beginning work in period 1 must be at least 10. All of these nurses will still be working during time period 2, but only eight agents are required then. Thus even if X2 = 0, there will be two extra nurses on duty during period 2.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Further Readings:
Arsham H., Scheduling Travelling Inspectors - A Modular Decision Support Systems Helps to Plan Laboratory Accreditation Visits, OR Insight, Vol. 10, No. 1, 20-27, 1997.
Marketing Application
Suppose five daily newspapers are published in a certain country, each paper covering some of the nine regions of the country as shown in the following table:
|
Newspaper# |
Region Covered |
Cost of Advertisement |
Benefit of Advertisement |
|
1 |
1,2,3 |
3 |
12 |
The Marketing Manager problem is to find a minimum total cost such that the advertisement covers the whole country. This problem can be formulated as the following zero-one LP problem:
|
Minimize C = 3y1 + 4y2 + 3y3 + 7y4 + 5y5 |
|
|
s.t. y1 |
³ 1 (Region 1) |
|
y1 + y2 |
³ 1 (Region 2) |
|
y1 + y2 |
³ 1 (Region 3) |
|
y3 |
³ 1 (Region 4) |
|
y3 + y4 |
³ 1 (Region 5) |
|
y2 + y3 + y5 |
³ 1 (Region 6) |
|
y4 |
³ 1 (Region 7) |
|
y4 + y5 |
³ 1 (Region 8) |
|
y5 |
³ 1 (Region 9) |
|
yj = 0 OR 1, for all j's |
The optimal solution is to advertise in Newspapers 1, 3, 4, and 5 for a total cost of $18.00. This solution is the lowest cost associated with coverage in each of the nine areas.
The Cutting Stock Problem
Suppose that a lumberyard has a supply of 10-ft boards, which are cut into 3-ft, 4-ft, and 5-ft boards according to customer demand. The 10-ft boards can be cut in six different sensible patterns as shown in the following table:
|
Pattern # |
3-ft boards |
# of 4-ft boards |
5-ft boards |
Waste (ft) |
|
1
|
3
|
0
|
0
|
1
|
|
2
|
2
|
1
|
0
|
0
|
|
3
|
1
|
0
|
1
|
2
|
|
4
|
0
|
1
|
1
|
1
|
|
5
|
0
|
2
|
0
|
2
|
|
6
|
0
|
0
|
2
|
0
|
There are many other possible but not sensible patterns; for instance, one would cut a 10-ft board into a 3-ft and a 4-ft board, leaving 3-ft as waste. This would not make sense, since the 3-ft waste could be used as a 3-ft board, as in pattern #2. If a customer orders 50 3-ft boards, 65 4-ft boards, the question is how many 10-ft boards need to be cut and what cut pattern is to be used?
To model this decision problem, let's denote by yj the number of 10-ft boards cut according to pattern j, j =1, ......, 6. Whereas the total customer demand is 50(3) + 65(4) + 40(5) = 610 ft, the total length of boards actually cut is:
10(y1 + y2 + y3 + y4 + y5 + y6),
and the total waste is, therefore:
10(y1 + y2 + y3 + y4 + y5 + y6) - 610.
This implies that when we:
minimize y1 + y2 + y3 + y4 + y5 + y6,
the total number of 10-ft boards that need to be cut, we also minimize the total waste, and vice versa. The actual number of 3-ft boards obtained in the cutting procedure is:
3y1 + 2y2 + y3,
and therefore:
3y1 + 2y2+ y3 ³ 50
must hold in order to satisfy customer demand for 3-ft boards. Similarly,
y2 + y4 + 2y5 ³ 65
to satisfy the demand for 4-ft boards and
y3 + y4 + 2y6 ³ 40
for 5-ft boards. Since the variables yj must be nonnegative integers,
j = 1, ......, 6, we can summarize this cutting stock formulation as:
|
P: Min z = y1 + y2 + y3 + y4 + y5 + y6 |
(10-ft boards) |
|
s.t. 3 y1 + 2y2 + y3 |
³ 50 (3-ft boards) |
|
y2 + y4 + 2y5 |
³ 65 (4-ft boards) |
|
y3 + y4 + 2y6 |
³ 40 (5-ft boards) |
|
yj are non-negative integer, j = 1, .., 6 |
The above example illustrates a simple instance of the cutting stock or trim loss problem, which is widely applicable whenever trim waste is to be minimized. The example above refers to a one-dimensional situation (board length).
An Engineering Application: Mixing Substances
A chemical company is producing two types of substances ( A and B ) consisting of three types of raw materials (I, II, and III). The requirements on the compositions of the three substances and the profits are as follows:
|
Substance |
Compositions |
Profits |
|
A |
|
10 |
|
B |
|
8 |
Each material's available amount and treatment costs are as follows:
|
Raw
Material
|
Available
Amount (KG)
|
Treatment
Costs/KG
|
|
I
|
400
|
4
|
|
II
|
500
|
5
|
|
III
|
300
|
6
|
The company's problem is to find out how much of each substance to produce at which composition, such that the profit is maximized.
Because we have two substances and three raw materials, we introduce 6 (=2 x 3 ) decision variables xij, i = A, B, and j = I, II, III.
For example, xBIII is the amount of raw material III in substance B. The goal function is thus to maximize the profits minus the treatment costs:
max 10(xAI+xAII+xAIII) + 8(xBI+xBII +xBIII) - 4(xAI +xBI) - 5(xAII +xBII) - 6(xAIII+xBIII)
Rewriting this in terms of the 6 decision variables, the equivalent problem is:
max: 6xAI + 5xAII + 4xAIII + 4xBI + 3xBII + 2xBIII
The material constraints are:
xAI + xBI £ 400
xAII + xBII £
500
xAIII + xBIII £ 300.
The composition constraints are:
0.2(xAI + xAII+ xAIII) ³ xAI
0.1(xAI + xAII + xAIII) ³ xAII
0.2(xAI + xAII + xAIII) £ xAIII
0.4(xBI + xBII + xBIII) ³ xBI
0.5(xBI + xBII + xBIII) ³ xBIIII
From the first inequality in the table above, we can derive the following constraint:
0 £ -0.8xAI + 0.2xAII + 0.2xAIII
Our problem has therefore five constraints from the table above plus three material constraints, and one goal function. In addition, we require that the decision variables, xij, take on only non-negative integer values.
Using your sogtware package, the optimal solution is:
xAI = 85, xAII = 42, xAIII = 299, xBI = 306, xBII = 458, xBIII = 1,
with a total gain of 4,516.
This means that the company should produce 426 kg of substance A and 765 kg of substance B. Of the 400 kg of material I only 391 kg is used, while all of the 500 kg of material II and all of the 300 kg of material III are used.
References & Further Readings:
Ahuja R., T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall, 1993.
Visit also the Web site:
Eiselt H., and C. Sandblom, Integer Programming and Network Models, Springer, 2000.
Floudas C., Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications, Oxford University Press, 1995.
Phillips N., Network Models in Optimization & Their Applications in Practice, Wiley, 1992.
Schrijver, A., Theory of Linear and Integer Programming, Wiley, 1998.
Sierksma G., Linear and Integer Programming: Theory and Practice, Marcel Dekker, 2002.
A Tutorial on Integer Programming
The Copyright Statement: The fair use, according to the 1996 Fair Use Guidelines for Educational Multimedia, of materials presented on this Web site is permitted for non-commercial and classroom purposes only.
This site may be mirrored intact (including these notices), on any server with public access, and linked to other Web pages. All files are available at
http://home.ubalt.edu/ntsbarsh/Business-stat for mirroring.
Kindly e-mail me your comments, suggestions, and concerns. Thank you.
This site was launched on 2/25/1994, and its intellectual materials have been thoroughly revised on a yearly basis. The current version is the 8th Edition. All external links are checked once a month.
EOF: Ó 1994-2012.