This chapter will study the problems of integer and binary programming, and their extensions, establishing the circumstances in which they should be utilized according to characteristics of the problem and their research objectives, with a focus on decision making. We will present modeling of several real problems in binary and integer programming, including knapsack, selection of investment projects, traveling salesman and staff scheduling problems, to name a few, as well as the methods for solving them. The concept of linear relaxation and its importance for solving binary and integer programming problems will also be discussed. All of the problems presented will be solved using Excel Solver.
Binary programming; Integer programming; Knapsack problem; Problem of investment project selection; Traveling salesman problem; Staff scheduling problem; Linear relaxation; Excel Solver
I will always choose a lazy person to do a difficult job. Because a lazy person will find an easy way to do it.
Bill Gates
A problem is classified as being integer programming (IP) when all of the decision variables of the model are discrete, that is, may assume values within a finite set or a numerable quantity of values, derived from counting. When part of the decision variables is discrete and the other is continuous (assume any values in an interval of real numbers), the model is called mixed integer programming (MIP).
As for cases in which all of the decision variables are binary or dummy, that is, may only assume values of 1 (when the characteristic of interest is present in the variable) or 0 (opposite case), we have a model of binary programming (BP). When part of the decision variables is binary and the other is continuous, the model is called mixed binary programming (MBP).
When one has discrete and binary decision variables in the same model, it becomes in a problem of binary integer programming (BIP).
It is important to point out that many authors do not differentiate the discrete variables from the binary one simply call the model one of integer programming in cases in which the variables are discrete and/or binary, and mixed integer programming when the variables are discrete and/or binary and continuous.
In this chapter, we will study only the linear models.
Box 19.1 summarizes the principal characteristics of the integer (linear) programming models and their extensions.
As examples of binary programming we may list: job assignment problem and shortest path problem (seen in the previous chapter on network programming), knapsack problem, capital budgeting problem with binary variables, production scheduling program, traveling salesman problem, vehicle routing program, among others. For its part, the staff scheduling problem is an example of integer programming, while the facility location problem is classified as a problem of mixed binary programming, since it has as decision variables the possible facilities (variable binary) and the quantities delivered (variable continuous).
As exact solution methods for binary and integer programming problems, one may cite the branch-and-bound algorithm, the cutting plane algorithms, branch-and-cut algorithms, and others. However, many problems in binary and integer programming are NP-complete, that is, they may not be solved in polynomial time because of the high computational complexity. As an alternative to exact methods, approximate algorithms such as heuristic and metaheuristic type have been proposed for resolving this type of problem.
The branch-and-bound algorithm is a divide and conquer strategy, in which a main problem is divided into subproblems. The problem is solved for those smaller levels. The method discards subproblems through implicit enumeration, meaning subproblems that do not contain the optimal solution. The solutions for subproblems are combined until the optimal FBS is obtained. There is also the branch-and-cut algorithm, an adaptation of the branch-and-bound algorithm in which cutting plane algorithms are applied.
The term heuristic may be defined as a search procedure guided by intuition, rules, and ideas that seeks to find a good solution. As for the term metaheuristic is a combination of search procedures with higher level strategies, including intensification and diversification, seeking to escape local optimums and find solutions much closer to the global optimum; but without a guarantee of optimality. As examples of metaheuristics that are being applied to solve integer programming problems we may mention tabu search, simulated annealing, greedy randomized adaptive search procedures (GRASP), genetic algorithms, ant colony, and particle swarm, among others.
In this chapter, we will present the mathematical formulation for the knapsack, capital budgeting with binary variables, traveling salesman, facility location and staff scheduling problems, as well as their solution using Excel Solver.
Formulation of a general model for integer and/or binary programming may be represented mathematically as:
maxouminz=f(x1,x2,…,xn)=c1x1+c2x2+…+cnxnsubject to:a11x1+a12x2+…+a1nxn{≤,=,≥}b1a21x1+a22x2+…+a2nxn{≤,=,≥}b2⋮⋮⋮⋮am1x1+am2x2+…+amnxn{≤,=,≥}bmx1,x2,…,xn≥0x1,x2,…,xninteger and/or binary
One approach to find the optimal solution for Expression (19.1) is to relax or eliminate the integrality constraints of the variables (and/or the constraint that the variables are binary), leading to a linear programming problem called Linear relaxation of the integer programming problem (and/or Binary programming).
In some problems, even after relaxing the integrality constraints of the original IP problem (and/or relaxing the constraint that the variables be binary in the original BP problem) and resolution of the same by the Simplex method, for example, the solution obtained may also satisfy the integrality conditions (and/or that the variables be binary) and, therefore, represent the optimal solution of the original problem. Among the examples presented in this book that apply to in this case, we can cite Examples 16.3 and 16.10 from Chapter 16 (Venix and Fenix & Furniture, respectively) and Examples 18.10 and 18.11 from Chapter 18 (job assignment problem and shortest path problem, respectively). Some characteristics of the original problem guarantee that the optimal solution may be obtained directly by relaxing the integrality conditions (and/or that the variables be binary), such as, for example, the supply capacity and demand for nodes with integer values (for the network programming problem), or the availability of resources with integer values (for the production mix or production and inventory problems), besides the resolution of the problem by the Simplex method.
However, in many cases, it is unfortunately not possible to directly obtain the optimal solution of the original IP problem (or BP or BIP) by relaxing the integrality conditions (and/or relaxing the constraint that the variables be binary). One alternative for finding an integer solution in those cases is by rounding the solution obtained after linear relaxation of the IP problem. However, rounding may lead to a new unfeasible solution. Another negative point is that there is no guarantee that the new rounded solution will be the optimal solution of the original integer programming problem. To achieve such a guarantee, other exact methods of integer programming may be applied, such as the branch-and-bound algorithm, cutting plane algorithms, branch-and-cut algorithm, and Lagrangian relaxation, as well as others.
The knapsack problem seeks to determine, among n possible objects, which of them should be carried in the knapsack, taking into account their utility and their weight. Each object j has a utility value cj and a weight pj. The maximum weight that may be carried in the knapsack is Cmax. The objective is thus to determine which objects should be carried in the knapsack, so as to maximize its total utility, subject to the constraint that the capacity of the knapsack may not be exceeded.
The model parameters, the decision variables, and the overall mathematical formulation of the knapsack problem are specified as follows.
Parameters of the model:
cj = utility of the object j
pj = weight of the object j
Cmax = capacity of the knapsack
Decision variables:
xj={1if the objectjis in the knapsack0otherwise
Mathematical formulation:
Fobj=maxz=n∑j=1cjxjs.t.n∑j=1pjxj≤Cmaxxj∈{0,1}
that corresponds to a binary programming problem.
The knapsack problem may also be formulated as a problem of integer programming if xj corresponds to the number of objects of type j placed in the knapsack (one may take more than one object of same type).
Example 19.2 referring to the knapsack problem will be solved in this section using Excel Solver. The representation of the problem in an Excel spreadsheet is illustrated in Fig. 19.2 (see file Example19.2_Knapsack.xls).
The formulas utilized in Fig. 19.2 are specified in Box 19.2.
The names attributed to the cells and intervals of cells of Fig. 19.2 that will be referred to in the Solver are presented in Box 19.3.
The representation of the knapsack problem (Example 19.2) in the Solver Parameters dialog box is illustrated in Fig. 19.3. Since we are faced with a binary programming problem, a new constraint was included through an Add button (see Fig. 19.4). On the left side are referenced the variable cells (called Objects). In the middle cell, instead of selecting the equal to or unequal to sign, as done with the other constraints, one selects the bin option. Note that on the right side the binary name appears automatically. The bin option is automatically substituted by the equal sign after the constraint is added. Additionally, in the Options dialog box, it is necessary to disable the Ignore Integer Constraints check box (otherwise, the binary constraint is ignored) and specify the Integer Optimality % (the value 0% ensures that a proven optimal solution is found, but may take considerable extra time), as shown in Figure 19.4.
Returning to Fig. 19.3, as the constraint that the decision variables may only assume the values 0 or 1 has already been added, it is not necessary to select the Make Unconstrained Variables Non-Negative check box. In the Select a Solving Method box, we selected the Simplex LP engine.
When the Simplex LP or GRG Nonlinear Solving methods are used, Solver uses a Branch & Bound method for the integer constraints. The Evolutionary Solving method uses its own methods for such problems (https://www.solver.com/excel-solver-integer-programming).
Fig. 19.5 presents the optimal solution of the knapsack problem (Example 19.2).
The optimal solution is, therefore, x1 = 1, x2 = 1, x3 = 0, x4 = 1, x5 = 1, x6 = 1, x7 = 1, x8 = 1, and x9 = 0 (one selects all of the objects, except for the tennis shoes and camera) with z = 41.
As seen in Chapter 16 (Section 16.6.4), the objective of the capital budgeting problem is to select from a set of alternatives, the investment projects that are financially viable, respecting the budget constraints of the investment company. The capital budgeting problem uses the concept of NPV (Net Present Value) that seeks to define which investment is the most attractive. Considering different investment projects, the most attractive one is the one presenting the highest Net Present Value.
Unlike Chapter 16, in which a model of linear programming was used to solve the capital budgeting problem, in this chapter we will use a binary programming model to determine, among a set of alternatives for investment projects, if the project j will be approved (xj = 1) or rejected (xj = 0).
Example 19.3 of the Investilila company will be solved in this section using Excel Solver. The representation of the problem in an Excel spreadsheet is illustrated in Fig. 19.6 (see file Example19.3_Investilila.xls).
The formulas utilized in Fig. 19.6 are specified in Box 19.4.
The names attributed to the cells and intervals of cells of Fig. 19.6 are presented in Box 19.5.
The representation of the problem of the Investilila company in the Solver Parameters dialog box is illustrated in Fig. 19.7. Analogous to the knapsack problem, since we are faced with a binary programming problem, the constraint that the decision variables be binary was included (see Fig. 19.8). To do that, on the left side of the Add constraint dialog box, one references the variable cells (Approved_rejected). In the middle cell, one selects the option bin, which automatically generates the binary name on the right side. Additionally, in the Options dialog box, it is necessary to disable the Ignore Integer Constraints check box and specify the value 0 in the Integer Optimality (%) box, as shown in Fig. 19.8.
Note in Fig. 19.7 that the Simplex LP option was selected as the solving method. As the binary constraint has already been added, it is not necessary to select the Make Unconstrained Variables Non-Negative check box. Fig. 19.9 presents the optimal solution of the problem of the Investilila company (Example 19.3).
The optimal FBS is, therefore, x1 = 1, x2 = 0, x3 = 1, x4 = 1, and x5 = 0 (invest in projects 1, 3 and 4) with z = 52 (total NPV in the amount of $ 52 million).
As is the case with the shortest path problem, the traveling salesman problem also corresponds to a binary programming problem that may also be modeled like a problem of network programming.
The Traveling Salesman Problem (TSP) is an optimization problem associated with determining what are called Hamiltonian paths. Its origin comes from William Rowan Hamilton, who proposed a game where the challenge consists of finding a route using the nodes of a dodecahedron (solid regular, with 20 nodes, 30 arcs, and 12 faces) so that the path begins and ends at the same node without ever repeating a visit. Consider G = (N, A) a nonoriented graph n which N is the set of n cities and A is the set of arcs between as cities. The objective of the TSP is thus to find in graph G = (N, A), the Hamiltonian path with lowest cost so that all of the nodes are visited a single time.
In other words, the problem consists of determining a single route with the lowest possible cost that allows the traveling salesman (or vehicle) to visit all of the nodes (cities or clients) in a network a single time. The graph of the problem and one of the possible solutions to the game are presented in Fig. 19.10.
There are several formulations for the traveling salesman problem. Dantzig et al. (1954) model the TSP specified as follows.
Parameters of the model:
cij = cost or distance from city i to city j, i = 1, …, n and j = 1, …, n.
Decision variables:
xij={1if the traveling salesman goes directly from cityito cityj,i≠j0otherwise
Mathematical formulation:
(Fobj)=minz=n∑i=1n∑j=1cijxij
s.t.
n∑i=1xij=1∀j∈N(1)n∑j=1xij=1∀i∈N(2)∑i,j∈Sxij≤|S|−1∀S⊂N(3)xij∈{0,1}∀i,j∈N(4)
that corresponds to a binary programming problem.
The objective function seeks to minimize the cost or the total distance for the route. Constraints (1) and (2) guarantee that each node is visited a single time. Consider S is a subgraph of G in which | S | represents the number of nodes in that subgraph. Thus, constraint (3) prevents formation of subroutes. Finally, constraint (4) requires that the decision variables be binary.
Example 19.4 referring to the traveling salesman problem will be solved in this section using Excel Solver. The representation of the problem in an Excel spreadsheet is illustrated in Fig. 19.13 (see file Example19.4_TravelingSalesman.xls).
With regard to the formulas utilized in Fig. 19.13, all of the cells of lines 11 to 49, between columns C and V, correspond to the cell of row 5 of the same column. For example, G11 = G5, C12 = C5, D13 = D5, and so forth, up to T49 = T5 or V32 = V5. For their part, the cells of column W of a given row correspond to the sum of cells of column C with those of column V of the same row. For example, W11 = SUM(C11:V11), and so forth, up to W49 = SUM(C49:V49). We furthermore have the formula of the destination cell, which is X5 = SUMPRODUCT(C5:V5, C7:V7).
The names attributed to the cells and intervals of cells of Fig. 19.13 that will be referred to in the Excel Solver are presented in Box 19.6.
The representation of the traveling salesman problem in the Solver Parameters dialog box is illustrated in Fig. 19.14. As we are faced with a binary programming problem, the constraint that the decision variable Routes are binary was included. Similar to previous problems, clicking on the Options button, do not forget to disable the Ignore Integer Constraints check box and to specify the value 0 in the Integer Optimality (%) box.
Since the constraint that the decision variables may only assume values 0 or 1 has already been included, it is not necessary to select the Make Unconstrained Variables Non-Negative check box. In the Select a Solving Method box, the Simplex LP method was selected. Fig. 19.15 presents the optimal solution of the traveling salesman problem (Example 19.4).
The optimal FBS is, therefore, x14 = 1, x21 = 1, x32 = 1, x45 = 1, and x53 = 1 that corresponds to the route 1 → 4 → 5 → 3 → 2 → 1 (or x12 = 1, x23 = 1, x35 = 1, x41 = 1, x54 = 1) that corresponds to the opposite direction) with z = 217, 21. This solution may also be represented graphically, as shown in Fig. 19.16.
Facility location models have been widely studied during recent decades. The term facility includes factories, distribution centers, ports, airports, or terminals. The objective of the facility location problem is to determine the number of facilities and select the optimal locations among a set of candidate locations, as well as to achieve better distribution of the products from the facilities to the final clients so that their demands are met at the lowest possible cost. The simplest problem considers only two links in the supply chain (single-stage location problem) but may be generalized into three links (two-stage location problem) as happens in the transshipment problem. The two-stage facility location problem is thus an extension of the transshipment problem, in which the transshipment points must be located (they become decision variables). Thus, the facility location problem may also be modeled like a network programming problem. We will present the simplest single-stage model here.
The model parameters, the decision variables, and the overall mathematical formulation of the facility location problem are specified as follows, based on Chopra and Meindl (2015).
Indexes:
i = 1, …, m that represent the facilities
j = 1, …, n that represent the consumers
Parameters of the model:
cij = transportation cost from facility i to the consumer j
fi = fixed cost of keeping facility i open
Cmax, i = maximum capacity from facility i
Dj = demand from consumer j
Decision variables:
xij = quantity transported from facility i to the consumer j
yi={1if facilityiis open0otherwise
Mathematical formulation:
Fobj=minz=m∑i=1fiyi+m∑i=1n∑j=1cijxijs.t.n∑j=1xij≤Cmax,i⋅yi,i=1,…,m(1)m∑i=1xij=Dj,j=1,…,n(2)xij≥0,i=1,…,m,j=1,…,n(3)yi∈{0,1},i=1,…,m(4)
that corresponds to a problem of mixed binary programming.
The objective function of the facility location model seeks to minimize the sum of the fixed costs for facilities maintenance and the transportation costs from the facilities to the final customers. Constraint (1) guarantees that the maximum capacity of each facility i will not be exceeded. Obviously, the capacity from facility i will only be considered if that facility is open. The second constraint guarantees that the demand of each consumer j will be met. Finally, it is affirmed that the decision variables xij are positive and that the variables yi are binary.
Example 19.5 regarding the facility location problem will be solved in this section using Excel Solver. The representation of the problem in an Excel spreadsheet is illustrated in Fig. 19.18 (see file Example19.5_Location.xls).
The formulas utilized in Fig. 19.18 are specified in Box 19.7.
The names attributed to the cells and intervals of cells in Fig. 19.18 that will be referred to in the Excel Solver are presented in Box 19.8.
The representation of the facility location problem in the Solver Parameters dialog box is illustrated in Fig. 19.19. As we are faced with a problem of mixed binary programming, the constraint that the Location decision variables are binary was included. To complete the operation, click on the Options button, disable the Ignore Integer Constraints check box and specify the value 0 in the Integer Optimality (%) box. Otherwise, the binary constraint is ignored.
Instead of adding the Quantities_transported>=0 constraint, we could select the Make Unconstrained Variables Non-?Negative check box. Note that the Simplex LP method was selected. Fig. 19.20 presents the optimal solution of the facility location problem (Example 19.5).
The optimal FBS is, therefore, x12 = 18,000, x15 = 17,000, x21 = 16,000, x23 = 7,000, x33 = 5,000, x34 = 17,000, x35 = 3,000, y1 = 1, y2 = 1, and y3 = 1 with z = 430,580.00. For this problem, Solver can find more than one optimal solution.
Several staff scheduling problems have arisen, such as staffing for nurses, staffing at post offices, banks, telephone call centers, employees scheduling for transportation companies, to name a few. The problem consists of allocating a set of employees at different work times, so that the service centers may meet their demands, respecting the constraints of the system. Since the decision variables must assume integer values (number of employees per shift), the staff scheduling problem corresponds to a problem of integer programming.
Example 19.6 regarding the PRINCE bank problem, will be solved in this section using Excel Solver. Fig. 19.21 illustrates the representation of the model in an Excel spreadsheet (see file Example19.6_Banksum.xls).
Box 19.9 presents the formulas utilized in Fig. 19.21.
The names attributed to the cells and intervals of cells of Fig. 19.21 that will be referred to in Solver are specified in Box 19.10.
Fig. 19.22 presents a representation of the PRINCE bank problem in the Solver Parameters dialog box. As we are faced with a problem of integer programming, the new constraint was included using the Add button (see Fig. 19.23). On the left side are listed the variable cells (called Quantity_employees). In the middle cell, instead of selecting the equal to or unequal to sign, as done with the other constraints, one selects the int option. Note that on the right side the number name appears automatically. The int option is automatically substituted by the equal sign after the problem is solved. Similar to previous problems, clicking on the Options button, do not forget to disable the Ignore Integer Constraints check box and to specify the value 0 in the Integer Optimality (%) box, as shown in Fig. 19.23.
Once again, the Make Unconstrained Variables Non-Negative check box and the Simplex LP method were selected in Fig. 19.22. Fig. 19.24 presents the optimal solution of the PRINCE bank problem.
The optimal solution is, therefore, x1 = 22, x2 = 18, x3 = 14, x4 = 30, and x5 = 18 with z = 11,430.
Section 19.1 (ex. 1). Classify the following problems as: integer programming (IP), mixed integer programming (MIP), binary programming (BP), mixed binary programming (MBP), or binary integer programming (BIP):
Section 19.2 (ex. 1). Look again at the exercises from the previous section. Solve each relaxed problem by the Simplex method and verify if the solution found corresponds to the optimal solution of the original problem.
Section 19.2 (ex. 2). Consider the following integer programming problem:
maxz=2x1+3x2s.t.2x1+5x2≤205x1+3x2≤30x1,x2≥0x1,x2areintegers
You are to:
Section 19.2 (ex. 3). Same for the following integer programming problem:
maxz=x1+2x2s.t.x1+3x2≤63x1+x2≤9x1,x2≥0x1,x2areintegers
Section 19.2 (ex. 4). Same for the following integer programming problem:
maxz=3x1+2x2s.t.4x1+2x2≤16x2≤2x1,x2≥0x1,x2areintegers
Section 19.3 (ex.1). The Translibert bus company operates on the Sao Paulo - Ubatuba stretch and is analyzing whether to take on additional passengers during the route, considering the last bus that has left the terminal. There is a total of 8 passengers waiting, and each will travel a different route, paying different fares, as shown in Table 19.1. The weights of the passengers must also be considered, given that the maximum weight that can be added is 280 kg, so as not to exceed the maximum capacity of the bus in circulation. Determine the passengers that should be selected, in order to maximize the profit for the company while respecting the capacity constraints.
Table 19.1
Passenger | Ticket Price | Weight |
---|---|---|
1 | 48.00 | 80 |
2 | 40.00 | 70 |
3 | 52.00 | 84 |
4 | 45.00 | 72 |
5 | 55.00 | 90 |
6 | 40.00 | 65 |
7 | 30.00 | 50 |
8 | 35.00 | 55 |
Section 19.4 (ex.1). A company is considering 6 projects to invest in. The estimated profit (NPV) and the capital required for each project are illustrated in Table 19.2. Projects 5 and 6 are mutually exclusive (one project may only be selected if the other is not chosen), while project 3 is dependent on project 2 (acceptance of project 3 depends on acceptance of project 2). The total available in funds for investing in those projects is US$ 20 million. Formulate the problem for selecting investment projects and determine the optimal solution using Excel Solver.
Table 19.2
Project | NPV | Capital Necessary |
---|---|---|
1. Invest in IT | 7 | 4 |
2. Open the new factory | 12 | 7 |
3. Acquire a new supplier | 8 | 5 |
4. Develop a new product | 10 | 6 |
5. Invest in R&D | 7 | 4 |
6. Invest in publicity and advertising | 6 | 3 |
IT, Information Technology; R&D, Research and Development.
Section 19.5 (ex.1). Formulate the vehicle routing problem that is specified here and is an extension of the traveling salesman problem. The problem consists of determining multiple routes (instead of a single route as happens with the traveling salesman problem), at the lowest possible cost, so that each vehicle visits at least one node of the network, and each node is visited only once. The total demand of each node should be met. The problem is based on a single deposit and the vehicle must leave and return to the same base. The problem also considers vehicle capacity constraints.
Section 19.6 (ex.1). A company in the automobile sector is planning to open new distribution centers and is considering five possibilities: Belem, Palmas, Sao Luis, Teresina, and Fortaleza. From the new distribution centers (DCs), the products will be delivered to five final customers: Belo Horizonte, Vitoria, Rio de Janeiro, Sao Paulo, and Campo Grande. However, each final consumer may only be served by a single DC. Each DC has a fixed maintenance cost and a maximum operating capacity, as shown in Table 19.3. The transportation costs per unit transported from each DC to each final consumer, besides the demand from consumers, are also detailed in the same table. The company wishes to determine which distribution center(s) to open, so as to minimize the sum of the fixed costs for installation and transportation, ensuring that the demand of the final customers will be met. Model the facility location problem and determine the optimal solution using Excel Solver.
Table 19.3
Unit Transportation Costs | |||||||
---|---|---|---|---|---|---|---|
Belo Horizonte | Vitoria | Rio de Janeiro | Sao Paulo | Campo Grande | Fixed cost | Capacity | |
Belem | 0.87 | 0.90 | 0.92 | 0.94 | 0.90 | 140,000 | 25,000 |
Palmas | 0.82 | 0.88 | 0.90 | 0.92 | 0.92 | 135,000 | 35,000 |
Sao Luis | 0.93 | 0.95 | 0.99 | 1.02 | 0.97 | 125,000 | 25,000 |
Teresina | 0.95 | 1.06 | 0.98 | 1.02 | 0.95 | 120,000 | 20,000 |
Fortaleza | 1.02 | 0.89 | 0.92 | 0.98 | 1.04 | 125,000 | 30,000 |
Demand | 12,000 | 15,000 | 18,000 | 20,000 | 20,000 |
Section 19.6 (ex.2) (Source: Adapted from Brito Júnior, 2004). A supply company with head offices in the United States and Europe supplies a production line located in Harbin (northern China). The various materials may be sent from the suppliers directly to the production line in Harbin or undergo a consolidation stage (transshipment) in one of the possible consolidation points: in Brazil (Sao Jose dos Campos), East and West Coasts of the United States (Miami and Los Angeles), or in France (Paris). In this problem, each client may be served by more than one facility. The consolidation points have maximum capacity constraints.
The objective is to determine optimal consolidation sites among the possible local candidates, besides the quantity of each product that will be transported directly from the suppliers to the production line in Harbin, and the quantity of each product that undergoes the transshipment stage in one of the chosen sites, in order to minimize total logistics costs in the network analyzed, subject to the following conditions:
Model the location and transshipment problem for the company analyzed.
Section 19.7 (ex.1). The City Government of Ukiah-CA is introducing new bus routes, in order to meet the transportation needs of residents in a given area of the city. They are seeking to determine the number of buses that will be assigned for each shift, in order to meet the level of service for clients on a given day, with the lowest possible cost. Each begins its operation on one of the shifts specified in Table 19.4, operating for a consecutive period of 8 hours. The number of buses necessarily varies according to the time of day, as shown in Table 19.5. Formulate the integer programming problem that seeks to minimize the number of buses in operation in each shift and determine the optimal solution using Excel Solver.
Table 19.4
Shift | Start of Operation |
---|---|
1 | 6:01 |
2 | 8:01 |
3 | 10:01 |
4 | 12:01 |
5 | 14:01 |
6 | 16:01 |
7 | 18:01 |
8 | 20:01 |
9 | 22:01 |
Table 19.5
Period | Minimum Number of Buses in Operation |
---|---|
6:01–8:00 | 20 |
8:01–10:00 | 24 |
10:01–12:00 | 18 |
12:01–14:00 | 15 |
14:01–16:00 | 16 |
16:01–18:00 | 27 |
18:01–20:00 | 18 |
20:01–22:00 | 12 |
22:01–24:00 | 10 |
00:01–02:00 | 4 |
02:01–04:00 | 3 |
04:01–06:00 | 8 |
Section 19.7 (ex.2). A post office branch needs to hire employees so as to meet client demand for each day of the week. The minimum number of employees, for each day of the week, is detailed in Table 19.6. According to labor laws, each worker has the right to 5 consecutive work days and 2 days off. Formulate the integer programming problem that seeks to minimize the number of employees to be hired, respecting the constraints of the system. Also determine the optimal solution using Excel Solver.