Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


2. REPRESENTATION OF LINEAR PROGRAMMING MODELS: UNIK-LP

2.1. OBJECT-ORIENTED REPRESENTATION OF LINEAR PROGRAMMING MODELS

A specific Linear Programming model should be represented in such a way as to be understood by rule-based systems. To accomplish this, the LP model needs to be represented in objects, which is named as semantic form. The object-oriented LP model (named a semantic form) can be transformed to the notational form, modeling language form, and tabular form, as depicted in Figure 1. A specific semantic model is composed of constraints, blocks of terms (BOT), attributes, and indices, as depicted in Figure 1. This idea is implemented in UNIK-LP (Lee and Kim, 1995).


FIGURE 1 Structure of specific linear programming model.

For instance, consider the monthly product mix planning model, which decides the production and inventory levels.

(1)

subject to

(2)
 
(3)
 
(4)

The attributes imply:

X: production amount
I: inventory
a: unit processing time
b: capacity
c: unit cost
s: sales quantity

and the indices imply:

i: product
j: facility
t: month.

The LP model (1)-(4) is a mathematical notational form. However, this form is not compatible with the rule-based systems. So, the model may be represented in an object as follows.

          {{monthly_product_mix_a
                 IS_A: LP_MODEL
                 DIRECTION: MIN
                 OBJ_FN: (+ production_cost_BOT)
                 CONSTRAINTS: production_capacity_constraint
                              production_sales_balance_constraint
                 CONTEXT: (TIME_UNIT month)
                          (PERIOD multiple) }}

The production_capacity_constraint can also be represented in an object.

          {{production_capacity_constraint
                 IS_A: constraint
                 OPERATOR: LE
                 LHS: (+ processing_time_BOT)
                 RHS: (+ facility_capacity_BOT)
                 INDEX: facility time
                 DOMAIN: (f1,...,fN) (t1,...,tT) }}.

In this manner, the variables, constants, and indices can be represented in a top-down manner.

          {{production_amount
                 IS_A: attribute
                 SYMBOL: X
                 ROLE: variable
                 LINKED_INDEX: product facility time }}
          {{unit_processing_time
                 IS_A: attribute
                 SYMBOL: a
                 ROLE: constant
                 LINKED INDEX: product facility }}
          {{product
                 IS_A: index
                 DESCRIPTION:
                 SYMBOL: i
                 LINKED_ATTRIBUTES: production_amount
                                    inventory
                                    unit_cost
                                    unit_processing_time
                                    sales_quantity }}

Since the semantic form possess more information than the mathematical notational form, we can transform the semantic form to notational form as depicted in Figure 2. The semantic form can be transformed to the aggregated notational form (Figure 3) and individual notational form (Figure 4). Since these models usually have thousands of variables and constraints, the maintenance of the models can be made much easier by using a tool like UNIK-LP.

2.2. KNOWLEDGE ASSISTED MODEL FORMULATION

Since the formulation of the semantic LP model is not an easy task for novice model builders, the function of knowledge-assisted LP model formulation is developed for UNIK-LP. For this purpose, the knowledge base needs to retain the LP model's structure knowledge and domain-specific knowledge (such as information about products and facilities). Using this knowledge, the LP model can be generated simply by identifying the relevant indices, decision variables, and constraints from the menu in a guided manner. For a detailed step-by-step explanation, readers may refer to Lee and Kim (1995).


FIGURE 2 Four modeling views.


FIGURE 3 An Illustrative aggregte notational model.

3. UNIFICATION OF LP MODEL WITH RULE-BASED SYSTEM: UNIK-PMA

To unify an LP model with a rule base, the two should share some of the decision variables. The unified model is thus virtually a multiobjective decision-making problem that considers both the numeric objective in the linear programming model and the symbolic objectives in the rule base. To solve the unified model, the Post-Model Analysis procedure is adopted as depicted in Figure 5 (Lee and Hurst, 1988; Lee and Song, 1996; Lee and Song, 1995). In this figure, note that the LP model and rule base are independently prepared. But since the LP model is formulated in semantic form, the LP model can communicate with the rule base at the semantic level.

3.1. POST-MODEL ANALYSIS PROCEDURE

The Post-Model Analysis procedure starts by finding the optimal solution of an LP model. The optimal solution is then inputted into the fact base of the rule-based system for evaluation. If the goals in the rule base are satisfied with the current optimal solution, the current solution can be selected as a satisfactory nondominated solution both for the optimization and rule-based system. However, if the current solution is not satisfactory, the adjusted goal in the rule base should be interpreted as the additional constraints to the LP model. Transforming the rules associated with the adjusted goal to the objects of semantic LP model is the key technological function in this process. For the details, readers may refer to Lee and Song (1996). Finally, the LP model with the additional constraints should be re-solved to assure the adjusted goals.


FIGURE 4 An illustrative individual notational model.


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.