Modeling with Binary Variables

Integer programming (IP) models with binary variables have been successfully used in practice to design supply chain networks. Hence, we begin this chapter with a review of modeling with binary variables. We will then apply the IP models for location and distribution decisions in supply chain management. 

we discuss an important aspect of supply chain network design, called Risk Pooling. Risk pooling refers to the use of a more consolidated distribution network with fewer facilities, each serving a large allocation of customer demand. A consolidated distribution system reduces supply chain costs—inventory holding cost (IHC), order costs, and facilities cost. However, customer service suffers, as time to fulfill customer demand increases. We will study the tradeoff between supply chain cost and customer service under risk pooling. 

we present some basic results in continuous location models and how they relate to supply chain network design. We conclude the chapter by discussing several real-world applications of IP models used successfully in supply chain network design and other problems. 

---

An example of structurally represented policies is a decision between using direct shipments and using a centralized warehouse. Evaluation of such alternatives effectively implies development of two separate models, which share common features. However, it is also possible to constmct a single model with binary variables used for switching between different structures. 

The flash drum in Figure 20.9 illustrates a situation where a stream containing a binary mixture of two components, A and B, is flashed through a valve and separated in a flash drum into an overhead vapw stream and a residual liquid product stream. The hquid in the drum is cooled by external heat exchange with hquid recycle. This process is modeled with 11 variables F,-, T, Q, F, Pf h, Tf, Fv, y, Fi, and x. Two variables are considered to be extemaUy defined, T and C. The model involves five equations a... 

Figure 1 shows the different possibilities in a two-column system with two components. At the inlet of a column, it is possible to feed the mixture to be separated (e.g. molasses), the eluent (e.g. water), or the outflow from some other column. At the outlet of a column, one can collect the products or re-use the outcome for further separation. These decisions are modeled using binary variables, yj, ykij and Xku, as illustrated in Figure 1. The times when these decisions are made are denoted by i , tr, where to = 0. The number of intervals is denoted by T and the length of the period by t = tr- The index i denotes which binary variables are valid during the time interval The indexes k and /...

Subject to the following constraints are (i) process models, material balances of the generic model block (Eqs. 1.1-1.7) (ii) process constraints, rules defining the superstructure together with binary variables (5 ", S " ) and the flow constraints (Eqs. 1.8-1.10) ... 

We define a fee lattice and affect at each site n, a spin or an occupation variable <7 which takes the value +1 or —1 depending on whether site n is occupied by a A or B atom. Within the generalized perturbation method , it has been shown that substitutional binary alloys AcBi-c may be described within a Ising model with effective pair interactions with concentration dependence. Thus, the energy of a configuration c = (<7i,<72,- ) among the 2 accessible configurations for one system can be written... 

Lastly, this chapter presents the concept of aggregation as a means of reducing the binary dimension in large-scale problems. In the examples cited, the objective values predicted by the aggregation model were very close to those predicted by the general formulation. However, the aggregation model requires a much smaller number of binary variables which is concomitant with significantly reduced computational effort. 

The overall model for this scenario involves 5614 constraints, 1132 continuous 280 binary variables. Three major iterations with an average of 1200 nodes in the branch and bound search tree were required in the solution. The objective value of 1560 kg, which corresponds to 33.89% reduction in freshwater requirement, was obtained in 60.24 CPU seconds. An equivalent of this scenario, without reusable water storage, i.e. scenario 2, resulted in 13% reduction in fresh water. Figure 4.12 shows the water recycle/reuse network corresponding to this solution. 

Table 4.4 is the summary of the mathematical model and the results obtained for the case study. The model for scenario 1 involves 637 constraints, 245 continuous and 42 binary variables. Seventy nodes were explored in the branch and bound algorithm. The model was solved in 1.61 CPU seconds, yielding an objective value (profit) of 1.61 million over the time horizon of interest, i.e. 6 h. This objective is concomitant with the production of 850 t of product and utilization of 210 t of freshwater. Ignoring any possibility for water reuse/recycle, whilst targeting the same product quantity would result in 390 t of freshwater utilization. Therefore, exploitation of water reuse/recycle opportunities results in more than 46% savings in freshwater utilization, in the absence of central reusable water storage. The water network to achieve the target is shown in Fig. 4.14. 

As shown in Table 4.4, the model for scenario 2, which is a nonconvex MINLP, consists of 1195 constraints, 352 continuous and 70 binary variables. An average of 151 nodes were explored in the branch and bound algorithm over the 3 major iterations between the MILP master problem and NLP subproblems. The problem was solved in 2.48 CPU seconds with an objective value of 1.67 million. Whilst the product quantity is the same as in scenario 1, i.e. 850 t, the water requirement is only 185 t, which corresponds to 52.56% reduction in freshwater requirement. The water network to achieve this target is shown in Fig. 4.15. 

The example was formulated in GAMS 22.0 and solved using the DICOPT2 solution algorithm, with CPLEX 9.1.2 as the MIP solver and CONOPT3 as the NLP solver. The model was solved using a Pentium 4 3.2 GHz processor and required 16.8 CPU seconds to find a solution. DICOPT did 4 major iterations to find the final solution. The optimal number of time points was 8, which resulted in 192 binary variables for the model. 

The MINLP-model instances comprised 200 binary variables, 588 continuous variables and 1038 constraints. The linearization not only eliminates the nonlinearity but also leads to a reduced number of398 continuous variables and 830 constraints (the number of 200 binary variables is unchanged). The MINLP-problems were solved by the solver architecture DICOPT/CONOPT/CPLEX, and the MILP problems were solved by CP LEX, both on a Windows machine with an Intel Xeon 3 GHz CPU and 4 GB RAM. 

A simpler and general discrete time scheduling formulation can also be derived by means of the Resource Task Network concept proposed by Pantelides [10], The major advantage of the RTN formulation over the STN counterpart arises in some problems involving many identical pieces of equipment. In these cases, the RTN formulation introduces a single binary variable instead of the multiple variables used by the STN model. The RTN-based model also covers all the features at the column on discrete time in Table 8.1. In order to deal with different types of resources in a uniform way, this approach requires only three different classes of constraints in terms ofthree types of variables defining the task allocation, the batch size, and the resource availability. Briefly, this model reduces the batch scheduling problem to a simple resource balance problem carried out in each predefined time period. 

An alternative formulation is based on the concept of immediate batch precedence. In contrast to the previous model, allocation and sequencing decisions are divided into two different sets of binary variables. This idea is described in the work presented by Mendez et al. [30], where a single-stage batch plant with multiple equipment in parallel is assumed. Relevant work following this direction can also be found in Gupta and Karimi [31]. Key variables are defined as follows ... 

The occurrence of the set-up procedure in period i is denoted by the binary variable Wi (0 = no, 1 = yes). The production costs per batch are denoted by p = 1.0 and the cost for a set-up is y = 3.0. Demands di that are satisfied in the same period as requested result in a regular sale Mi with a full revenue of a = 2.0 per unit of product. Demands that are satisfied with a tardiness of one period result in a late sale Mf with a reduced revenue of aL = 1.5 per unit. Demands which are not satisfied in the same or in the next period result in a deficit Bf with a penalty of a = 0.5 per unit. The surplus production of each period is stored and can be sold later. The amount of batches stored at the end of a period is denoted by Mf and the storage costs are a+ =0.1 per unit. The objective is to maximize the profit over a horizon of H periods. The cost function P contains terms for sales revenues, penalties, production costs, and storage costs. For technical reasons, the model is reformulated as a minimization problem ... 

In our case study, the problem instances for SNP optimization result from master data of approximately 10000 location-products, 10000 recipes, 400 production resources and 10 resources relevant for campaign production with 3-10 different products per campaign resource. This translates into a MIP model with about 700 000 continuous variables, 1000 binary variables and 300 000 linear constraints. 

In the top temperature interval only the matches between the hot process streams and the cold process streams can take place. In the bottom interval we have the matches of Hi, H2, HZ with Cl and CW only since C2 does not participate in this TI. As a result we need to introduce 12 instead of 18 continuous variables Qijk. We need to introduce nine binary variables for the aforementioned potential matches. The MILP transshipment model P2 is ... 

Remark 1 If no approximation is introduced in the PFR model, then the mathematical model will consist of both algebraic and differential equations with their related boundary conditions (Horn and Tsai, 1967 Jackson, 1968). If in addition local mixing effects are considered, then binary variables need to be introduced (Ravimohan, 1971), and as a result the mathematical model will be a mixed-integer optimization problem with both algebraic and differential equations. Note, however, that there do not exist at present algorithmic procedures for solving this class of problems. 

---