TableofContentsvii.26111Formulatingand Solving Integer Programs..26111.1Introduction....11.1.1TypesofVariables..261.26211.2ExploitingtheIPCapability:StandardApplications.26211.2.1BinaryRepresentationof General IntegerVariables.26211.2.2MinimumBatchSizeConstraints...26311.2.3FixedChargeProblems.26311.2.4TheSimplePlantLocationProblem.26511.2.5TheCapacitatedPlantLocationProblem(CPL)11.2.6ModelingAlternativeswiththeScenarioApproach.267..26811.2.7LinearizingaPiecewiseLinearFunction11.2.8ConvertingtoSeparableFunctions.27111.3OutlineofIntegerProgrammingMethods..272.27411.4ComputationalDifficultyofIntegerPrograms....27511.4.1NP-CompleteProblems...11.5ProblemswithNaturallyIntegerSolutionsandthePrayerAlgorithm.275.27611.5.1NetworkLPsRevisited....27611.5.2Integral Leontief Constraints.27711.5.3Example:AOne-PeriodMRPProblem....27911.5.4TransformationstoNaturallyIntegerFormulations28111.6TheAssignmentProblemandRelatedSequencingandRoutingProblems.28111.6.1Example:TheAssignmentProblem...28311.6.2TheTravelingSalespersonProblem.28911.6.3CapacitatedMultipleTSPNehicleRoutingProblems..29311.6.4MinimumSpanningTree...29311.6.5TheLinearOrderingProblem..29611.6.6QuadraticAssignmentProblem....29911.7 Problems of Grouping,Matching,Covering,Partitioning,and Packing.30011.7.1FormulationasanAssignmentProblem.....30111.7.2Matching Problems, Groups of Size Two ....30311.7.3GroupswithMoreThanTwoMembers..30711.7.4GroupswithaVariableNumberofMembers,AssignmentVersion..30811.7.5GroupswithAVariableNumberofMembers,PackingVersion.31111.7.6GroupswithAVariableNumberofMembers,CuttingStockProblem..31511.7.7GroupswithAVariableNumberof Members,VehicleRouting.11.8LinearizingProductsof Variables..320.32011.8.1Example:BundlingofProducts...32311.9RepresentingLogicalConditions..32411.10Problems....33512Decision making UnderUncertainty and Stochastic Programs...33512.1Introduction...33512.2 Identifying Sources of Uncertainty..33612.3TheScenarioApproach......33812.4AMore Complicated Two-Period Planning Problem...34012.4.1TheWarm WinterSolution...12.4.2TheColdWinterSolution.340
Table of Contents vii 11 Formulating and Solving Integer Programs.261 11.1 Introduction.261 11.1.1 Types of Variables .261 11.2 Exploiting the IP Capability: Standard Applications.262 11.2.1 Binary Representation of General Integer Variables .262 11.2.2 Minimum Batch Size Constraints.262 11.2.3 Fixed Charge Problems .263 11.2.4 The Simple Plant Location Problem .263 11.2.5 The Capacitated Plant Location Problem (CPL).265 11.2.6 Modeling Alternatives with the Scenario Approach .267 11.2.7 Linearizing a Piecewise Linear Function .268 11.2.8 Converting to Separable Functions .271 11.3 Outline of Integer Programming Methods .272 11.4 Computational Difficulty of Integer Programs.274 11.4.1 NP-Complete Problems .275 11.5 Problems with Naturally Integer Solutions and the Prayer Algorithm.275 11.5.1 Network LPs Revisited.276 11.5.2 Integral Leontief Constraints.276 11.5.3 Example: A One-Period MRP Problem.277 11.5.4 Transformations to Naturally Integer Formulations .279 11.6 The Assignment Problem and Related Sequencing and Routing Problems.281 11.6.1 Example: The Assignment Problem .281 11.6.2 The Traveling Salesperson Problem .283 11.6.3 Capacitated Multiple TSP/Vehicle Routing Problems.289 11.6.4 Minimum Spanning Tree.293 11.6.5 The Linear Ordering Problem .293 11.6.6 Quadratic Assignment Problem .296 11.7 Problems of Grouping, Matching, Covering, Partitioning, and Packing .299 11.7.1 Formulation as an Assignment Problem.300 11.7.2 Matching Problems, Groups of Size Two .301 11.7.3 Groups with More Than Two Members .303 11.7.4 Groups with a Variable Number of Members, Assignment Version .307 11.7.5 Groups with A Variable Number of Members, Packing Version.308 11.7.6 Groups with A Variable Number of Members, Cutting Stock Problem .311 11.7.7 Groups with A Variable Number of Members, Vehicle Routing.315 11.8 Linearizing Products of Variables.320 11.8.1 Example: Bundling of Products.320 11.9 Representing Logical Conditions.323 11.10 Problems.324 12 Decision making Under Uncertainty and Stochastic Programs.335 12.1 Introduction.335 12.2 Identifying Sources of Uncertainty.335 12.3 The Scenario Approach.336 12.4 A More Complicated Two-Period Planning Problem.338 12.4.1 The Warm Winter Solution.340 12.4.2 The Cold Winter Solution.340
vili Table of Contents12.4.3TheUnconditionalSolution...341.34412.5ExpectedValueofPerfectInformation(EVPI).34512.6ExpectedValueofModelingUncertainty.34512.6.1CertaintyEquivalence....12.7RiskAversion...34612.7.1DownsideRisk.34712.7.2Example....348.35012.8ChoosingScenarios..35112.8.1MatchingScenarioStatisticstoTargets...35212.8.2GeneratingScenarioswithaSpecifiedCovarianceStructure.35312.8.3 Generating a Suitable Z Matrix ....12.8.4Example.....35435512.8.5ConvertingMulti-StageProblemstoTwo-StageProblems12.9 Decisions Under Uncertainty with More thanTwo Periods355..35612.9.1DynamicProgrammingandFinancialOptionModels...35712.9.2BinomialTreeModelsof InterestRates..36112.9.3BinomialTreeModelsofForeignExchangeRates..12.10DecisionsUnderUncertaintywithanInfiniteNumberofPeriods363..36512.10.1Example:CashBalanceManagement....12.11Chance-ConstrainedPrograms..368..36912..12Problems........37113PortfolioOptimization....37113.1Introduction...37113.2TheMarkowitzMean/VariancePortfolioModel.13.2.1Example....37237513.3DualingObjectives:EfficientFrontierandParametricAnalysis37513.3.1PortfolioswithaRisk-FreeAsset...37813.3.2TheSharpeRatio......37913.4Important Variationsof thePortfolioModel...38013.4.1PortfolioswithTransactionCosts.38013.4.2Example...38213.4.3PortfolioswithTaxes....38413.4.4FactorsModelforSimplifyingtheCovarianceStructure.38513.4.5Exampleof theFactorModel....13.4.6ScenarioModel forRepresenting Uncertainty.386.38713.4.7Example:ScenarioModelforRepresentingUncertainty13.5Measures of Risk other than Variance ....389.39013.5.1MaximizingtheMinimumReturn.39113.5.2ValueatRisk..39213.5.3ExampleofVAR.39313.6ScenarioModelandMinimizingDownsideRisk...39413.6.1Semi-varianceandDownsideRisk..39613.6.2DownsideRiskandMAD.13.6.3ScenariosBasedDirectlyUponaCovarianceMatrix.396..39813.7Hedging,MatchingandProgramTrading.39813.7.1PortfolioHedging
viii Table of Contents 12.4.3 The Unconditional Solution.341 12.5 Expected Value of Perfect Information (EVPI) .344 12.6 Expected Value of Modeling Uncertainty .345 12.6.1 Certainty Equivalence.345 12.7 Risk Aversion.346 12.7.1 Downside Risk .347 12.7.2 Example .348 12.8 Choosing Scenarios .350 12.8.1 Matching Scenario Statistics to Targets .351 12.8.2 Generating Scenarios with a Specified Covariance Structure.352 12.8.3 Generating a Suitable Z Matrix .353 12.8.4 Example .354 12.8.5 Converting Multi-Stage Problems to Two-Stage Problems .355 12.9 Decisions Under Uncertainty with More than Two Periods .355 12.9.1 Dynamic Programming and Financial Option Models .356 12.9.2 Binomial Tree Models of Interest Rates.357 12.9.3 Binomial Tree Models of Foreign Exchange Rates .361 12.10 Decisions Under Uncertainty with an Infinite Number of Periods.363 12.10.1 Example: Cash Balance Management .365 12.11 Chance-Constrained Programs.368 12.12 Problems.369 13 Portfolio Optimization.371 13.1 Introduction.371 13.2 The Markowitz Mean/Variance Portfolio Model.371 13.2.1 Example .372 13.3 Dualing Objectives: Efficient Frontier and Parametric Analysis .375 13.3.1 Portfolios with a Risk-Free Asset.375 13.3.2 The Sharpe Ratio.378 13.4 Important Variations of the Portfolio Model .379 13.4.1 Portfolios with Transaction Costs .380 13.4.2 Example .380 13.4.3 Portfolios with Taxes.382 13.4.4 Factors Model for Simplifying the Covariance Structure .384 13.4.5 Example of the Factor Model.385 13.4.6 Scenario Model for Representing Uncertainty.386 13.4.7 Example: Scenario Model for Representing Uncertainty.387 13.5 Measures of Risk other than Variance .389 13.5.1 Maximizing the Minimum Return .390 13.5.2 Value at Risk.391 13.5.3 Example of VAR.392 13.6 Scenario Model and Minimizing Downside Risk.393 13.6.1 Semi-variance and Downside Risk .394 13.6.2 Downside Risk and MAD .396 13.6.3 Scenarios Based Directly Upon a Covariance Matrix.396 13.7 Hedging, Matching and Program Trading .398 13.7.1 Portfolio Hedging .398
Tableof Contentsix.39813.7.2 Portfolio Matching, Tracking, and Program Trading ...39913.8MethodsforConstructingBenchmarkPortfolios.....40213.8.1ScenarioApproachtoBenchmarkPortfolios.13.8.2EfficientBenchmarkPortfolios...40413.8.3EfficientFormulationofPortfolioProblems40513.9CholeskyFactorizationforQuadraticPrograms..407..40913.10Problems.....41114MultipleCriteriaandGoal Programming..41114.1Introduction...41214.1.1AlternateOptima andMulticriteria.14.2ApproachestoMulti-criteriaProblems.412.41214.2.1ParetoOptimalSolutionsandMultipleCriteria..14.2.2UtilityFunctionApproach....412.41314.2.3Trade-offCurves.14.2.4Example:AdLibMarketing.41314.3Goal Programming and Soft Constraints....416.41714.3.1Example:SecondaryCriteriontoChooseAmongAlternateOptima..41914.3.2Preemptive/LexicoGoalProgramming.....14.4Minimizing theMaximumHurt,orUnordered LexicoMinimization422.42314.4.1Example....14.4.2 Finding a Unique Solution Minimizing the Maximum.42342814.5IdentifyingPointsontheEfficientFrontier...42814.5.1EfficientPoints,More-is-BetterCase...43014.5.2EfficientPoints,Less-is-BetterCase...43214.5.3EfficientPoints,theMixedCase.....43314.6ComparingPerformancewithData EnvelopmentAnalysis....43814.7Problems......44115Economic Equilibriaand Pricing.....44115.1WhatisanEquilibrium?..44215.2ASimpleSimultaneousPrice/ProductionDecision..44315.3RepresentingSupply&DemandCurvesinLPs...44715.4AuctionsasEconomicEguilibria...45115.5Multi-ProductPricingProblems.......45515.6GeneralEquilibriumModelsofAnEconomy...45715.7Transportation Equilibria........46115.7.1UserEquilibriumvs.SocialOptimum.46315.8EquilibriainNetworksasOptimizationProblems15.8.1EguilibriumNetworkFlows..46515.9Problems..46716GameTheoryandCostAllocation.471.47116.1Introduction.16.2Two-PersonGames.471..47216.2.1TheMinimaxStrategy16.3Two-PersonNon-ConstantSumGames.474
Table of Contents ix 13.7.2 Portfolio Matching, Tracking, and Program Trading .398 13.8 Methods for Constructing Benchmark Portfolios.399 13.8.1 Scenario Approach to Benchmark Portfolios.402 13.8.2 Efficient Benchmark Portfolios.404 13.8.3 Efficient Formulation of Portfolio Problems.405 13.9 Cholesky Factorization for Quadratic Programs.407 13.10 Problems.409 14 Multiple Criteria and Goal Programming .411 14.1 Introduction.411 14.1.1 Alternate Optima and Multicriteria .412 14.2 Approaches to Multi-criteria Problems .412 14.2.1 Pareto Optimal Solutions and Multiple Criteria.412 14.2.2 Utility Function Approach.412 14.2.3 Trade-off Curves .413 14.2.4 Example: Ad Lib Marketing.413 14.3 Goal Programming and Soft Constraints.416 14.3.1 Example: Secondary Criterion to Choose Among Alternate Optima.417 14.3.2 Preemptive/Lexico Goal Programming.419 14.4 Minimizing the Maximum Hurt, or Unordered Lexico Minimization .422 14.4.1 Example .423 14.4.2 Finding a Unique Solution Minimizing the Maximum.423 14.5 Identifying Points on the Efficient Frontier.428 14.5.1 Efficient Points, More-is-Better Case.428 14.5.2 Efficient Points, Less-is-Better Case .430 14.5.3 Efficient Points, the Mixed Case .432 14.6 Comparing Performance with Data Envelopment Analysis.433 14.7 Problems.438 15 Economic Equilibria and Pricing.441 15.1 What is an Equilibrium?.441 15.2 A Simple Simultaneous Price/Production Decision.442 15.3 Representing Supply & Demand Curves in LPs.443 15.4 Auctions as Economic Equilibria .447 15.5 Multi-Product Pricing Problems .451 15.6 General Equilibrium Models of An Economy.455 15.7 Transportation Equilibria.457 15.7.1 User Equilibrium vs. Social Optimum .461 15.8 Equilibria in Networks as Optimization Problems.463 15.8.1 Equilibrium Network Flows.465 15.9 Problems.467 16 Game Theory and Cost Allocation .471 16.1 Introduction.471 16.2 Two-Person Games.471 16.2.1 The Minimax Strategy.472 16.3 Two-Person Non-Constant Sum Games.474
TableofContents+16.3.1Prisoner'sDilemma...475...47616.3.2ChoosingaStrategy....47916.3.3BimatrixGameswithSeveralSolutions.16.4 Nonconstant-Sum Games Involving Two or More Players.48116.4.1ShapleyValue...483..48316.5TheStableMarriagelAssignmentProblem.48716.5.1TheStableRoom-mateMatchingProblem.49016.6Problems....49317Inventory,Production,andSupplyChainManagement....49317.1 Introduction....17.2OnePeriodNewsVendorProblem.493..49417.2.1Analysis of the Decision....49617.3Multi-StageNewsVendor....49917.3.1OrderingwithaBackupOption..50117.3.2SafetyLotsize...50217.3.3MultiproductInventorieswithSubstitution.50617.4EconomicOrderQuantity......50717.5TheQ,rModel......50717.5.1DistributionofLeadTimeDemand.50717.5.2CostAnalysisofQ.r.........51217.6BaseStockInventoryPolicy..51317.6.1BaseStock—PeriodicReview.51317.6.2 Policy...51317.6.3Analysis..51517.6.4BaseStock—ContinuousReview.51517.7Multi-EchelonBaseStock,theMETRICModel.51917.8DCWithHoldbackInventory/Capacity...52117.9Multiproduct,ConstrainedDynamicLotSizeProblems52217.9.1 Input Data...52317.9.2Example....52817.9.3Extensions....52917.10Problems....53118Design&ImplementationofServiceandQueuingSystems-18.1Introduction..531..53118.2ForecastingDemandforServices...53218.3WaitingLineorQueuingTheory..53318.3.1ArrivalProcess..18.3.2QueueDiscipline..534.53418.3.3ServiceProcess.53418.3.4PerformanceMeasuresforServiceSystems53518.3.5Stationarity.....53518.3.6AHandyLittleFormula.53518.3.7Example.....53618.4SolvedQueuingModels53718.4.1NumberofOutboundWATSlinesviaErlangLossModel
x Table of Contents 16.3.1 Prisoner’s Dilemma.475 16.3.2 Choosing a Strategy .476 16.3.3 Bimatrix Games with Several Solutions.479 16.4 Nonconstant-Sum Games Involving Two or More Players .481 16.4.1 Shapley Value.483 16.5 The Stable Marriage/Assignment Problem.483 16.5.1 The Stable Room-mate Matching Problem.487 16.6 Problems.490 17 Inventory, Production, and Supply Chain Management .493 17.1 Introduction.493 17.2 One Period News Vendor Problem .493 17.2.1 Analysis of the Decision.494 17.3 Multi-Stage News Vendor.496 17.3.1 Ordering with a Backup Option.499 17.3.2 Safety Lotsize .501 17.3.3 Multiproduct Inventories with Substitution .502 17.4 Economic Order Quantity .506 17.5 The Q,r Model.507 17.5.1 Distribution of Lead Time Demand .507 17.5.2 Cost Analysis of Q,r .507 17.6 Base Stock Inventory Policy.512 17.6.1 Base Stock — Periodic Review .513 17.6.2 Policy.513 17.6.3 Analysis.513 17.6.4 Base Stock — Continuous Review .515 17.7 Multi-Echelon Base Stock, the METRIC Model.515 17.8 DC With Holdback Inventory/Capacity .519 17.9 Multiproduct, Constrained Dynamic Lot Size Problems .521 17.9.1 Input Data.522 17.9.2 Example .523 17.9.3 Extensions.528 17.10 Problems.529 18 Design & Implementation of Service and Queuing Systems.531 18.1 Introduction.531 18.2 Forecasting Demand for Services .531 18.3 Waiting Line or Queuing Theory.532 18.3.1 Arrival Process.533 18.3.2 Queue Discipline.534 18.3.3 Service Process .534 18.3.4 Performance Measures for Service Systems .534 18.3.5 Stationarity .535 18.3.6 A Handy Little Formula .535 18.3.7 Example .535 18.4 Solved Queuing Models .536 18.4.1 Number of Outbound WATS lines via Erlang Loss Model.537
Table of Contentsxi.53818.4.2EvaluatingServiceCentralizationviatheErlangCModel.53918.4.3AMixedService/lnventorySystemviatheM/G/ooModel.54018.4.4OptimalNumberofRepairmenviatheFiniteSourceModel..54118.4.5 Selection of a Processor Type via the M/G/1 Model .54318.4.6MultipleServerSystemswithGeneralDistribution,M/G/c&G/G/c.54518.5CriticalAssumptionsandTheirValidity.......18.6NetworksofQueues....545.54718.7DesignerQueues..18.7.1Example:PositivebutFiniteWaitingSpaceSystem547.55018.7.2ConstantServiceTime.InfiniteSource.NoLimitonLineLength.55018.7.3ExampleEffectofServiceTimeDistribution...55318.8Problems..19Design&ImplementationofOptimization-BasedDecisionSupportSystems...55555519.1GeneralStructureoftheModelingProcess55619.1.1DevelopingtheModel:DetailandMaintenance.55619.2Verificationand Validation.55619.2.1AppropriateLevelofDetailandValidation.55719.2.2WhenYour Model&the RW Disagree, Bet on the RW.19.2.3ShouldWeBehaveNon-Optimally?558.55819.3SeparationofDataandSystemStructure19.3.1SystemStructure55919.4Marketing theModel....559.55919.4.1Reports..56319.4.2ReportGenerationinLINGO.56519.5ReducingModelSize.....56619.5.1ReductionbyAggregation...56919.5.2ReducingtheNumberofNonzeroes.....56919.5.3ReducingtheNumberofNonzeroesinCoveringProblems.19.6On-the-FlyColumnGeneration.....571..57219.6.1ExampleofColumnGenerationAppliedtoaCuttingStockProblem.57619.6.2ColumnGenerationandIntegerProgramming...19.6.3RowGeneration...57619.7Problems..577.579ReferencesINDEX589
Table of Contents xi 18.4.2 Evaluating Service Centralization via the Erlang C Model .538 18.4.3 A Mixed Service/Inventory System via the M/G/f Model .539 18.4.4 Optimal Number of Repairmen via the Finite Source Model. .540 18.4.5 Selection of a Processor Type via the M/G/1 Model .541 18.4.6 Multiple Server Systems with General Distribution, M/G/c & G/G/c .543 18.5 Critical Assumptions and Their Validity .545 18.6 Networks of Queues .545 18.7 Designer Queues.547 18.7.1 Example: Positive but Finite Waiting Space System .547 18.7.2 Constant Service Time. Infinite Source. No Limit on Line Length .550 18.7.3 Example Effect of Service Time Distribution.550 18.8 Problems.553 19 Design & Implementation of Optimization-Based Decision Support Systems.555 19.1 General Structure of the Modeling Process .555 19.1.1 Developing the Model: Detail and Maintenance .556 19.2 Verification and Validation.556 19.2.1 Appropriate Level of Detail and Validation.556 19.2.2 When Your Model & the RW Disagree, Bet on the RW.557 19.2.3 Should We Behave Non-Optimally? .558 19.3 Separation of Data and System Structure.558 19.3.1 System Structure .559 19.4 Marketing the Model.559 19.4.1 Reports.559 19.4.2 Report Generation in LINGO .563 19.5 Reducing Model Size.565 19.5.1 Reduction by Aggregation.566 19.5.2 Reducing the Number of Nonzeroes .569 19.5.3 Reducing the Number of Nonzeroes in Covering Problems.569 19.6 On-the-Fly Column Generation .571 19.6.1 Example of Column Generation Applied to a Cutting Stock Problem .572 19.6.2 Column Generation and Integer Programming.576 19.6.3 Row Generation .576 19.7 Problems.577 References.579 INDEX .589