Discrete Optimization

Discrete optimization problems involve discrete decision variables. Discrete optimization problems can be classified as integer programming (IP) problems, mixed integer linear programming (MILP), and mixed integer nonlinear programming (MINLP) problems. 

The commonly used mathematical programming method for solving IP, MILP, and MINLP is the branch and bound method which uses a tree structure to define the problem and the associated binary variables. The following example shows the tree structure for the problem. 

Example 5.3 Given a mixture of four components A, B, C, D for which separation technologies given in Table 5.1 are to be considered. 

Having developed the representation, the question is how to search for the optimum. One can go through the complete enumeration, but that would involve evaluating each node of the tree. The intelligent way is to reduce the search space by implicit enumeration and evaluate as few nodes as possible. Consider the above example of separation sequencing. The objective is to minimize the cost of separation. If one looks at the nodes for each branch, there are an initial node, intermediate nodes, and a terminal node. Each node is the sum of the costs of aU earher nodes in that branch. Because this cost increases monotonicaUy as we progress through the initial, intermediate, and final nodes, we can define the upper bound and lower bounds for each branch. 

These heuristics allow us to prune the tree. If the cost at the current node is greater than or equal to the upper bormd defined earlier either from one of the prior branches or known to us from experience, then we don t need to go further in that branch. These are the two common ways to prrme the tree based on the order in which the nodes are enumerated  

---

In the formulation above, the discrete optimization on the number of compressors has been transformed into a continuous optimization on suction and delivery pressures. This transformation was made possible by the form of the compressor cost function which vanishes when pd = ps. However, if the compressor costs include a fixed capital outlay, i.e., the cost function is a linear function of horsepower with a nonzero constant term, then a branch and bound procedure must be used in conjunction with the GRG method. 

The quant net is the basis of the discrete optimization. Constraints for the process times and movements of products are considered. Batch sizes will be calculated by the optimization. 

Parker, R. G. and R. Rardin. Discrete Optimization. Academic Press, New York (1986). 

Branch and bound techniques, discrete optimization via, 26 1023 Branched aliphatic solvents, 23 104 Branched alkylbenzene (BAB), 77 725 Branched copolymers, 7 610t Branched epoxies, 70 364 Branched olefins, 77 724, 726 Branched polycarbonates, 79 805 Branched polymers, 20 391 Branched primary alcohols, synthetic processes for, 2 2 7t Branching... 

Discovery research, on macrolide antibiotics, 15 305-306 Discrete optimization problems,... 

Ouchterlony technique, 9 754 Ouricouri wax, 26 210—211 Ouricury, in mascara, 7 862 Outer approximations (OA), discrete optimization via, 26 1024 Outer—Helmholtz plane (OHP), 3 419 Outer-sphere (OS) mechanism,... 

Grossmann, I.E., van den Heever, S.A., and Harjunkoski, I. (2001) Discrete optimization methods and their role in the integration of planning and scheduling. Proceedings of Chemical Process Control Conference 6 at Tucson, 2001, http // egon.cheme.cmu.edu/papers.html accessed on June 20, 2006. 

Kleywegt, A.J., Shapiro, A., and Homem-De-Mello, T. (2001) The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12, 479. 

R. G. Parker and R. L. Rardin. Discrete optimization. Academic Press, 1988. 

Kaganovich, B. M., "Discrete Optimization of Heat Networks", 88 p. Nauka, Novosibirsk (1978). (in Russian). 

When the nonlinear discrete optimization problem is formulated as the generalized disjunctive program in (DPI), one can develop a corresponding logic-based branch-and-bound method. The basic difference is that the branching is performed... 

Balas, E. Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems, SIAM J. Alg. Disc. Methods 6, 466-486 (1985). 

Figure 3 Potential energies of PWCs versus total dipole moments for complete classes of discrete optimized configurations. Mainly the values are calculated using TIP4P potential.

Figure 5 The energy distribution of random configurations. Right side shows a part of the plot on an enlarged scale. Open circle indicates the energy of discrete optimized structure.

Crowley, T.J. Choi, K.Y. Discrete optimal control of molecular weight distribution in a batch free radical polymerization process. Ind. Eng. Chem. Res. 1997, 36, 3676-3684. 

Tabular method of discrete optimization. The basis of dynamic programming is the principle of prefix optimality. This principle states that the optimal solution to the optimization problem can be composed of optimal solutions of a limited number of smaller instances of the same type of problem. The tabular method incrementally solves subinstances of increas-... 

Balas E. 1985. Disjunctive programming and a hierarchy of relaxations for discrete optimization problems, SIAM J. Alg. Discrete Methods, 6, 466-486. 

Syslo, M. M., Deo, N., and Kawalik, J. S. (1983), Discrete Optimization Algorithms, Prentice Hall, Englewood Cliffs, NJ. 

Modeling is the process of mathematically representing a problem in a form conducive to analysis and solution. The logical nature of discrete optimization—especially pure discrete optimization— invites a variety of quite different representations. Many problems can usefully be modeled in terms of logical predicates, objects and sets, graphs, or numerous other constructs. 

The goal of all discrete optimization analysis is to find feasible solutions with good objective function values. It is rarely important to know a mathematically optimal solution to a model, since the model is itself only an approximation to the underlying problem. However, it is desirable to have a sharp bound on the objective function value that might be obtained by any feasible solution. Then, for example, if a feasible solution to a maximize problem is known with objective function value 92, and other analysis establishes that no feasible solution can produce better that 100, one can accept the 92 solution with confidence that it is no more (100 — 92)/l(X) = 8% suboptimal. The attraction of mathematically optimal solutions is that they provide good feasible solutions with zero-error bounds. 

Many search methods for discrete optimization move through a sequence of partial solutions that assign specific values to some decision variables in a model, leaving others/tkc or undetermined. A completion of a partial solution is an assignment of specific values to any remaining free variables. Of course, the definition of a partial solution includes the possibility that there are no free variables, in which case the solution is complete. 

When dealing with difficult discrete optimization problems, it is natural to search for related, but easier optimization models that can aid in the analysis. Relaxations are auxiliary optimization problems of this sort formed by weakening either the constraints or the objective function of the main problem. Specifically, an optimization problem P) is said to be a constraint relaxation of another optimization problem (P) if every solution feasible to (P) is also feasible for (P). Similarly, maximize problem (respectively minimize problem) P) is an objective relaxation of another maximize (respectively minimize) problem (P) if the two problems have the same feasible solutions and the objective function value in P) of any feasible solution is (respectively <) the objective function value of the same solution in (P). 

Relaxations of discrete optimization problems tiid in both the good solution finding and the... 

---