19.1 Introduction

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.

19.2 Mathematical Formulation of a General Model for Integer Programming and/or Binary and Linear Relaxation

Formulation of a general model for integer and/or binary programming may be represented mathematically as:

$\begin{array}{l}max\mathrm{ou}minz=f\left(x_1,x_2,\dots ,x_n\right)=c_1{x}_1+c_2{x}_2+\dots +c_n{x}_n\\ \text{subject to}:\\ a_{11}{x}_1+a_{12}{x}_2+\dots +a_{1n}{x}_n\left\{\le ,=,\ge \right\}{b}_1\\ a_{21}{x}_1+a_{22}{x}_2+\dots +a_{2n}{x}_n\left\{\le ,=,\ge \right\}{b}_2\\ ⋮⋮⋮⋮\\ a_{m1}{x}_1+a_{m2}{x}_2+\dots +a_{\mathit{mn}}{x}_n\left\{\le ,=,\ge \right\}{b}_m\\ x_1,x_2,\dots ,x_n\ge 0\\ x_1,x_2,\dots ,x_n\text{integer and}/\text{or binary}\end{array}$

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.

Example 19.1

Consider the following integer programming problem:

$\begin{array}{l}max4x_1+3x_2\\ \mathrm{s}.\mathrm{t}.\\ 5x_1+3x_2\le 22\\ 2x_1+2x_2\le 11\\ x_1,x_2\ge 0\\ x_1,x_2\mathrm{are}\text{integers}\end{array}$

  (19.2)

Determine the feasible region of the original problem and of the relaxed problem and compare the solutions.

Solution

The relaxed problem of Expression (19.2) is:

$\begin{array}{l}max4x_1+3x_2\\ \mathrm{s}.\mathrm{t}.\\ 5x_1+3x_2\le 22\\ 2x_1+2x_2\le 11\\ x_1,x_2\ge 0\end{array}$

  (19.3)

The graphical solution of problems of Expressions (19.2) and (19.3) is represented in Fig. 19.1.

The shaded area represents the feasible region of the relaxed problem, whose optimal solution is represented by the point (x₁, x₂) = (2.75, 2.75). The other points of the shaded area represent the viable integer solutions of the problem represented by Expression (19.2) that has the point (x₁, x₂) = (3, 2) as the optimal solution. Note that the viable integer solutions represented by Expression (19.2) consist of only 19 discrete points, including (0, 0), and all belong to the feasible region of the relaxed problem. We can affirm that the feasible region of the relaxed problem will always encompass all of the viable integer solutions of the original IP problem and, consequently, its respective optimal solution.

We have seen in Chapter 17 that the simplex method for solving LP problems starts with an initial feasible basic solution and at each iteration seeks a new feasible basic solution with the best value in the objective function until the optimum value is reached. All of the feasible basic solutions correspond to an extreme point in the viable region. Therefore, the simplex method examines only a small share of all of the viable solutions for the problem until it reaches the optimal solution, which means that large-scale problems may be solved in a short computing time. Unfortunately, the same thing does not happen in relation to the IP problems; no algorithm is known for solving IP problems that starts from an initial FBS and finds a better FBS at each iteration. In summary, although the feasible region of an IP problem is a subset of the feasible region of the original relaxed problem, an IP problem is much more difficult to solve than a LP problem (Winston, 2004).

19.3 The Knapsack Problem

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 c_j and a weight p_j. The maximum weight that may be carried in the knapsack is C_max. 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.

19.3.2 Solution of the Knapsack Problem Using Excel Solver

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.

Box 19.2

Formulas Utilized in Fig. 19.2

Cell	Formula
F5	= D5⁎E5
F6	= D6⁎E6
F7	= D7⁎E7
F8	= D8⁎E8
F9	= D9⁎E9
F10	= D10⁎E10
F11	= D11⁎E11
F12	= D12⁎E12
F13	= D13⁎E13
F14	= SUM(F5:F13)
H5	= SUMPRODUCT(C5:C13,E5:E13)

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.

Box 19.3

Names Attributed to the Cells of Fig. 19.2

Name	Cells
Utility	C5:C13
Weight	D5:D13
Objects	E5:E13
Total_weight	F14
Knapsack_capacity	F16
Total_utility	H5

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, x₁ = 1, x₂ = 1, x₃ = 0, x₄ = 1, x₅ = 1, x₆ = 1, x₇ = 1, x₈ = 1, and x₉ = 0 (one selects all of the objects, except for the tennis shoes and camera) with z = 41.

19.4 The Capital Budgeting Problem as a Model of Binary Programming

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 (x_j = 1) or rejected (x_j = 0).

19.4.1 Solution of the Capital Budgeting Problem as a Model of Binary Programming Using Excel Solver

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.

Box 19.4

Formulas Utilized in Fig. 19.6

Cell	Formula
G10	= SUMPRODUCT(B10:F10,B16:F16)
G11	= SUMPRODUCT(B11:F11,B16:F16)
G12	= SUMPRODUCT(B12:F12,B16:F16)
G16	= SUMPRODUCT(B5:F5,B16:F16)

The names attributed to the cells and intervals of cells of Fig. 19.6 are presented in Box 19.5.

Box 19.5

Names Attributed to the Cells of Fig. 19.6

Name	Cells
Unit_NPV	B5:F5
Unit_investment	B10:F12
Total_investment	G10:G12
Funds_available	I10:I12
Approved_rejected	B16:F16
Total_NPV	G16

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, x₁ = 1, x₂ = 0, x₃ = 1, x₄ = 1, and x₅ = 0 (invest in projects 1, 3 and 4) with z = 52 (total NPV in the amount of $ 52 million).

19.5 The Traveling Salesman Problem

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.

19.5.1 Modeling of the Traveling Salesman Problem

There are several formulations for the traveling salesman problem. Dantzig et al. (1954) model the TSP specified as follows.

Parameters of the model:

c_ij = cost or distance from city i to city j, i = 1, …, n and j = 1, …, n.

Decision variables:

$x_{\mathit{ij}}=\left\{\begin{array}{l}1\text{if the traveling salesman goes directly from city}i\text{to city}j,i\ne j\\ 0\text{otherwise}\end{array}\right.$

Mathematical formulation:

$\left(F_{\mathrm{obj}}\right)=minz=\sum _{i=1}^n\sum _{j=1}^n{c}_{\mathit{ij}}{x}_{\mathit{ij}}$

s.t.

$\begin{array}{lll}\sum _{i=1}^n{x}_{\mathit{ij}}=1& {\forall }_j\in N& \left(1\right)\\ \sum _{j=1}^n{x}_{\mathit{ij}}=1& {\forall }_i\in N& \left(2\right)\\ \sum _{i,j\in S}{x}_{\mathit{ij}}\le \left|S\right|-1& \forall S\subset N& \left(3\right)\\ x_{\mathit{ij}}\in \left\{0,\left.1\right\}\right.& {\forall }_{i,j}\in N& \left(4\right)\end{array}$

  (19.5)

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

Consider a symmetrical traveling salesman problem with 5 cities whose coordinates (x, y) are specified in Table 19.E.3. Model the traveling salesman problem.

Table 19.E.3

Coordinates (x, y) of the 5 Cities

City	x	y
1	10	30
2	20	50
3	50	90
4	70	30
5	90	50

Solution

The 5 cities may be represented graphically as shown in Fig. 19.11.

An illustration of subroutes is represented in Fig. 19.12. On the left side, we have a subroute S = {1, 2, 4} with three nodes and on the right side a subroute S = {2, 3, 4, 5} with four nodes.

First, we must calculate the Euclidean distances between each pair of cities i and j through expression $d_{\mathit{ij}}=\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}$, whose results are presented in Table 19.E.4.

Table 19.E.4

Euclidean Distances Between Each Pair of Cities i and j

	1	2	3	4	5
1	x	22.36	72.11	60.00	82.46
2	22.36	x	50.00	53.85	70.00
3	72.11	50.00	x	63.25	56.57
4	60.00	53.85	63.25	x	28.28
5	82.46	70.00	56.57	28.28	x

The decision variables of the model are:

$x_{\mathit{ij}}=\left\{\begin{array}{l}1\text{if the traveling salesman goes directly from city}i\text{to city}j,i\ne j\\ 0\text{otherwise}\end{array}\right.,i=1,\dots ,5\text{and}j=1,\dots ,5$

The objective function seeks to minimize the total distance for the route:

$\begin{array}{l}{F}_{obj}=minz=22.36x_{12}+72.11x_{13}+60.00x_{14}+82.46x_{15}+\\ 22.36x_{21}++50.00x_{23}+53.85x_{24}+70.00x_{25}+\\ 72.11x_{31}+50.00x_{32}++63.25x_{34}+56.57x_{35}+\\ 60.00x_{41}+53.85x_{42}+63.25x_{43}++28.28x_{45}+\\ 82.46x_{51}+70.00x_{52}+56.57x_{53}+28.28x_{54}\end{array}$

The constraints of the model are specified as follows:

1. 1. Each node j must be visited only once:

$x_{21}+x_{31}+x_{41}+x_{51}=1\left(j=1\right)$

$x_{12}+x_{32}+x_{42}+x_{52}=1\left(j=2\right)$

$x_{13}+x_{23}+x_{43}+x_{53}=1\left(j=3\right)$

$x_{14}+x_{24}+x_{34}+x_{54}=1\left(j=4\right)$

$x_{15}+x_{25}+x_{35}+x_{45}=1\left(j=5\right)$

1. 2. Each node i must be visited only once:

$x_{12}+x_{13}+x_{14}+x_{15}=1\left(i=1\right)$

$x_{21}+x_{23}+x_{24}+x_{25}=1\left(i=2\right)$

$x_{31}+x_{32}+x_{34}+x_{35}=1\left(i=3\right)$

$x_{41}+x_{42}+x_{43}+x_{45}=1\left(i=4\right)$

$x_{51}+x_{52}+x_{53}+x_{54}=1\left(i=5\right)$

1. 3. Constraint (3) prevents formation of subroutes with two nodes (| S | = 2):

$x_{12}+x_{21}\le 1$

$x_{13}+x_{31}\le 1$

$x_{14}+x_{41}\le 1$

$x_{15}+x_{51}\le 1$

$x_{23}+x_{32}\le 1$

$x_{24}+x_{42}\le 1$

$x_{25}+x_{52}\le 1$

$x_{34}+x_{43}\le 1$

$x_{35}+x_{53}\le 1$

$x_{45}+x_{54}\le 1$

Note that all possible combinations of subroutes with 2 nodes are considered.

1. 4. Constraint (4) prevents formation of subroutes with three nodes (| S | = 3):

$x_{12}+x_{23}+x_{31}\le 2$

$x_{12}+x_{24}+x_{41}\le 2$

$x_{12}+x_{25}+x_{51}\le 2$

$x_{13}+x_{34}+x_{41}\le 2$

$x_{13}+x_{35}+x_{51}\le 2$

$x_{14}+x_{45}+x_{51}\le 2$

$x_{23}+x_{34}+x_{42}\le 2$

$x_{23}+x_{35}+x_{52}\le 2$

$x_{24}+x_{45}+x_{52}\le 2$

$x_{34}+x_{45}+x_{53}\le 2$

1. 5. There will be no formation of subroutes with four nodes (| S | = 4):

$x_{12}+x_{23}+x_{34}+x_{41}\le 3$

$x_{12}+x_{23}+x_{35}+x_{51}\le 3$

$x_{12}+x_{24}+x_{45}+x_{51}\le 3$

$x_{13}+x_{34}+x_{45}+x_{51}\le 3$

$x_{23}+x_{34}+x_{45}+x_{52}\le 3$

1. 6. Non-negativity constraints:

$x_{\mathit{ij}}\ge 0,i\ne j,i=1,\dots ,5\text{and}j=1,\dots ,5$

19.5.2 Solution of the Traveling Salesman Problem Using Excel Solver

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.

Box 19.6

Names Attributed to the Cells of Fig. 19.13

Name	Cells
Routes	C5:V5
Total_distance	X5
Visits_j	W11:W15
Visits_i	W17:W21
Sub_routes_2_nodes	W23:W32
Sub_routes_3_nodes	W34:W43
Sub_routes_4_nodes	W45:W49

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, x₁₄ = 1, x₂₁ = 1, x₃₂ = 1, x₄₅ = 1, and x₅₃ = 1 that corresponds to the route 1 → 4 → 5 → 3 → 2 → 1 (or x₁₂ = 1, x₂₃ = 1, x₃₅ = 1, x₄₁ = 1, x₅₄ = 1) that corresponds to the opposite direction) with z = 217, 21. This solution may also be represented graphically, as shown in Fig. 19.16.

19.6 The Facility Location Problem

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.

19.6.1 Modeling of the Facility Location Problem

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:

c_ij = transportation cost from facility i to the consumer j

f_i = fixed cost of keeping facility i open

C_{max, i} = maximum capacity from facility i

D_j = demand from consumer j

Decision variables:

x_ij = quantity transported from facility i to the consumer j

$y_i=\left\{\begin{array}{l}1\text{if facility}i\text{is open}\\ 0\text{otherwise}\end{array}\right.$

Mathematical formulation:

$\begin{array}{l}{F}_{\mathrm{obj}}=minz=\sum _{i=1}^m{f}_i{y}_i+\sum _{i=1}^m\sum _{j=1}^n{c}_{\mathit{ij}}{x}_{\mathit{ij}}\\ \mathrm{s}.\mathrm{t}.\\ \begin{array}{llll}\sum _{j=1}^n{x}_{\mathit{ij}}\le C_{max,i}\cdot y_i,& i=1,\dots ,m& & \left(1\right)\\ \sum _{i=1}^m{x}_{\mathit{ij}}=D_j,& j=1,\dots ,n& & \left(2\right)\\ x_{\mathit{ij}}\ge 0,& i=1,\dots ,m,& j=1,\dots ,n& \left(3\right)\\ y_i\in \left\{0,1\right\},& i=1,\dots ,m& & \left(4\right)\end{array}\end{array}$

  (19.6)

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 x_ij are positive and that the variables y_i are binary.

Example 19.5

A food sector company is planning to open new factories and is considering five possibilities of cities in Brazil: Manaus, Fortaleza, Vitoria, Barueri, and Curitiba. From the new facilities, the products will be delivered to five final customers: Sao Luis, Brasilia, Belo Horizonte, Rio de Janeiro, and Sao Paulo (Fig. 19.17).

Each factory has a fixed cost for maintenance and a maximum capacity, as shown in Table 19.E.5. The transportation costs per unit transported from each factory to each final consumer, besides the demand from consumers, are also detailed in Table 19.E.5. The company wishes to determine which factory(ies) to open, so as to minimize the sum of the fixed costs for installation and the transportation costs, ensuring that the demand of the final customers will be met. Model the facility location problem.

Table 19.E.5

Costs for Transportation, Fixed Cost, Capacity, and Demand

	Unit transportation costs
	Sao Luis	Brasilia	Belo Horizonte	Rio de Janeiro	Sao Paulo	Fixed cost	Capacity
Manaus	0.82	0.95	1.10	1.33	1.22	111,000	35,000
Fortaleza	0.74	1.12	1.06	1.13	1.24	124,000	30,000
Vitoria	1.34	1.24	0.72	0.72	0.88	120,000	25,000
Barueri	1.48	1.26	0.98	0.95	0.70	135,000	30,000
Curitiba	1.52	1.45	1.33	1.22	1.15	140,000	20,000
Demand	16,000	18,000	12,000	17,000	20,000

Solution

The decision variables of the model are:

x_ij = quantity transported from facility i to the consumer j, i = 1, …, 5 and j = 1, …, 5.

$y_i=\left\{\begin{array}{l}1\text{if facility}i\text{is open}\\ 0\text{otherwise}\end{array}\right.,i=1,\dots ,5$

in which the index i corresponds to:

i = 1 (Manaus), i = 2 (Fortaleza), i = 3 (Vitoria), i = 4 (Barueri), and i = 5 (Curitiba);

and the index j corresponds to:

j = 1 (Sao Luis), j = 2 (Brasilia), j = 3 (Belo Horizonte), j = 4 (Rio de Janeiro), and j = 5 (Sao Paulo).

The objective function seeks to minimize the sum of the fixed costs for factories maintenance and for transportation costs:

$\begin{array}{l}{F}_{\mathit{obj}}=minz=111,000y_1+124,000y_2+120,000y_3+135,000y_4+140,000y_5\\ +0.82x_{11}+0.95x_{12}+1.10x_{13}+1.33x_{14}+1.22x_{15}\\ +0.74x_{21}+1.12x_{22}+1.06x_{23}+1.13x_{24}+1.24x_{25}\\ +1.34x_{31}+1.24x_{32}+0.72x_{33}+0.72x_{34}+0.88x_{35}\\ +1.48x_{41}+1.26x_{42}+0.98x_{43}+0.95x_{44}+0.70x_{45}\\ +1.52x_{51}+1.45x_{52}+1.33x_{53}+1.22x_{54}+1.15x_{55}\end{array}$

The constraints of the model are specified as follows:

1. 1. The maximum capacity of each factory may not be exceeded:

• x₁₁ + x₁₂ + x₁₃ + x₁₄ + x₁₅ ≤ 35,000y₁    (factory in Manaus)
• x₂₁ + x₂₂ + x₂₃ + x₂₄ + x₂₅ ≤ 30,000y₂    (factory in Fortaleza)
• x₃₁ + x₃₂ + x₃₃ + x₃₄ + x₃₅ ≤ 25,000y₃    (factory in Vitoria)
• x₄₁ + x₄₂ + x₄₃ + x₄₄ + x₄₅ ≤ 30,000y₄    (factory in Barueri)
• x₅₁ + x₅₂ + x₅₃ + x₅₄ + x₅₅ ≤ 20,000y₅    (factory in Curitiba)

1. 2. The demand of each client should be met:

• x₁₁ + x₂₁ + x₃₁ + x₄₁ + x₅₁ = 16,000    (consumer in Sao Luis)
• x₁₂ + x₂₂ + x₃₂ + x₄₂ + x₅₂ = 18,000    (consumer in Brasilia)
• x₁₃ + x₂₃ + x₃₃ + x₄₃ + x₅₃ = 12,000    (consumer in Belo Horizonte)
• x₁₄ + x₂₄ + x₃₄ + x₄₄ + x₅₄ = 17,000    (consumer in Rio de Janeiro)
• x₁₅ + x₂₅ + x₃₅ + x₄₅ + x₅₅ = 20,000    (consumer in Sao Paulo)

1. 3. The decision variables x_ij are positive:

• x_ij ≥ 0,     i = 1, …, 5,     j = 1, …, 5

1. 4. The decision variables y_i are binary:

• y_i ∈ {0, 1},     i = 1, …, 5

19.6.2 Solution of the Facility Location Problem Using Excel Solver

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.

Box 19.7

Formulas Utilized in Fig. 19.18

Cell	Formula
C14	= SUM(C23:G23)
C15	= SUM(C24:G24)
C16	= SUM(C25:G25)
C17	= SUM(C26:G26)
C18	= SUM(C27:G27)
H14	= SUM(C23:C27)
H15	= SUM(D23:D27)
H16	= SUM(E23:E27)
H17	= SUM(F23:F27)
H18	= SUM(G23:G27)
E14	= I5 x H23
E15	= I6 x H24
E16	= I7 x H25
E17	= I8 x H26
E18	= I9 x H27
I23	= SUMPRODUCT(C5:H9,C23:H27)

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.

Box 19.8

Names Attributed to the Cells of Fig. 19.18

Name	Cells
Supply	C14:C18
Capacity_y	E14:E18
Delivery	H14:H18
Demand	J14:J18
Quantities_transported	C23:G27
Location	H23:H27
Total_cost	I23

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, x₁₂ = 18,000, x₁₅ = 17,000, x₂₁ = 16,000, x₂₃ = 7,000, x₃₃ = 5,000, x₃₄ = 17,000, x₃₅ = 3,000, y₁ = 1, y₂ = 1, and y₃ = 1 with z = 430,580.00_. For this problem, Solver can find more than one optimal solution.

19.7 The Staff Scheduling Problem

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.

19.7.1 Solution of the Staff Scheduling Problem Using Excel Solver

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.

Box 19.9

Formulas Utilized in Fig. 19.21

Cell	Formula
G8	= SUMPRODUCT(B8:F8,$B$21:$F$21)
G9	= SUMPRODUCT(B9:F9,$B$21:$F$21)
G10	= SUMPRODUCT(B10:F10,$B$21:$F$21)
G11	= SUMPRODUCT(B11:F11,$B$21:$F$21)
G12	= SUMPRODUCT(B12:F12,$B$21:$F$21)
G13	= SUMPRODUCT(B13:F13,$B$21:$F$21)
G14	= SUMPRODUCT(B14:F14,$B$21:$F$21)
G15	= SUMPRODUCT(B15:F15,$B$21:$F$21)
G16	= SUMPRODUCT(B16:F16,$B$21:$F$21)
G17	= SUMPRODUCT(B17:F17,$B$21:$F$21)
G21	= SUMPRODUCT(B5:F5,$B$21:$F$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.

Box 19.10

Names Attributed to the Cells of Fig. 19.21

Name	Cells
Total_employees	G8:G17
Minimum_employees	I8:I17
Quantity_employees	B21:F21
Total_cost	G21

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, x₁ = 22, x₂ = 18, x₃ = 14, x₄ = 30, and x₅ = 18 with z = 11,430.

19.8 Exercises

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):

1. a) $\begin{array}{l}maxz=6x_1+5x_2\\ \mathrm{s}.\mathrm{t}.\\ 2x_1+3x_2\le 4\\ 4x_1+2x_2\le 6\\ x_1,x_2\in \left\{0,1\right\}\end{array}$
2. b) $\begin{array}{l}minz=2x_1+5x_2\\ \mathrm{s}.\mathrm{t}.\\ 3x_1+5x_2\ge 30\\ 6x_1+3x_2\ge 36\\ x_1,x_2\ge 0\\ x_1\text{integer}\end{array}$
3. c) $\begin{array}{l}maxz=2x_1+3x_2\\ \mathrm{s}.\mathrm{t}.\\ 5x_1+2x_2\le 50\\ 2x_1+4x_2\le 66\\ x_1,x_2\ge 0\\ x_1,x_2\mathrm{are}\text{integers}\end{array}$
4. d) $\begin{array}{l}maxz=3x_1+8x_2\\ \mathrm{s}.\mathrm{t}.\\ 2x_1+5x_2\le 20\\ 3x_1+5x_2\le 60\\ x_1\in \left\{0,1\right\}\\ x_2\ge 0\text{and integer}\end{array}$
5. e) $\begin{array}{l}maxz=4x_1+6x_2\\ \mathrm{s}.\mathrm{t}.\\ 2x_1+5x_2\le 2\\ 3x_1+2x_2\le 6\\ x_1,x_2\ge 0\\ x_1,x_2\in \left\{0,1\right\}\end{array}$
6. f) $\begin{array}{l}minz=5x_1+7x_2\\ \mathrm{s}.\mathrm{t}.\\ 2x_1+5x_2\ge 12\\ 4x_1+2x_2\ge 10\\ x_1\in \left\{0,1\right\}\\ x_2\ge 0\end{array}$
7. g) $\begin{array}{l}minz=3x_1+8x_2\\ \mathrm{s}.\mathrm{t}.\\ 5x_1+2x_2\ge 40\\ 2x_2\ge 10\\ x_1,x_2\ge 0\\ x_1\text{integer}\end{array}$

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:

$\begin{array}{l}maxz=2x_1+3x_2\\ \mathrm{s}.\mathrm{t}.\\ 2x_1+5x_2\le 20\\ 5x_1+3x_2\le 30\\ x_1,x_2\ge 0\\ x_1,x_2\mathrm{are}\text{integers}\end{array}$

You are to:

1. a) Solve the corresponding linear problem (relaxing the integrality constraints) in graphical form.
2. b) Solve the original problem graphically, enumerating all of the possible integer solutions.
3. c) Determine the optimal solution of the original problem using Excel Solver.

Section 19.2 (ex. 3). Same for the following integer programming problem:

$\begin{array}{l}maxz=x_1+2x_2\\ \mathrm{s}.\mathrm{t}.\\ x_1+3x_2\le 6\\ 3x_1+x_2\le 9\\ x_1,x_2\ge 0\\ x_1,x_2\mathrm{are}\text{integers}\end{array}$

Section 19.2 (ex. 4). Same for the following integer programming problem:

$\begin{array}{l}maxz=3x_1+2x_2\\ \mathrm{s}.\mathrm{t}.\\ 4x_1+2x_2\le 16\\ x_2\le 2\\ x_1,x_2\ge 0\\ x_1,x_2\mathrm{are}\text{integers}\end{array}$

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.

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.

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.

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:

1. 1. The demand for all of the products should be satisfied;
2. 2. Each consolidation point has a maximum storage capacity;
3. 3. The supply capacity may not be exceeded for each product.

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.

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.