iDocSlide.Com

Free Online Documents. Like!

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Description

A knowledge-based system for cash management with management science expertise

Tags

Transcript

An intelligent modeling system for generalized network flow problems: With application to planning formultinational firms
Richard D. McBride and Daniel E. O’Leary
School of Business, University of Southern California, Los Angeles, CA 90089-1421, USA
E-mail: mcbride@sba2.usc.edu; oleary@rcf.usc.edu This paper presents a discussion of the
G
eneralized
N
etwork
S
ystem (GNS), a systemthat captures knowledge about generalized network flow problems, in order to help usersformulate, solve and interpret generalized network flow problems. Although previousresearchers have built intelligent systems that incorporate knowledge about linear program-ming, this system includes more specific knowledge about generalized network flow prob-lems. GNS is illustrated using it in a setting that requires international financial andproduction planning. In particular, these multinational planners need to be able to plan andreplan rapidly. In addition, they need to be able to model complex events and organizationstructures. For example, multinational planners need to be able to plan for production inmultiple countries and repatriatization of funds. GNS allows users to meet these needs.
1
.Introduction
Within the artificial intelligence (AI) community there is the view that (Winston[21, p.2]) “One central goal of artificial intelligence is to make computers moreuseful.” Although operations research (OR) tools can be used to guide the user tobetter solutions than other approaches, researchers have unfortunately found few usersof the portfolio of OR techniques, including mathematical programming (e.g., [11]).As a result, there has been substantial interest in the relationship between AI andOR, in particular, mathematical programming (MP). Researchers are interested in thequestion, “Can AI make OR useful (and used)?” Accordingly, a number of specialissues of journals, such as
Annals of Operations Research
, have focused on the inte-gration of AI and MP. National and international meetings (e.g., American Associationfor Artificial Intelligence, 1992) have had special sessions and workshops relating tothe topic.
© J.C. Baltzer AG, Science PublishersAnnals of Operations Research 75(1997)355–372355
Research integrating AI and MP has concentrated on building knowledge of MPinto systems to solve MP problems. Generally, this has meant knowledge about
linear programming problems
and their structures. Similarly, the system discussed in thispaper uses knowledge about
generalized network flow
problems in order to exploitour knowledge of the underlying structure of those problems to facilitate problemformulation and solution. It does this in the context of an example of financial plan-ning for a multinational firm. Concentrating on specific knowledge about generalizednetwork flow problems is consistent with previous literature integrating AI and MP,as discussed below. Further, focusing on specific structure has enabled the solution of generalized network flow problems using algorithms that are much faster than solvingthose problems as general linear programming problems (e.g., [5]).
1.1.Application: Planning for multinational firms
Multinational firms need to be able to plan where to produce goods and when torepatriate funds earned in other countries. Multinational firms need to be able to planrapidly because currency values can fluctuate rapidly. In addition, multinational firmsface a complex assortment of changing currency and production situations. As a result,users need robust and flexible planning tools to help them adapt to numerous situ-ations.Firms do not have time to have a planner contact an OR expert, meet for lunch,talk about the planning problem, have the OR expert work for the next six monthsconstructing a model, and then have the planner ask the OR expert to solve the prob-lem one day and then the next day solve another version of the problem. Instead, thereis a need for a tool that allows firms to rapidly model complex integrated multinationalcorporate structures and international currency situations.
1.2.This paper
As a result, this paper presents an intelligent system called the
G
eneralized
N
etwork
S
ystem (GNS), that can be used to formulate, solve and interpret generalizednetwork flow problems. Because the system is easy to use and facilitates real-timeresponse, it can facilitate planning and replanning. In the example presented in thispaper, GNS helps the user generate an integrated production and currency valuationmodel of the firm. The system then formulates that model as a generalized network flow problem. GNS tests the feasibility of the model and then solves the model,and presents the results to the user. The system can be used for replanning, sinceparameters can be easily changed and nodes and arcs can be easily added or deleted.This paper proceeds as follows. Section 2 briefly reviews some of the previousliterature on integrating AI and MP. Section 3 provides a brief background of theuse of generalized network models for planning. Section 4 reviews the knowledgeembedded in GNS. Section 5 illustrates the use of the system. Section 6 briefly sum-marizes the paper and discusses some extensions.
R.D. McBride, D.E. O’Leary
An intelligent modeling system
356
2.Previous research integrating mathematical programming and artificialintelligence
Researchers have developed integrated AI and MP systems for general analysisof linear programs, within the context of a number of business situations.
2.1.General systems
The literature contains three forms of general integration of AI and MP, includingsystems that: formulate problems for solution by a linear programming algorithm;determine which algorithm should be used to solve a particular problem; and interpretand debug linear programming models. These systems contain substantial knowledgeabout linear programming models.A sequence of papers, including Murphy and Stohr [18] and Ma et al. [16],described an intelligent system, called LPFORM, that formulated linear programs forusers. LPFORM supports three classes of inputs: row orientation, activity orientationand transportation structures used to define different objects of interests, within thecontext of linear programming.Schittkowski [19] developed EMP, which has the ability to choose a suitablelinear or nonlinear programming algorithm to solve the program. EMP then writes aF
OTRAN
program to solve the particular problem under consideration. That program isthen executed and the results are stored in a database for further analysis.Perhaps the first research that built knowledge into mathematical programmingsystems was Greenberg’s [12,13] work on debugging and explaining linear programs.Greenberg’s [13, p.333] ANALYZE is an “English language discourse model toexplain linear programming models and their solutions”. ANALYZE detects redundantconstraints, infeasibility and other issues.
2.2.Applications
The primary focus of applications to date has been on production planning, withlittle emphasis on financial planning or international financial planning problems.Instead, researchers have primarily focused on solving production-based problems.Binbasioglu and Jarke [5] developed a model that helps the user formulate a linearprogramming example from scratch to solve a production scheduling problem. Leeand Lee [15] developed a system designed to consider short and long term effects of the sales mix. The system solves a linear programming problem and then analyzes theoutput to determine if the solution satisfies the long-run interests of the company.Takahara et al. [20] developed a platform for constructing intelligent systems using ahierarchical connection of a numeric solver and a nonnumeric evaluator, which evalu-ates the solution heuristically. They illustrate their system using an example drawnfrom the job assignment problem.
R.D. McBride, D.E. O’Leary
An intelligent modeling system
357
There has been limited research on integrating mathematical programming andartificial intelligence to solve financial problems. Dempster and Ireland [9,10]developed a decision support system that integrates stochastic programming into anintelligent system for supporting borrowing planning for a public utility. Once outputis received from the programming model, it is refined by the system based on rulesdeveloped jointly with an experienced corporate treasurer and professional under-writers. Back [1,2] and Back and Back [3] describe an expert system for assisting inthe development of financial statements, with particular interest in understanding theimpact of income smoothing. A mathematical program, embedded in an expert system,generates the recommended solution to the user.
2.3.Contribution of our system
Previous researchers have focused virtually exclusively on linear programmingproblems. As a result, the system discussed in this paper is concerned with usingknowledge about generalized network flow problems to build an intelligent system tohelp formulate, ensure feasibility and interpret results. It does this in the context of international financial planning, an application area that also has received limitedattention in the integration of AI and MP.
3.Generalized network flow problems: Models of multinational firms
This section summarizes some of the relevant previous research on network models and their use in planning for multinational firms. Then, the basic generalizednetwork flow model used in this paper is generated.
3.1.Generalized networks
Although the linear programming algorithms can be used to solve virtually anylinear program, there are computational advantages to developing algorithms forspecific types of problems. A particularly computationally efficient algorithm hasbeen developed for generalized network flow problems by Brown and McBride [5].In addition, McBride [17] developed a computationally efficient approach for thesolution of embedded networks. Those algorithms can solve even very large prob-lems rapidly. Solution of those generalized network flow problems is speeded up byexploiting the unique structure of the problems.
3.2.Models of multinational firms and mathematical formulation
Perhaps the first network models for multinational firms were developed byCrum [6], who modeled the process of planning cash conversion by multinationalcorporations as a generalized network flow problem. The formulation presented in
R.D. McBride, D.E. O’Leary
An intelligent modeling system
358
this section comes from Crum et al. [7]. This example problem is chosen because itillustrates the importance of having tools available to easily formulate and solvegeneralized network flow problems and to illustrate system use.Let
x
ij
be the arc flow from node
i
to node
j
. Let
L
ij
be the lower bound on theflow on that arc. Let
U
ij
be the upper bound on the flow on that arc. Let
c
ij
be the costof shipping one unit on arc (
i
,
j
). Let
p
ij
be the multiplier on the flow of one unit onarc (
i,j
). Thus,
p
ij
∗
x
ij
is the amount of flow entering node
j
from node
i
. Let
b
i
bethe supply or demand at node
i
, where supply is denoted as a positive quantity anddemand is a negative quantity.Each arc in a generalized network represents a variable and each node representsan equation. Let
A
be the set of feasible arcs in a network. The general mathematicalprogram can be written asDifferent nodes would be used to represent currency and production resourcesin both the parent and each of the subsidiaries. Arcs would be used to represent directtransfer of cash and product to different nodes.
3.3.Availability of data
The model assumes that up to four primary types of conversion data and pro-cesses are available. First, there can be linear data that relates to the cost of convertingforeign currency to foreign product. Second, there can be linear data that relates tothe cost of converting domestic currency to domestic product. Third, there can belinear data that relates conversion of foreign currency to domestic currency (or con-versely). Fourth, there can be conversion of foreign product to domestic product (orconversely).Associated with each type of conversion there is a per unit cost. In addition,there can be either or both lower and upper bounds on the amount of the conversions.
3.4.Need for GNS in multinational corporations
However, the use of generalized networks to solve multinational planning prob-lems has been limited by the availability of approaches to facilitate the formulation of problems. Generally, in order to use the approaches of Brown and McBride [5] andMcBride [17] requires user familiarity with the basic algorithms and substantialproblem formulation work.
minimizesubject to
( , )( , ) ( , )
, , , ,, ( , ) .
i jij iji jiji jij ij iij ij ij
c x x p x b i m L x U i j
∈∈ ∈
∑∑ ∑
∗− ∗ = = …≤ ≤ ≤
∈
AA A
A
10
R.D. McBride, D.E. O’Leary
An intelligent modeling system
359

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x