Integer programming

Mixed Integer Linear Programming If the objective and constraint functions are all linear, then (3-84) becomes a mixed integer linear programming problem given by 

Note that if we relax the t binary variables by the inequalities 0 y 1, then (3-110) becomes a linear program with a (global) solution that is a lower bound to the MILP (3-110). There are specific MILP classes where the LP relaxation of (3-110) has the same solution as the MILP. Among these problems is the well-known assignment problem. Other MILPs that can be solved with efficient special-purpose methods are the knapsack problem, the set covering and set partitioning problems, and the traveling salesperson problem. See Nemhauser and Wolsey (1988) for a detailed treatment of these problems. 

More generally, MILPs are solved with branch and bound algorithms, similar to the spatial branch and bound method of the previous section, that explore the search space. As seen in Fig. 3-61, binary variables are used to define the search tree, and a number of bounding properties can be noted from the structure of (3-110). 

Upper bounds on the objective function can be found from any feasible solution to (3-110), with y set to integer values. These can be found at the bottom or leaf nodes of a branch and bound tree (and sometimes at intermediate nodes as well). The top, or root, node in 

3-60 Spatial branch and bound sequence for global optimization example. 

---

Grossmann, I. E., Mixed Integer Programming Approach for the Synthesis of Integrated Process Flowsheets, Camp. Chem. Eng., 9 463, 1985. 

Kakhu, A. L, and Flower, J. R., Synthesi ng Heat-Integrated Distillation Systems Using Mixed Integer Programming, Trans. IChemE ChERD, 66 241, 1988. 

Mixed-integer programming contains integer variables with the values of either 0 or 1. These variables represent a stmcture or substmcture. A special constraint about the stmctures states that of a set of (stmcture) integer variables only one of them can have a value of 1 expressed in a statement the sum of the values of (alternate) variables is equal to 1. In this manner, the arbitrary relations between stmctures can be expressed mathematically and then the optimal solution is found with the help of a computer program. (52). 

Using mixed-integer programming, find the minimum number of mass exchangers the benzene recovery example described in Section 3.7 (Example 3.1). 

Integer programming has been applied by De Vries [3] (a short English-language description can be found in [2]) for the determination of the optimal configuration of equipment in a clinical laboratory and by De Clercq et al. [4] for the selection of optimal probes for GLC. From a data set with retention indices for 68 substances on 25 columns, sets ofp probes (substances) (p= i,2,..., 20) were selected, such that the probes allow to obtain the best characterization of the columns. This type of application would nowadays probably be carried out with genetic algorithms (see Chapter 27). 

Taha FLA (1975) Integer Programming Theory and Applications, Academic Press. 

Glover, F., 1975. Improved linear integer programming formulation of nonlinear problems. Manag. Sci., 22(4) 455-460... 

Engineered Mixed-Integer Programming in Chemical Batch Scheduling"... 

Sand, G. and Engell, S. (2003) Modeling and solving real-time scheduling problems by stochastic integer programming. Comput. Chem. Eng., 28, 1087-1103. 

Till, J Engell, S. and Sand, G. (2005) Rigorous vs stochastic algorithms for two-stage stochastic integer programming applications. Inti. J. Inf. Technol., 11, 106-115. 

---