![]() |
|||
![]()
|
![]() |
![]() |
![]() |
3.2. TRADE-OFFS BETWEEN GOALS IN THE OPTIMIZATION MODEL AND RULE-BASED SYSTEMThe major advantage of the PMA procedure is that it can support the trade-offs between the goals regardless of their association with the optimization model or rule base. Three types of trade-offs can be supported systematically (Lee and Song, 1995):
If such trade-offs happen in the organization in which one department uses a rule-based model, while the other department uses an optimization model, the PMA procedure can be used for negotiating support procedures between different departments. An experimental application developed in this line is the negotiation of work schedule between the auditing firm and multiple individual auditors. The auditing firm seeks the firm's profit, while each auditor seeks an individually preferred schedule (Lee and Jeong, 1995). To help with communication among the agents, we need to employ the agents' communication language. This application can also be extended for use in negotiations between hostile agents.
4. REPRESENTATION OF INTEGER PROGRAMMING: UNIK-IPThe next step of UNIK-LP is the extention of the LP to integer programming (IP). The IP model can be easily represented on the linear programming model simply by additionally identifying whether the variables are integer, 0 or 1. This level of representation is called a base level. However, it will be much easier if the models can be represented using the high-level logical operators such as IF-THEN and EITHER-OR. So, UNIK-IP is designed to allow such logical operators; automatically transforming the high-level representation to the base-level representation. The logical operators necessary for IP models formulation are: AND, k-fold, at_least, at_most, NOT, Binary, XOR, OR, EITHER-OR, IF-THEN, and FIXED-CHARGE. So, all these operators are adopted in UNIK-IP (Yeom and Lee, 1996). For instance, the operator that needs to satisfy at least k out of m constraints -- At_Least_<k>_Constraint_<m>(f11(X) [less than or equal to] 0, ..., fm(X) [less than or equal to] 0) -- implies the addition of the technical constraints in Equations 5 and 7 to the original model. Note that the constraints in the list should have the canonical form of fi(X) [less than or equal to] 0.
If the model builder is required to identify At_Least_<k>_Constraint_<m>(...), this will be much easier than formulating the model (5)-(7) at base level. 4.1. AN ILLUSTRATIVE INTEGER PROGRAMMING MODEL FOR OPTIMAL SAVINGS PLANUNIK-IP is applied to the formulation of optimal savings plan. In this example, there are six groups of complex constraints. Among the constraints, the minimum balance restriction of an account requires the saving balance EITHER to exceed the minimum amount to open the account OR to stay unopened. This means that the EITHER-OR operator is adequate in expressing the situation. As another example, some savings products are not allowed to be possessed together. Such mutually exclusive relationships can be effectively represented by using the IF-THEN expression. IF the balance of a product, which has a mutually exclusive relationship, is non-zero, THEN the balance of other products in the mutually exclusive group should be kept zero (Lee and Nam, 1996). In this manner, UNIK-IP can effectively support the formulation of complex IP model. 4.2. KNOWLEDGE-BASED RELAXATIONUsually, a large-scale IP model is not easy to solve. So, finding a series of solution algorithm is an important issue in solving the IP problem. One of the most popular approaches to solving IP models is Lagrangian Relaxation (Fisher, 1981). Lagrangian relaxation is a scheme of relaxing the portion of constraints that makes the model too complex to solve, and finding a tight bound with the relaxed problem to evaluate the performance of some heuristic algorithms. UNIK-RELAX identifies the structural characteristics of the IP model to determine which constraints should be relaxed to generate the Lagrangian model. For the identification of the structure, the relationship among the embedded structures, constraints, and blocks of terms are identified as depicted in Figure 6 (Kim and Lee, 1996). For instance, the embedded structure of 0_1_knapsack subproblem can be identified by the following rule: IF ([inverted sans serif] CONSTRAINT(Capacity)) AND XOR(Max, Min) THEN STRUCTURE = 0_1_Knapsack. This means that if there exists a capacity constraint in the IP model, with either maximizing or minimizing objective function, the model includes the 0_1_knapsack subproblem. The capacity constraint can be identified by the following condition: ALL BOT (AT_LHS(Volume_Sum_0_1) AND AT_RHS(Nonnegative_Real_Coefficient) AND OPERATOR = LE This means that if a constraint represented in the object has the Volume_Sum_0_1 blocks of terms (BOT) in the left-hand side and the Nonnegative_Real_Coefficient BOT in the right-hand side, this constraint is a capacity constraint. The distinctiveness of Volume_Sum_0_1 BOT can be identified by Volume_Sum_0_1 = AND(Nonnegative_Real_Coefficient 0_1_Integer_Variable). Note that those distinctions can be identified owing to the object-oriented representation of the integer programming model. For the identification of Lagrangian Relaxation, we need 15 elementary distinctive BOTs, 6 composite distinctive BOTs, 10 distinctive constraints, and 7 embedded subproblem structures. Although the current study has identified only 7 embedded structures in the IP model, the beauty of this approach is its expandability by adding more rules. This is extremely important because we have opened the way of automatically identifying the characteristics of problems. Clearly, this implies that an appropriate solution method can also be automatically identified.
|
![]() |
|
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. |