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


Chapter 15
Unification of Artificial Intelligence with Optimization

Jae Kyu Lee


CONTENTS

Abstract
1. Introduction
2. Representation of Linear Programming Models: UNIK-LP
2.1. Object-Oriented Representation of Linear Programming Models
  2.2. Knowledge-Assisted Model Formulation
3. Unification of LP Model with Rule-Based System: UNIK-PMA
3.1. Post-Model Analysis Procedure
  3.2. Trade-Offs Between Goals in the Optimization Model and Rule-Based System
4. Representation of Integer Programming: UNIK-IP
4.1. An Illustrative Integer Programming Model for Optimal Savings Plan
  4.2. Knowledge-Based Relaxation
5. Neural Network-Based Adaptive Optimal Control: UNIK-LP/NN
5.1. Neural Network Model for the Control of Optimization Model
  5.2. Architecture of UNIK-LP/NN
6. Integration of Rules with Constraint Satisfaction Problem: UNIK-CRSP
6.1. Constraint and Rule Satisfaction Problems
  6.2. Unified Reasoning for CRSP
  6.3. Illustrations
7. Conclusion
References

ABSTRACT

This chapter reviews the UNIK project, which unifies the Artificial Intelligence (AI) with optimization models for decision support. Our goal is to unify the specification of problems, to encompass as many hybrid types of problems as possible, from both AI and optimization. Currently, the types of problems selected from the AI side are the rules, compatibility constraints, and neural network, while linear programming and integer programming models are selected from the optimization side. A key issue to be resolved for the unification is the unified representation of the optimization model and rules so that they can understand each other. The next issue is designing the unified architecture and devising the solution method. This chapter reviews the above issues one by one, with illustrative applications.

1. INTRODUCTION

Artificial Intelligence (AI) and optimization are two of the most popular paradigms for decision aid. Since a large group of problems requires adopting both paradigms in a unified manner, we need to develop methods of formulating and solving such problems, which might be named Unified Programming. The basic components from the optimization side of Unified Programming are Linear Programming, Integer Programming, and Nonlinear Programming; while Rule-based Reasoning, Neural Network, Constraint Satisfaction Problems, and Case-Based Reasoning, and Search techniques come from the AI side.

Linear Programming is a basic decision modeling technique that optimizes a linear objective function subject to the linear constraints as illustrated in (1)-(4) in Section 2.1. The decision variables in the linear programming models are continuous real numbers. If the decision variables are restricted to integer numbers, the model becomes Integer Programming. If any functions in the linear programming becomes nonlinear, the model becomes a Nonlinear Programming model (Murty, 1995). A typical Constraint Satisfaction Problem is a decision model that seeks consistent solutions that satisfy the multiple compatibility constraints (Kuman, 1992). Case Based Reasoning is a paradigm that searches for solutions used in the most similar case to the newly faced problem, and adjusts the difference, if there exists discrepancy, between the new problem and the prior similar problem.

To achieve the framework of Unified Programming, the mutually interpretable representation of problems is an essential foundation. For a literature review on unification of AI with optimization, readers may refer to the two special issues: "Integration and Competition of AI with Quantitative Methods for Decision Support" in Expert Systems with Applications (Vol. 1, 1990) and "Unified Programming" in Decision Support Systems (Vol. 18, No. 3, 1996). As a book, refer to Holsapple et al. (1995).

In Section 2, we represent linear programming models in objects at a semantic level, which is understandable not only by the optimization solver, but also by the rules. UNIK-OPT is a knowledge-assisted optimization modeling system that can easily produce such a semantic optimization formulation. Since the initial scope of UNIK-OPT is Linear Programming (LP), the system for LP is named UNIK-LP (Lee and Kim, 1995). In Section 3, the independently prepared rule-based systems and optimization models are integrated via the shared decision variables. The trade-offs among the goals in the rule-based system and the optimization model are supported by using the Post-Model Analysis approach (Lee and Song, 1995). This approach makes integrated modeling possible for a class of Multiple Criteria Decision-Making problems that include both quantitative and qualitative factors. Several illustrative cases are discussed along with a tool UNIK-PMA (Lee and Song, 1996). This approach can be extended to the group decision aid (Lee and Jeong, 1995).

In Section 4, UNIK-LP, which initially started with the linear programming, is now extended to cover the high-level representation of integer programming models (UNIK-IP) (Yeom and Lee, 1996) and Lagrangian relaxation models (UNIK-RELAX) (Kim and Lee, 1996). In Section 5, the neural network is applied to the adaptive control on the optimization model and a tool UNIK-LP/NN is developed for this purpose. An application is demonstrated with refinery (Lee and Kim, 1996). In Section 6, a hybrid representation and reasoning that satisfies both constraints and rules are presented. The framework can be applied to many planning and design problems because it allows for trade-offs among conflicting goals. We illustrate the system UNIK-CRSP with examples for planning and configuration (Lee, Shim, and Kwon, 1996).


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.