Combinatorial optimization,

A Stochastic Approach to Combinatorial Optimization and Neural Computing. John Wiley Sons, New York, 1989. 

To solve the problems of representation and control, we will employ the framework of the branch-and-bound algorithm, which has been used to solve many types of combinatorial optimization problems, in chemical engineering, other domains of engineering, and a broad range of management problems. Specifically, we will use the framework proposed by Ibaraki (1978), which is characterized by the following features ... 

The first step in solving a combinatorial optimization problem is to model the solution space itself. Such a model should be declarative in character, if it is to be independent of the characteristics of the specific algorithm that will be used to find the solution within the solution space. The model we have adopted for the scheduling of flowshop operations is the discrete decision process (DDP) introduced originally by Karp and Held (1967). As defined by Ibaraki (1978) a DDP, Y, is a triple (.S,S,/) with its elements defined as follows ... 

The large size of the solution space for combinatorial optimization problems forces us to represent it implicitly. The branch-and-bound algorithm encodes the entire solution space in a root node, which is successively expanded into branching nodes. Each of these nodes represents a subset of the original solution space specialized to contain some particular element of the problem structure. 

Theoretically it has been shown (Thayse, 1988) that the DDP formalism is closely related to a simpler form of horn clause logic, i.e., the propositional calculus. This would suggest that we could use the horn clause form to express some of the types of knowledge we are required to manipulate in combinatorial optimization problems. The explicit inclusion of state information into the representation, necessitates the shift from the simpler propositional form, to the first-order form, since we wish to parsimoniously represent properties that can be true, or take different values, in different states. By limiting the form to horn clauses, we are striving to retain the maximum simplicity of representation, whilst admitting the necessary expressive power. 

Ibaraki, T., Branch and bound procedure and state-space representation of combinatorial optimization problems. Inf. Control 36,1-27 (1978). 

Realff, M.J., Machine Learning for the Improvement of Combinatorial Optimization Algorithms A Case Study in Batch Scheduling. Ph.D Thesis, MIT., Cambridge, MA, 1992. 

Lee BW, Sheu BJ (1990) Combinatorial optimization using competitive Hopfield neural network. Proc Internat Joint Conf Neural Networks II 627, Washington, DC... 

Planning Large Supply Chain Scenarios with Quant-based Combinatorial Optimization ... 

This chapter focuses on a new approach that allows for the comprehensive planning and optimization of multi-stage production processes - the quant-based combinatorial optimization. First, a distinction is drawn between classical approaches such as Linear Programming (LP) and the quant-based combinatorial approach. Before going into the special characteristics and requirements of the process industry the one model approach with quant-based combinatorial optimization is introduced. Then we will give two examples of how this new approach is applied to real life problems. 

The quant-based combinatorial optimization accounts for the entire value chain and its associated processes, that is for all of its inputs, outputs and system parameters. Based on these data an integrated and complete model of a company s supply chain is derived, detecting in advance what impact a decision or an external influence will have on the total system. 

Initially - using the physical term quant which is used to describe the smallest energy package - the term business quant has been introduced. Let s give a definition of quant-based combinatorial optimization. First what is a quant ... 

There are numerous definitions of combinatorial optimization. We will use this definition Combinatorial optimization means algorithms which generate quants and assign them to resources such that the costs summarized over all quants are minimized and all constraints are met. ... 

The quant-based combinatorial optimization differs from classical approaches in a number of ways. First, it is the strength of the quant-based approach to account for all constraints that prevail in a real-life planning scenario. Even though they usually come into effect in complex, interrelated and varying ways. 

Companies who to date have decided in favor of the quant-based combinatorial optimization approach, are collectively characterized by a complex and multi-step supply chain whose scheduling requires the consideration of multiple constraints. By nature of their production processes, many of these companies come from the chemical or pharmaceutical industry. 

Additional Modeling Elements of the Quant-based Combinatorial Optimization 65... 

Fig. 4.3 Sketch of an often used branch and bound algorithm and corresponds to the box combinatorial optimization" in Figure 4.2.

The above example was used as a reference example in the European Research Proj ect AM ETI ST [46]. A comparison with other solution approaches clearly showed the advantage of the quant-based combinatorial optimization. 

The quant-based combinatorial optimization is a new approach. It supports the simultaneous planning and optimization of complex production problems. The solution procedure is built with operators which may be applied in any sequence allowing integrated BOM explosion and scheduling. The overall solution procedure may be extended at any time by simply adding new operators [20, 21],... 

---