استخراج مدل برنامه ریزی خطی از پایگاه داده با استفاده از ابزار تجزیه و تحلیل انتهایی و شبکه های عصبی مصنوعی

Since formulating linear programming models from scratch is knowledge-intensive and, hence, very costly, knowledge-based formulation support systems have been proposed. The drawback of knowledge-based formulation support systems, however, is that they require that sufficient domain knowledge be captured in advance. Hence, the purpose of this paper is to propose a methodology that automatically recognizes and captures relevant knowledge on formulating linear programming models from a relational database. Our methodology has two components. First, first-cut models are recognized from a data dictionary via means-ends analysis (MEA). Second, valid first-cut models are isolated through the application of an artificial neural network technique. To demonstrate the integrity of our methodology, Model Miner, a prototype system, is described and tested.

Formulating linear program (LP) models from scratch is labor-intensive and costly. Formulation efforts include having to select decision variables and find linear dependencies between the left-hand side (LHS) and the right-hand side (RHS) of the model. Discerning complex relationships between database fields remains a research challenge (Fayyad, Piatetsky-Shapiro & Smyth, 1996). Because linear programming models are applicable to this case, relying on conventional discovery techniques is not efficient. For example, a module of a linear programming model consists of a set of modelling constructs that are related to each other, either by an objective function or by a constraint. These constructs offer a methodology by which linear programming models can be exacted from a database with both domain-independent and domain-specific knowledge. In this paper, we propose a two-phased LP model discovery method: a first-cut model discovery and a second-cut model discovery. The first-cut model discovery phase recognizes well-formed candidate modules from the data dictionary of a relational database. Then, a means-ends analysis (MEA) algorithm is applied. The second-cut model discovery phase selects a valid LP model among the candidate modules. In this phase, correct coefficient values are found by adopting a back propagation method. Model Miner, a prototype system, which is described in detail, tests the integrity of our methodology. The remainder of this paper is as follows. In Section 2, a literature survey on model formulation and MEA is described briefly. Overall framework for the LP model discovery is illustrated in Section 3. The first part, the first-cut model discovery from data dictionary, is delineated in Section 4. Section 5 shows the second-cut model discovery and how ANN is applied. In Section 6, a prototype system is given to show the feasibility of the proposed methodology. Finally, concluding remarks and future research issues are put in Section 7.

This paper proposes a methodology that automatically recognises and captures relevant knowledge on formulating linear programming models from a relational database. The contributions of the proposed methodology are three-fold. First, this methodology produces a knowledge superior to the knowledge revealed in traditional data mining techniques. Our methodology combs the database for causality and classification, mines optimisation knowledge, and investigates how the linear programming models can be manipulated to reveal useful forms of knowledge buried in the corporate database. Second, in comparison with other knowledge-based model formulation support systems, our methodology provides decision makers with more general model formulation support. We separate generic and domain-specific formulation knowledge. We show how MEA and artificial ANN techniques can be combined to discover LP models from the database. This kind of methodology has applications to the data-oriented decision support systems like data warehousing and OLAP. Lastly, using our prototype, the first-cut model discovery and second-cut model discovery can maintain LP models according to the change of data structure and that of data value, respectively, to produce a newly modified LP model. This capability may overcome the limitations inherent to knowledge-based formulation support systems. Model Miner, a prototype system, demonstrates the feasibility of the algorithm proposed in this paper. Experimental results show that the algorithm works better than graduate students, when those students are provided only the primitive data set and a data dictionary. The proposed algorithm, however, is limited in scope. It does not apply to a non-linear programming model and this limitation is left for further research because the non-linearity would confound the selecting available operators.