Neural Networks and Linear Programming
Asim Roy (Arizona State University)
This tutorial will present several new methods for generating
neural networks using linear programming. Unlike connectionist
learning methods (e.g. back propagation type learning), these
methods can both design and train the appropriate network, not
just train a pre-defined network. These LP-based methods can
be used to generate different types of neural networks
including multilayer perceptrons, radial basis function (RBF)
nets and fuzzy logic nets. The methods can be used to generate
nets both for classification and function approximation. The
tutorial will also present a new neural network learning
theory that is much more robust and reliable than classical
connectionist learning. This new learning theory essentially
defines broad computational principles (algorithmic
characteristics) that are brain-like and that should be
followed in designing all neural network algorithms. The
computational features of this new learning theory will be
discussed. This tutorial will also cover historical
developments in the area, other recent LP-based methods for
generating neural networks and computational experience with
these methods.
Return to Program Overview
From Search to Analysis: A Linguistic Geometry for Modeling and
Control
Boris Stilman (University of Colorado at Denver)
There are many real-world problems where human expert skills
in reasoning about complex systems are incomparably higher
than the level of modern computing systems. At the same time
there are even more areas where advances are required but
human problem-solving skills can not be directly applied. For
example, there are problems of planning and automatic control
of autonomous agents such as space vehicles, stations and
robots with cooperative and opposing interests functioning in
a complex, hazardous environment. Reasoning about such complex
systems should be done automatically, in a timely manner, and
often in a real time. Moreover, there are no highly-skilled
human experts in these fields ready to substitute for robots
(on a virtual model) or transfer their knowledge to them.
There is no grand-master in robot control, although, of
course, the knowledge of existing experts in this field should
not be neglected - it is even more valuable. It is very
important to study human expert reasoning about similar
complex systems in the areas where the results are successful,
in order to discover the keys to success, and then apply and
adopt these keys to the new, as yet, unsolved problems. Then,
we meet a hard question. What language tools do we have for
the adequate representation of human expert skills? An
application of such language to the area of successful results
achieved by the human expert should yield a formal, domain
independent knowledge ready to be transferred to different
areas. Neither natural nor programming languages satisfy our
goal. The first are informal and ambiguous, while the second
are usually detailed, lower-level tools. Actually, we have to
learn how we can formally represent, generate, and investigate
a mathematical model based on the abstract images extracted
from the expert vision of the problem.
There have been many attempts to find the optimal (suboptimal)
operation for real-world complex systems. One of the basic
ideas is to decrease the dimension of the real-world system
following the approach of a human expert in a certain field,
by breaking the system into smaller subsystems. These ideas
have been implemented for many problems with varying degrees
of success. Implementations based on the formal theories of
linear and nonlinear planning meet hard efficiency problems.
An efficient planner requires an intensive use of heuristic
knowledge. On the other hand, a pure heuristic implementation
is hardly reproduced for other problem domains. There is no
general constructive approach to such implementations. Each
new problem should be carefully studied and previous
experience usually can not be applied. Basically, we can not
answer the question: what are the formal properties of human
heuristics which drove us to a successful hierarchy of
subsystems for a given problem and how we can apply the same
ideas in a different problem domain.
In the 1960's a formal syntactic approach to the investigation
of properties of natural language resulted in the fast
development of a theory of formal languages by Chomsky,
Ginsburg, and others. This development provided an interesting
opportunity for dissemination of this approach to different
areas. In particular, there came an idea of analogous
linguistic representation of images. This idea was
successfully developed into syntactic methods of pattern
recognition by Fu, Narasimhan, and Pavlidis, and picture
description languages by Shaw, Feder, Phaltz and Rosenfeld.
Searching for the adequate mathematical tools formalizing
human heuristics of dynamic hierarchy, we have transformed the
idea of linguistic representation of complex real-world and
artificial images into the idea of similar representation of
complex hierarchical systems [2]. However, the appropriate
languages should possess more sophisticated attributes than
languages usually used for pattern description. The origin of
such languages can be traced back to the research on
programmed attribute grammars by Knuth, Rozenkrantz, and
Volchenkov.
A mathematical environment (a "glue") for the formal
implementation of this approach was developed following the
theories of formal problem solving and planning by Nilsson,
Fikes, Sacerdoti, McCarthy, Hayes, and others based on first
order predicate calculus.
To show the power of the linguistic approach it is important
that the chosen model of the heuristic hierarchical system be
sufficiently complex, poorly formalized, and have successful
applications in different areas. Such a model was developed by
Botvinnik, Stilman, and others, and successfully applied to
scheduling, planning, and computer chess [1].
In order to discover the inner properties of human expert
heuristics, which were successful in a certain class of
complex control systems, we develop a formal theory, the
so-called Linguistic Geometry. This research includes the
development of syntactic tools for knowledge representation
and reasoning about large-scale hierarchical complex systems.
It relies on the formalization of search heuristics, which
allow to decompose complex system into the hierarchy of
subsystems, and thus solve intractable problems reducing the
search. These hierarchical images were extracted from the
expert vision of the problem. The hierarchy of subsystems is
represented as a hierarchy of formal attribute languages. The
lowest level language, the Language of Trajectories, is the
formalization of the set of paths between the locations of
elements of the system. Subsets of paths and elements unified
in achieving (opposing) local goals form the next level
languages, the Family of Trajectory Network Languages. The
Language of Zones, a member of this family, is applicable to
military control systems. The highest level of the hierarchy
of languages is the Family of Languages of Searches. It
includes as members all the well known search algorithms,
e.g., alpha-beta search, dynamic programming, etc. The
Language of Translations, representing the search for the
optimal operation in the hierarchy of subsystems, is a member
of the same Family.
The details of generating grammars, actual generation of the
hierarchy of languages, and examples of applications to
robotics, aerospace combat, scheduling will be considered in
the tutorial.
The development of Linguistic Geometry will benefit a variety
of applied and theoretical areas including strategic planning
and automatic control of intelligent autonomous systems
functioning in hazardous dynamic environment, different
non-military control and planning systems.
Return to Program Overview
1. An Efficient Dual Simplex Optimizer for Generalized Networks
Jeffery L. Kennington (Southern Methodist University) and Riad A.
K. Mohamed (Sabre Decision Technologies)
This manuscript describes a specialization of the dual simplex
algorithm for the generalized network problem. We use a dual
two phase method along with efficient dual pricing schemes and
specialized routines for the dual ratio test. In comparison
with CPLEX 3.0 on a set of ten benchmark problems, we found
that our specialized dual code performed 20 times faster than
the best CPLEX optimizer. Problems having 10 to 20 thousand
arcs are routinely solved in under 10 seconds on a 60 MHz
DECStation 5000/260 with both our rapid primal and dual
generalized network optimizers.
2. Optimality Conditions and Solution Procedures for Nondegenerate
Dual Response Systems
John Semple (University of Texas at Arlington)
This paper investigates the dual response problem in the case
where the response functions are nonconvex (nonconcave)
quadratics and the independent variables satisfy a radial
bound. The paper begins by establishing sufficient conditions
for a global optimum. It is then demonstrated that the
sufficient conditions may not hold if the problem is
"degenerate." A notion of stability is introduced to identify
the unusual case where the constraint surfaces barely
intersect. In the typical case, where the problem is
nondegenerate and stable, the sufficient conditions are shown
to hold at a unique global optimum. Under the same
assumptions, a specialized algorithm is developed to
efficiently locate this optimum in a finite number of
iterations. This algorithm is extremely easy to implement from
the standpoint of code development. When applied to a
well-documented dual response problem from quality control,
the specialized algorithm is shown to be more reliable than an
established general purpose non-linear optimization technique.
3. Resolving Inconsistency in Infeasible Linear Programmes
Mehrdad Tamiz and Simon J. Mardle (University of Portsmouth)
The detection of irreducibly inconsistent subsystems (IIS) of
constraints within an infeasible linear programme (LP) has
become a well-established approach in resolving any
infeasibilities present in such an infeasible LP. It has been
shown that an infeasible LP has at least one IIS, and in
reality may contain many overlapping IIS and/or distinct IIS.
In this talk, our method (GPIIS) which guarantees to find an
IIS in any infeasible LP will be described together with
strategies for detecting more than one IIS. Finding a set of
IIS containing the maximum number of distinct IIS is given the
highest priority. With this we construct a minimal set of
constraints which can be relaxed or deleted to render the
original LP feasible. Computational results will be presented
for the approaches discussed.
4. Generation of Pareto Solutions by Entropy-Based Methods
A.M. Sultan and A.B. Templeman (Liverpool University)
In recent years the Maximum Entropy Principle has been used to
develop new approaches to various classes of optimization
problems such as those of scalar non-linear constrained
optimization, vector and minimax optimization. In this paper,
two new entropy-based approaches are developed, proved and
applied to the problem of generating Pareto optimal solution
sets for general multi-criteria optimization problems.
The solution algorithms are applied to several test problems.
This paper will appear as part of a new book that is currently
under publication in England.
Return to Program Overview
Chair: Amy Puelz (Southern Methodist University)
1. Generator of Optimization-Based Decision Support Systems
Francisco Baranao, Juan-Carlos Ferrer, and Sergio Maturana
(Universidad Catolica de Chile)
Although Operations Research methodologies have been applied
to solve a wide variety of problems, there have been
significant practical difficulties in their implementation. In
order to make OR methodologies easier to use in practice, it
is necessary to have better implementation tools to build
Optimization-based Decision Support Systems, which are
delivery systems for these methodologies. This is particularly
true with respect to the graphical user interface which is a
large part of the implementation effort of these systems.
In this paper we discuss the general design of a generator of
optimization-based decision support systems which will be able
to automate several phases of the process of constructing such
systems. This will drastically reduce both the cost and the
time required to build these DSS compared to the traditional
approach.
This generator is being implemented in an ongoing project
which is using SML as a basis for generating
optimization-based DSSs in the context of production and
distribution applications. The main idea is to be able to
integrate a model specification with a database, a solver, and
a graphical user interface quickly and with relatively little
effort.
The generator should be able to perform the following tasks:
generate the database for storing the instantiating data,
generate the GUI, generate ad-hoc report, provide on-line
help and documentation, and select and integrate an
appropriate solver.
2. Building an Electronic Performance Support System to Assist
Students in Learning about Parallel Computing, Expert Systems,
Induction and Solution Methods for Linear Programming
H.C. De Kock and S.A. Du Plessis (University of Stellenbosch,
South Africa)
The authors have developed a model for an intelligent
electronic performance support, coaching and testing system
and has applied it to the domain of mathematical programming.
The resulting tutoring system is able to function in any one
of four possible modes, namely coaching, electronic
performance support, computerized adaptive testing and
accelerated learning. In another project they developed and
compared different algorithms for the solution of linear
programming problems and made these solution method
s available to be used to solve large linear programs. An
artificial decision support system (ADSS) was then developed
to help a naive problem solver make an intelligent choice
regarding the most effective solution method that is
applicable to his specific problem (from the ones made
available). In this paper the electronic performance support
mode of the intelligent tutor is applied to the domain of the
ADSS. The goal of the resulting system is to create a dynamic
learning environment in which the user is taught how to select
the most appropriate solution method for his situation, and to
assist students in learning about linear programming, parallel
algorithms, induction and expert systems, the building blocks
of the ADSS. Different tools were developed to implement it,
including a point-and-query interface, a computerized adaptive
testing procedure, a computerized problem solver, a generic
questioning module and a computer mind mapping facility.
3. On Using SML as a Basis for Implementing Optimization-Based
Decision Support Systems
Juan-Carlos Ferrer, Francisco Baranao, and Sergio Maturana
(Universidad Catolica de Chile)
Structured Modeling was developed by Arthur Geoffrion to
improve model-based work. SML (Structured Modeling Language)
was the first language to support this Framework and has many
important features for developing modeling systems, such as,
extensive error-checking, detailed semantics connections among
model parts, automatic generation of relational data table
designs for model instance data, complete independence between
model structure and instantiating data, and complete
independence between models and solvers, among others.
There is an ongoing project which is using SML as a basis for
implementing optimization-based DSSs in the context of
production and distribution applications. The main idea is to
be able to integrate a model specification with a database, a
solver, and a graphical user interface quickly and with
relatively little effort.
This approach relies heavily on the design of SML as the model
specification language for representing the different types of
problems, and plays a central role in the design of the
optimization-based DSS that are being implemented. This paper
reports on the suitability of SML, and Structured Modeling as
the underlying Framework, in this role. Based on our
experience, we analyze the potential of SML for model
specification, graphical user interface specification,
database design, reports specification, documentation, and
solver selection and integration.
Return to Program Overview
1. Inspection Problems Arising in the Transportation of Hazardous
Materials
Daniel J. Rosenkrantz, Giri K. Tayi, and S. S. Ravi (University
at Albany - State University of New York)
As the volume of hazardous materials being transported
around the world increases steadily, determination of the
shipping routes and selection of inspection sites enroute to
the destination becomes an important task. In transporting
such materials, carriers need to comply with several
governmental regulations. The primary purpose of inspection
is to ensure that the materials are in continuous compliance
with the regulations and to rectify violations if any.
Inspection facilities may not be available at all sites, and
the cost of inspection could vary from site to site.
In this paper, we formulate two broad types of inspection
problems in transporting hazardous materials. In these
problems, we propose a novel computational method for
estimating the penalty associated with a failure during
transit. The first type of problems involve choosing
inspection sites given the route. The second type deals with
simultaneous selection of a route and inspection stations
along that route. Under each type, several problem
formulations are proposed. These capture the nature of
inspection and practical constraints such as inspection
budget, number of inspection stations, limit on the distance
between two consecutive inspection stations, limit on the
maximum penalty incurred, etc. We analyze each of these
problems and develop results that characterize their
computational complexity. Based on this analysis, efficient
algorithms are developed for some problems while others are
shown to be NP-hard but solvable in pseudo-polynomial time.
These algorithms utilize a dynamic programming approach in
conjunction with suitable data structures.
2. A Dynamic Programming Approach to Transportation Mode Selection
R.G. Kasilingam and V.R. Beeram (University of Arkansas)
The selection of mode or a combination of modes is one of the
important decisions in transportation planning. Mode selection
decisions have a significant impact on the competitiveness of
a firm, as it dictates the transportation lead time,
transportation cost, and the utilization of key transportation
and material handling resources. Mode selection decisions are
complicated by the fact that various criteria must be
considered in the decision making process. Most research on
mode selection deals with the costs of transportation. The
cost of transferring from one mode to another at a city, which
greatly depend upon the incoming mode is largely ignored.
The problem addressed can be stated as follows: Transportation
of a shipment involves movement through several segments,
where each segment is a city pair. Given the known sequence
of segments (or route), and the alternative modes available
for each segment, determine the best transportation mode for
each segment considering linear transportation costs and
intermodal transfer costs. In this paper, we present a binary
integer programming model to select the optimal combination of
transportation modes from origin to destination based on
transportation costs and intermodal transfer costs.
Assuming n segments and m alternatives for each segment, the
number of alternative modal combinations is m^n. Even for a
small size problem, the binary integer programming model will
result in a large number of variables, making it intractable.
A backward recursive procedure based on dynamic programming
is presented to solve the problem. The model and the
procedure are illustrated using a numerical example. Possible
extensions of the model and the solution procedure to
simultaneously determine the best routing and best modal
combination are also presented.
3. Energy Generators Expansion Capacity Planning Under Uncertainty
L.F. Escudero (UITESA grupo IBERDROLA and DEIO, Universidad
Complutense, Madrid, Spain)
This paper presents a modelling framework for expansion
planning of power generation systems under several types of
uncertainty, namely investment and operation costs, energy
demand, economic environment, generation availability and book
life. A deterministic treatment of the problem provides
unsatisfactory results due to the high variability of the
uncertain data.
In contrast to traditional approaches, we use scenarios to
characterize the uncertainty. Solutions are obtained for each
scenario and then, these individual solutions are aggregated
to yield and implementable non-anticipative generation
expansion planning that either minimizes the regret of wrong
decisions, or minimizes the expected cost of the expansion
planned. Our approach results in a huge 0-1 mixed separable
nonlinear model with generation expansion models for each
scenario and scenario group plus coupling constraints. The
size of the problem and the structure of the constraints are
amenable to the use of decomposition techniques and parallel
computation tools. Some computational experience will be
reported.
Return to Program Overview