Transcript Module 1 (ppt file) - Department of Computer Science

AEM412
Computational Methods for
Management and Economics
Carla P. Gomes
Module 1
Introduction
Overview of this Lecture
• Course Administration
• Course Themes, Goals, and Syllabus
• Background on Mathematical Programming
• The Impact of Information Technology on
Business Practice
Course Administration
AEM412 - Introduction to
Mathematical Programming
Lectures: Tuesday and Thursday - 11:40 - 12:55
Location: WN 245
Lecturer: Prof. Gomes
Office: 448 Warren Hall
Phone: 255 1679 or 255 9189
Email: [email protected] or [email protected]
TA: Vivian Eliza Hoffmann ([email protected])
Administrative Assistant: Dawn Vail ([email protected])
147 Warren Hall, 254-6761
Web Site: http://courseinfo.cit.cornell.edu/courses/aem412/
Office Hours
• Prof. Gomes
Monday and Wednesday: 3:00p.m – 4:00 p.m.
• TA – Vivian Hoffmann
Tuesday (WN360) and Wednesday (WN201):
1:30 p.m – 2:30 p.m.
Grades
Midterm
(15%)
Homework
(35%)
Participation
(5%)
Final
(45%)
Note: The lowest homework grade will be dropped before the
final grade is computed.
Required Textbook
Introduction to Operations Research by
Frederick S. Hillier and
Gerald. J. Lieberman,
7th Edition
Overview of this Lecture
• Course Administration
• Course Themes, Goals, and Syllabus
• Background on Mathematical Programming
• The Impact of Information Technology on
Business Practice
Course Themes, Goals, and
Syllabus
What’s Mathematical Programming (MP)?
Main focus: Optimization
Optimization is pervasive in business and economics and
almost all aspects of human endeavor, including science and
engineering. Optimization is everywhere:
part of our language and the way we think!
–Firms want to maximize value to shareholders
–People want to make the best choices
–We want the highest quality at the lowest price
–In games, we want the best strategy
–We want to optimize the use of our time,
–etc
Optimization
•
•
•
•
•
•
•
•
•
•
Financial planning
Marketing
E-business
Telecommunications
Manufacturing
Operations Management
Production Planning
Transportation Planning
System Design
Health Care
Some of the themes of 412
• Optimization!!!
• Models, Models, Models
(insights not numbers)
•
•
•
•
Applications in business and economics
Algorithms, Algorithms, Algorithms
Efficient Algorithms --- whenever possible
Importance of factoring in computational issues in
business and economic applications: computational
limits and intractability
What’s Mathematical Programming?
•Very broad discipline covering a variety of Optimization
topics such as:
– Linear Programming
–Non-linear Programming
– Advanced Linear Programming
Models
– Network Models
– Integer Programming
–Decision Making under Uncertainty
– Dynamic Programming
– Heuristic techniques
• Simulated Annealing
• Genetic Algorithms
• Tabu Search
• Neural Networks
–Decision Making with Multiple
Objectives
–Game Theory
–etc
Syllabus 412
• Linear Programming
– Introduction
– Simplex/Revised Simplex
– Duality and Sensitivity Analysis
– Other LP Algorithms
• Network Models
– Transportation Problems
– Assignment Problems
– Network Optimization Models
• Special Topics(*)
– Integer Programming
– Dynamic Programming
– Heuristic techniques
•
•
•
•
Simulated Annealing
Genetic Algorithms
Tabu Search
Neural Networks
– Computational complexity(*)
(*)time permitting
Goals in 412
– Present a variety of models, algorithms, and tools for
optimization
– Illustrate applications in business and economics, and
other fields.
– Prepare students to recognize opportunities for
mathematical optimization as they arise
– Prepare students to be aware of computational complexity
issues: importance of using efficient algorithms whenever
possible and the limits of computation that can affect the
validity of business and economic models.
Background on Mathematical
Programming
Origins of Operations Research (OR)
• The roots of OR can be traced back many decades
and even centuries (Newton, Euler, Bernoulli,
Bayes, Lagrange, etc).
• Beginning of the activity called Operations
Research --- attributed to the military services
early in the World War II (1937).
– Need to allocate scarce resources to the various military
operations in an effective manner.
– The British first and then the U.S military management called upon
a large number of scientists to apply a scientific approach to
dealing with several military problems
• End of war – scientists understood that OR could
be applied outside the military as well.
• The industrial boom following the war led to an
increasing complexity and specialization of
organizations  scientific management
techniques became more and more crucial.
• By the early 1950s, OR techniques were being
applied to a variety of organizations in business,
industry, and government.
Impact of
Operations
Research
Key Factors for Rapid Growth of
OR
• Substantial progress was made early in
improving the techniques in OR
– Simplex, Dynamic Programming, Integer
Programming, Inventory Theory, Queing
Theory, etc
• Computer revolution - 1980s the PC further
boosted this trend.
Timeline
Operations Research Over the Years
• 1947
– Project Scoop (Scientific Computation of Optimum
Programs) with George Dantzig and others.
Developed the simplex method for linear programs.
• 1950's
– Lots of excitement, mathematical developments,
queuing theory, mathematical programming.
cf. A.I. in the 1960's
• 1960's
– More excitement, more development and grand plans.
cf. A.I. in the 1980's.
Source: J. Orlin (MIT) 2003
Operations Research Over the Years
• 1970's
– Disappointment, and a settling down. NPcompleteness. More realistic expectations.
• 1980's
– Widespread availability of personal computers.
Increasingly easy access to data. Widespread
willingness of managers to use models.
• 1990's
– Improved use of O.R. systems.
Further inroads of O.R. technology, e.g., optimization
and simulation add-ins to spreadsheets, modeling
languages, large scale optimization. More intermixing
of A.I. and O.R.
Operations Research in the 00’s
• LOTS of opportunities for OR as a field
• Data, data, data
– E-business data (click stream, purchases, other transactional
data, E-mail and more)
– The human genome project and its outgrowth
• Need for more automated decision making
• Need for increased coordination for efficient use of resources
(Supply chain management)
The Impact of Information
Technology on Business Practice
Advances in information technology are
increasingly impacting on business and
business practices.
Exciting new opportunities (and some risks).
Examples of applications
Driving Force
Exponential Growth
a) Compute power
b) Data storage
c) Networking
Combined with algorithmic advances
(software)
Compute power: Doubling every 18 months
100,000,000
transistors
per processor
4,000 transistors
per processor
How much can be stored in one Terabyte?
Yr ’06, 1 Terabyte for $200.
Storage
for
$200
video
1
Gigabyte/hour
1000 hours
scanned
color
images
1 Megabyte
each
1 million
images
text pages
3300
bytes/page
300 million
pages (Library
of Congress)
Wal-Mart customer data: 200 terabyte --- daily data mining for customer trends
Microsoft already working on a PC where nothing is ever deleted.
You will have a personal Google on your PC.
The Network: The Internet
This new level of connectivity
allows for much
faster, and more substantive
interactions between
companies/suppliers/customers
(e.g. electronic markets)
1981 --- 200 computers
1990 --- 300,000
1995 --- 6.5M
1997 --- 25M
2002 --- 300M
Examples of business impact
1) Supply-chain-management
2) Electronic markets
3) Beyond traditional scheduling application
Dell premier example of integration of information
technology into the business model.
Direct business-to-consumer model
• 1984 -- Michael Dell founds Dell
• 1996 – Dell starts selling computers via Internet at www.dell.com
• 1999 – "E-Support Direct from Dell" online technical support
•
• 2001 – Company sales via Internet exceed $40 M per day
Dell ranks No 1 in global market share
• 2003 – Revenue – $32.1 Billion
Direct business-to-consumer model
Power of Virtual Integration
Supply Chain Strategy and Processes
Reporting
Solution
DELL manages relationships with over
80% of suppliers through the Internet.
Report Users
Legacy
Systems
Over half of Dell customers use Webenabled support (over 40,000 Premier
Pages-10,000 in Europe).
Factory
Planner
Users
Factory
Planner
Supply
Logistics
Center
Collaboration
Suppliers
Supply
Chain
Planning
Supply Chain
Planning Users
Supplier
Collaboration
Internet
Real-time Access
and Transactions
Supply Hubs
Product configuration tools
Efficient supply chain:
Online design of made-to-order system.
Innovative product design,
Constraint-based reasoning tools (knowledge
about allowable system configurations)
An Internet order-taking process,
Customer-to-Knowledge
An innovative assembly system,
Customers search Dell databases
Close cooperation with suppliers.
Knowledge content for typical responses
Personalization tools
Optimization is everywhere
Electronic Markets
Combinatorial Auctions
Why Combinatorial Auctions?
More expressive power to bidders
In combinatorial auctions bidders have preferences not just for particular
items but for sets or bundles of Items due because of complementarities
or substitution effects.
Example Bids:
Airport time slots
[(take-off right in NYC @ time slot X ) AND
(landing right in LAX @ time slot y)] for $9,750.00
Delivery routes (“lanes”)
[(NYC - Miami ) AND
[((Miami – Philadelphia) AND (Philadelphia – NYC)) OR
((Miami – Washington) AND (Washington – NYC))]] for $700.00
Procurement Transportation Services on the web.
OPTIBID - software for combinatorial auctions
Managing over 100,000 trucks a day (June 2002),
>$8 billion worth of transportation services.
• FCC auctions spectrum licenses
( geographic regions and various frequency bands).
•Raised billions of dollars
•Currently licenses are sold in separate auctions
•USA Congress mandated that the next spectrum
auction be made combinatorial.
FCC Auction #31 700 MHz
Winner Determination Problem $12e6 + $16e6 +$8e6 =
Choose among a set of bids such that:
• Revenue to the FCC is maximized
$22e6 + $8e6 =
• Each license is awarded no more than once
$30e6
Bid
1
2
3
4
5
6
7
8
Bid amt.
$22e6
$12e6
$30e6
$16e6
$8e6
$11e6
$10e6
$7e6
Package
ABD
B
ABC
AD
C
BC
A
Example: 4 licenses, 8 bids
8
Max
x
A
x1
B
x1
+ x3
+ x2
 BidAmt
x1
b
D Hard
Computational
Problem 
 xb
b 1
+ x4
+ x7
+ x3
x3
C
D
$36e6
+ x5
<=
1
+ x6
<=
1
+ x6
<=
1
<=
1
+ x4
xb  0,1
+ x8
for all bids
(source: Hoffman)
Combinatorial Auctions cont.
• There exists a combinatorial auction mechanism
(“Generalized Vickrey Auction”), which guarantees
that the best each bidder can do is bid its true valuation
for each bundle of items. (“Truth revealing”).
• However, finding the optimal allocation to the bids is a
hard computational problem. No guarantees that an
optimal solution can be found in reasonable time.
• What about a near-optimal solution? Does this
matter?
• Yes! Problem: if the auctioneer cannot compute the
optimal allocation, no guarantee for truthful bidding.
Beyond Traditional Scheduling
Applications
Enforcing Safety Constraints
Nuclear Power Plant Outage Management
[ Gomes et al, 1996, 1997, 1998 ]
ACTIVITY
SCHEDULE
Activity Name
EST
LST
Duration
Predecessors
impacts
impacts
ROME LABORATORY OUTAGE MANAGER (ROMAN)
Parameters
Parameters Load
Load
RunRun Gantt
Gantt
Charts
Charts Utilities
Utilities Exit
Exit
Name: D21-1 Affects: ACPLOSS DIV1
Predecessors
EST: 65
LST: 65 DURATION: 15 START: 65 FINISH: 80 PECO
ROME LABORATORY OUTAGE MANAGER (ROMAN)
Parameters
Parameters Load
Load
RunRun Gantt
Gantt
Charts
Charts Utilities
Utilities ExitExit
Name: D21-1 Affects: ACPLOSS DIV1
Predecessors
EST: 65
LST: 65 DURATION: 15 START: 65 FINISH: 80 PECO
0
10
20
30
40
50
60
80
90
100
110
120
D23-3 70
RHRB-1
D23-2
D21BUS-1
DIV4DC-1
0
10
20
30
40
50
60
70
80
90
100
110
RHR
D21-1
A-1
D23-3
RHRB-1
D23-2
D21BUS-1
DIV4DC-1
RHRA-1
D21-1
impacts
ROME LABORATORY OUTAGE MANAGER (ROMAN)
STATE-Of-PLANT
Parameters
Parameters Load
Load
RunRun Gantt
Gantt
Charts
Charts Utilities
Utilities Exit
Exit
31 - 45: ACPOWER? 0 NUM-UNAV-RESS 1
UNAV-RES-MAP (DIV2 D24BUS-3 D24-2 D24-1) (ACPLOSS D24BUS-3 D24-2 D24-1)
LIST-AV-RESS (DIV1 DIV3 DIV4 SU10 SU20)
0
10
20
30
40
50
60
70
80
90
100
110
AC-POWER Status
AC Power
DIV1
DIV2
DIV3
DIV4
SU10
SU20
Given:
•activities for refueling and maintenance
•resources
•technological constraints
Find a schedule that minimizes the
duration of the outage while safely
performing all the activities
(up to 45,000 activities).
Cost of shutdown - $1M per day.
Main risk
The residual heat produced by the
nuclear materials can melt the
fuel and breach the reactor nvessel
Examples of Monitored Safety Systems
•ac power control system
•primary containment system
•shutdown cooling system
Limitations of Traditional Approaches
Rely heavily on manual procedures;
Current procedures – PERT/CPM
Outage Risk Assessment Methodology,
simulation performed to assess
the risks inherent to a schedule.
Nuclear Power Plant Outage Management
Example of decision tree for a
safety function for AC-Power
Activity with
AC Power loss
Potential?
no
2
Offsite
sources
available
yes
Operable
emergency
Safeguard
bus
Operable
emergency
Safeguard
bus
1
(…)
ROME LABORATORY OUTAGE MANAGER (ROMAN)
Parameters
Parameters Load
Load
Run Run GanttGantt
Charts
ChartsUtilities
Utilities ExitExit
Name: D21-1 Affects: ACPLOSS DIV1
Predecessors
EST: 65
LST: 65 DURATION: 15 START: 65 FINISH: 80 PECO
0
10
20
30
40
50
60
70
80
90
100
110
>3
2
1
0
Safety
threshold
>3
2
1
Time
Roman extends the functionality of
traditional project management tools
D23-3
RHRB-1
• It
incorporates the technological constraints,
automatically enforcing safety constraints
D23-2
D21BUS-1
DIV4DC-1
RHRA-1
D21-1
ROME LABORATORY OUTAGE MANAGER (ROMAN)
Parameters
Parameters Load
Load
Run Run GanttGantt
Charts
ChartsUtilities
Utilities ExitExit
31 - 45: ACPOWER? 0 NUM-UNAV-RESS 1
UNAV-RES-MAP (DIV2 D24BUS-3 D24-2 D24-1) (ACPLOSS D24BUS-3 D24-2 D24-1)
LIST-AV-RESS (DIV1 DIV3 DIV4 SU10 SU20)
0
AC-POWER Status
AC Power
DIV1
DIV2
DIV3
DIV4
SU10
SU20
10
20
30
40
50
60
70
80
90
100
110
• Robust schedules guaranteeing feasibility
over time-windows
• Fast schedules
• Solutions better than manual solutions
Syllabus 412
• Linear Programming
– Introduction
– Simplex/Revised Simplex
– Duality and Sensitivity Analysis
– Other LP Algorithms
• Network Models
– Transportation Problems
– Assignment Problems
– Network Optimization Models
• Special Topics(*)
– Integer Programming
– Dynamic Programming
– Heuristic techniques
•
•
•
•
Simulated Annealing
Genetic Algorithms
Tabu Search
Neural Networks
– Computational complexity(*)
(*)time permitting
Goals in 412
– Present a variety of models, algorithms, and tools for
optimization
– Illustrate applications in business and economics, and
other fields.
– Prepare students to recognize opportunities for
mathematical optimization as they arise
– Prepare students to be aware of computational complexity
issues: importance of using efficient algorithms whenever
possible and the limits of computation that can affect the
validity of business and economic models.