Optimization integer programming

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

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

A very popular scheduling framework is based on mixed-integer programming. Herein, the scheduling problem is modeled in terms of variables and algebraic inequalities and solved by mathematical optimization techniques. In opposition to this well-established framework, a different approach is advocated in the paper by Alur and Dill [8] on timed automata (TA). 

Nemhauser, G.L and Wolsey, L.A. (1988) Integer Programming and Combinatorial Optimization, Wiley, New York. 

Schrage, L. Optimization Modeling with UNDO. Duxbury Press, Pacific Grove, CA (1997). Schrijver, A. Theory of Linear and Integer Programming. Wiley, New York (1986). 

The Excel Solver. Microsoft Excel, beginning with version 3.0 in 1991, incorporates an NLP solver that operates on the values and formulas of a spreadsheet model. Versions 4.0 and later include an LP solver and mixed-integer programming (MIP) capability for both linear and nonlinear problems. The user specifies a set of cell addresses to be independently adjusted (the decision variables), a set of formula cells whose values are to be constrained (the constraints), and a formula cell designated as the optimization objective. The solver uses the spreadsheet interpreter to evaluate the constraint and objective functions, and approximates derivatives, using finite differences. The NLP solution engine for the Excel Solver is GRG2 (see Section 8.7). 

Branch and bound (BB) is a class of methods for linear and nonlinear mixed-integer programming. If carried to completion, it is guaranteed to find an optimal solution to linear and convex nonlinear problems. It is the most popular approach and is currently used in virtually all commercial MILP software (see Chapter 7). 

Although, as explained in Chapter 9, many optimization problems can be naturally formulated as mixed-integer programming problems, in this chapter we will consider only steady-state nonlinear programming problems in which the variables are continuous. In some cases it may be feasible to use binary variables (on-off) to include or exclude specific stream flows, alternative flowsheet topography, or different parameters. In the economic evaluation of processes, in design, or in control, usually only a few (5-50) variables are decision, or independent, variables amid a multitude of dependent variables (hundreds or thousands). The number of dependent variables in principle (but not necessarily in practice) is equivalent to the number of independent equality constraints plus the active inequality constraints in a process. The number of independent (decision) variables comprises the remaining set of variables whose values are unknown. Introduction into the model of a specification of the value of a variable, such as T = 400°C, is equivalent to the solution of an independent equation and reduces the total number of variables whose values are unknown by one. 

Relaxation of hard constraints is critical for optimization-based planning models used in industry practice with more than even 100,000 constraints and specifically for hard integer programming problems (Fisher 2004). Hard constraints set hard minimum and maximum boundaries for decision variables that have to be fulfilled. It may occur that no solution exists fitting all constraints at the same time. Planners have difficulties to identify manually constraints leading to infeasibility. Value chain planning model infeasibility is mainly caused by volume-related constraints of material flows e.g. by bounding sales quantities, inventories, transportation quantities, production and procurement quantities. Examples in literature for relaxation methods to e.g. transportation problems is presented by Klose/Lidke (2005)... 

Relative and absolute MIP gap mixed integer programming parameter for controlling optimization accuracy e g. MIP gap of 1% leads to an algorithm stop, if the objective value cannot be improved within a tolerance interval of 1%. 

The realization of the need and importance of petrochemical planning has inspired a great deal of research in order to devise different models to account for the overall system optimization. Optimization models include continuous and mixed-integer programming under deterministic or parameter uncertainty considerations. Related literature is reviewed at a later stage in this book, based on the chapter topic. 

Jimenez, G.A. and Rudd, D.F. (1987) Use of a recursive mixed-integer programming model to detect an optimal integration sequence for the Mexican petrochemical industry. Computers e[ Chemical Engineering, 11, 291. 

K. Holmberg. Generalized cross decomposition applied to nonlinear integer programming problems duality gaps and convexification in parts. Optimization, 23 341, 1992. 

H. Mawengkang and B. A. Murtagh. Solving nonlinear integer programs with large scale optimization software. Ann. of Oper. Res., 5 425, 1986. 

A. Schrijver. Theory of linear and integer programming. Wiley-Interscience series in discrete mathematics and optimization. J. Wiley, 1986. 

Since scope economies are especially hard to quantify, a separate class of optimization models solely dealing with plant loading decisions can be found. For example, Mazzola and Schantz (1997) propose a non-linear mixed integer program that combines a fixed cost charge for each plant-product allocation, a fixed capacity consumption to reflect plant setup and a non-linear capacity-consumption function of the total product portfolio allocated to the plant. To develop the capacity consumption function the authors build product families with similar processing requirements and consider effects from intra- and inter-product family interactions. Based on a linear relaxation the authors explore both tabu-search heuristics and branch-and-bound algorithms to obtain solutions. 

Solution of the optimization problem requires algorithms that locate the phase distribution corresponding to the global optimum. Castillo and Grossmann (1) term this a mixed-integer programming problem and suggest a tree to enumerate the possible combinations of phases at equilibrium. 

Shelton, M. R., and Grossmann, I. E. Optimal Synthesis of Integrated Refrigeration Systems. I Mixed-integer Programming Model, Comput. Chem. Eng. 10, 445 (1986a). 

---