Optimization Modelling A Practical Approach

List of Figures...................................................................................................... xv List of Tables ...................................................................................................... xxi List of Mathematical Notations .................................................................... xxiv Preface ................................................................................................................. xxv Acknowledgments ............................................ ............................................... xxix Authors............................................................................................................... xxxi Section I Introduction to Optimization and Modelling 1 Introduction ......................................................................................................3 1.1 General Introduction .............................................................................3 1.2 History of Optimization .......................................................................4 1.3 Optimization Problems.........................................................................5 1.4 Mathematical Model..............................................................................6 1.4.1 Characteristics and Assumptions ........................................... 6 1.5 Concept of Optimization ......................................................................8 1.6 Classification of Optimization Problems .........................................11 1.7 Organization of the Book ...................................................................13 Exercises ...........................................................................................................14 References ........................................................................................................15 2 The Process of Optimization.......................................................................17 2.1 Introduction ..........................................................................................17 2.2 Decision Process...................................................................................17 2.3 Problem Identification and Clarification .........................................19 2.4 Problem Definition ..............................................................................20 2.5 Development of a Mathematical Model ..........................................21 2.5.1 Measure of Effectiveness........................................................ 23 2.6 Deriving a Solution..............................................................................25 2.7 Sensitivity Analysis .............................................................................26 2.8 Testing the Solution.............................................................................26 2.9 Implementation ....................................................................................27 v 2.10 Summary ...............................................................................................28 Exercises ...........................................................................................................29 3 Introduction to Modelling ...........................................................................31 3.1 Introduction ..........................................................................................31 3.2 Components of a Mathematical Model............................................31 3.2.1 Decision Variables................................................................... 32 3.2.2 Objective Function................................................................... 32 3.2.3 Constraints................................................................................ 32 3.3 Simple Examples..................................................................................32 3.4 Analyzing a Problem...........................................................................34 3.4.1 A Nonmathematical Programming Problem...................... 35 3.5 Modelling a Simple Problem .............................................................36 3.5.1 Defining the Variables ............................................................ 37 3.5.2 Objective Function................................................................... 37 3.5.3 Constraints................................................................................ 37 3.6 Linear Programming Model ..............................................................39 3.7 More Mathematical Models ...............................................................39 3.8 Integer Programming..........................................................................42 3.9 Multi-Objective Problem.....................................................................45 3.9.1 Objective versus Goal ............................................................. 47 3.10 Goal Programming ..............................................................................47 3.11 Nonlinear Programming.....................................................................49 3.12 Summary ...............................................................................................52 Exercises ...........................................................................................................52 Section II Modelling Techniques 4 Simple Modelling Techniques I ................................................................59 4.1 Introduction ..........................................................................................59 4.2 Use of Subscripts in Variables ...........................................................59 4.3 Simple Modelling Techniques ...........................................................60 4.3.1 Additional Work Requirement in the Formulation........... 61 4.3.2 Variables as Fractions of Other Variables ........................... 64 4.3.3 Maintaining Certain Ratios among Different Variables .... 68 4.3.4 One Constraint Is a Fraction of Another Constraint ......... 70 4.3.5 Maxi–Min or Mini–Max Objective Function....................... 75 4.3.6 Multi-Period Modelling.......................................................... 77 4.3.7 Transforming Infeasible Solutions to Satisfactory Solutions.................................................................................... 79 4.3.8 Single to Multiple Objectives ................................................ 81 4.4 Special Types of Linear Programming.............................................82 4.4.1 Transportation Problem ......................................................... 83 4.4.2 Assignment Problem .............................................................. 86 4.4.3 Transshipment Problem ......................................................... 88 4.4.4 Project Management Problem ............................................... 91 vi 4.5 Summary ...............................................................................................98 Exercises ...........................................................................................................98 Bibliography ..................................................................................................102 5 Simple Modelling Techniques II .............................................................103 5.1 Introduction ........................................................................................103 5.2 Precedence Constraints.....................................................................103 5.3 Either–or Constraints ........................................................................104 5.4 K out of N Constraints Must Hold .................................................105 5.5 Yes-or-No Decisions ..........................................................................106 5.6 Functions with N Possible Values...................................................108 5.7 Mutually Exclusive Alternatives and Contingent Decisions......109 5.8 Linking Constraints with the Objective Function ........................111 5.9 Piecewise Linear Functions ..............................................................113 5.10 Nonlinear to Approximate Functions ............................................116 5.11 Deterministic Models with Probability Terms..............................118 5.12 Alternate Objective Functions .........................................................121 5.13 Constrained to Unconstrained Problem ........................................122 5.14 Simplifying Cross Product of Binary Variables............................124 5.15 Fractional Programming...................................................................126 5.16 Unrestricted Variables.......................................................................128 5.17 Changing Constraint and Objective Type .....................................129 5.17.1 From to¼Constraints..................................................... 129 5.17.2 From to¼Constraints..................................................... 130 5.17.3 From to Constraints.................................................... 130 5.17.4 From to Constraints.................................................... 130 5.17.5 From ¼ Constraint to and Constraints.................... 130 5.17.6 Changing Objective Type................................................... 131 5.18 Conditional Constraints....................................................................132 5.19 Dual Formulation...............................................................................133 5.20 Regression Model ..............................................................................136 5.21 Stochastic Programming...................................................................137 5.22 Constraint Programming..................................................................137 5.23 Summary .............................................................................................138 Exercises .........................................................................................................138 Bibliography ..................................................................................................142 References ......................................................................................................143 6 Modelling Large-Scale and Well-Known Problems I..........................145 6.1 Introduction ........................................................................................145 6.2 Use of the Summation (S) Sign.......................................................145 6.3 Use of the Subset (2) Sign ................................................................147 6.4 Network Flow Problems...................................................................149 6.4.1 Shortest Path Problem ........................................................ 149 6.4.2 Maximum Flow Problem ................................................... 150 6.4.3 Multi-Commodity Flow Problem ..................................... 152 vii 6.5 Knapsack Problem...............................................................................154 6.5.1 Capital Budgeting Problem................................................... 154 6.5.2 Bin Packing Problem .............................................................. 155 6.5.3 Cutting Stock Problem ........................................................... 157 6.6 Facility Location and Layout .............................................................159 6.6.1 Facility Location Problem...................................................... 159 6.6.2 Facility Layout Problem......................................................... 161 6.7 Production Planning and Scheduling ..............................................164 6.7.1 Relevant Literature ................................................................. 165 6.8 Logistics and Transportation .............................................................167 6.8.1 Airlift Problem ........................................................................ 167 6.8.2 Relevant Literature ................................................................. 168 6.9 Summary ...............................................................................................170 Exercises .........................................................................................................170 References ......................................................................................................172 7 Modelling Well-Known Problems II.......................................................177 7.1 Introduction ..........................................................................................177 7.2 Job and Machine Scheduling .............................................................177 7.2.1 Relevant Literature ................................................................. 179 7.3 Assignment and Routing....................................................................180 7.3.1 Generalized Assignment Problem ....................................... 180 7.3.2 Traveling Salesperson Problem............................................ 181 7.3.3 Relevant Literature on Traveling Salesperson Problem..................................................................................... 184 7.3.4 Vehicle Routing Problem....................................................... 185 7.3.5 Relevant Literature on Vehicle Routing Problem ............. 188 7.4 Staff Rostering and Scheduling .........................................................189 7.4.1 Staff Scheduling: A Weekly Problem .................................. 189 7.4.2 Daily Rostering Problem ....................................................... 191 7.4.3 Relevant Literature on General Staff Scheduling .............. 192 7.4.4 Crew Planning=Scheduling Problem................................... 193 7.5 Scheduling and Timetabling Problem..............................................194 7.5.1 School Timetabling Problem................................................. 194 7.5.2 University Timetabling .......................................................... 196 7.5.3 Relevant Literature ................................................................. 197 7.6 Summary ...............................................................................................199 Exercises .........................................................................................................199 References ......................................................................................................201 8 Alternative Modelling ................................................................................205 8.1 Introduction ..........................................................................................205 8.2 Modelling under Different Assumptions ........................................205 8.2.1 A Coal Blending Problem...................................................... 205 8.2.2 First Alternative Blending Model ........................................ 207 8.2.3 Second Alternative Blending Model.................................... 209 viii 8.2.4 Comparing the Two Simple Alternative Models ........... 210 8.2.5 A Crop Planning Problem.................................................. 211 8.2.6 Crop Planning Model 1 ...................................................... 212 8.2.7 Crop Planning Model 2 ...................................................... 213 8.3 Hierarchical Modelling: An Introduction.....................................214 8.3.1 Hierarchical Modelling in a Manufacturing Context .... 215 8.3.2 Aggregate Model ................................................................. 216 8.3.3 Family Scheduling Model .................................................. 217 8.3.4 Individual Item Scheduling Model................................... 218 8.4 Summary ............................................................................................219 References ......................................................................................................220 Section III Model Solving 9 Solution Approaches: An Overview........................................................223 9.1 Introduction .......................................................................................223 9.2 Complexity and Complexity Classes ............................................223 9.2.1 Complexity of Algorithms.................................................. 223 9.2.2 Complexity Classes.............................................................. 224 9.3 Classical Optimization Techniques................................................225 9.3.1 Linear Programming............................................................ 225 9.3.2 Integer Programming: The Curse of Dimensionality ................................................................. 227 9.3.3 Integer Linear Program: Solution Approaches ............... 228 9.3.4 Special Linear Programming Models ............................... 230 9.3.5 Goal Programming............................................................... 230 9.3.6 Nonlinear Programming..................................................... 231 9.3.7 Multi-Objective Models....................................................... 232 9.4 Heuristic Techniques........................................................................233 9.4.1 Hill Climbing ........................................................................ 233 9.4.2 Simulated Annealing ........................................................... 233 9.4.3 Tabu Search........................................................................... 234 9.4.4 Genetic Algorithms.............................................................. 234 9.4.5 Ant Colony Optimization ................................................... 235 9.4.6 Memetic Algorithms ............................................................ 236 9.4.7 Other Heuristics ................................................................... 236 9.5 Optimization Software.....................................................................236 9.5.1 LINGO=LINDO .................................................................... 237 9.5.2 MPL with OptiMax 2000, CPLEX, and XPRESS........................................................................... 237 9.5.3 GAMS..................................................................................... 237 9.5.4 Solver and Premium Solver................................................ 238 9.5.5 Win QSB................................................................................. 238 9.5.6 MINOS ................................................................................... 238 9.6 Summary ............................................................................................239 ix References ....................................................................................................239 Appendix-9A LINGO: An Introduction .................................................241 9A.1 Introduction.....................................................................................241 9A.2 Inputting Model in LINGO...........................................................241 9A.3 Solving the Model...........................................................................243 9A.3.1 Solver Status Window.................................................... 243 9A.3.2 LINGO Special Features ................................................ 244 9A.4 Another Example............................................................................246 9A.4.1 Objective Function .......................................................... 246 9A.4.2 Constraints ....................................................................... 247 9A.4.3 Complete LINGO Model ............................................... 248 9A.4.4 Defining the Sets ............................................................. 249 9A.4.5 Inputting the Data .......................................................... 250 9A.5 LINGO Syntax.................................................................................252 Appendix-9B MPL: An Introduction.......................................................253 9B.1 Introduction .....................................................................................253 9B.2 Use of MPL......................................................................................253 9B.3 Using Vectors and Indexes in MPL.............................................255 9B.4 A Product-Mix Model with Three Variables .............................256 Appendix-9C GAMS: An Introduction...................................................260 9C.1 Introduction.....................................................................................260 9C.2 An Example.....................................................................................260 Appendix-9D Excel Solver: An Introduction .........................................264 9D.1 Introduction.....................................................................................264 9D.2 Solving Linear Programs with Solver .........................................264 9D.2.1 Defining the Target Cell (Objective Function) ........... 266 9D.2.2 Identifying the Changing Cells (Decision Variables) ........................................................ 266 9D.2.3 Adding Constraints ........................................................ 267 9D.2.4 Some Important Options ............................................... 269 9D.2.5 The Solution ..................................................................... 270 Appendix-9E Win QSB: An Introduction ...............................................273 9E.1 Introduction.....................................................................................273 9E.2 Problem Solving with Win QSB...................................................273 9E.3 Reference..........................................................................................275 10 Input Preparation and Model Solving ..................................................277 10.1 Introduction .....................................................................................277 10.2 Data and Data Collection ..............................................................277 10.3 Data Type.........................................................................................279 10.4 Data Preparation .............................................................................280 10.4.1 Data Requirements ......................................................... 282 10.4.2 Data Aggregation............................................................ 283 10.5 Data Preprocessing .........................................................................287 10.6 Model-Driven Data versus Data-Driven Model ........................292 x 10.7 Model Solving .................................................................................292 10.7.1 Excel Solver ....................................................................... 293 10.7.2 LINGO and MPL.............................................................. 295 10.8 Summary .........................................................................................304 Exercises .......................................................................................................304 References.....................................................................................................308 Appendix-10A Additional Problem-Solving Using LINGO ...............309 10A.1 Example 4.6 (Model 4.7) ..............................................................309 10A.1.1 LINGO Code ................................................................ 309 10A.1.2 LINGO Solution ........................................................... 310 10A.2 A Transportation Model ..............................................................310 10A.2.1 LINGO in Algebraic Form ......................................... 311 10A.2.2 LINGO Solution Report.............................................. 311 10A.2.3 LINGO Codes (Alternative)....................................... 312 10A.2.4 LINGO Solution Report (Using Alternative Codes)....................................................... 312 10A.2.5 A Modified Transportation Model ........................... 313 10A.2.6 LINGO Solution Report (with Restricted Path)............................................................................... 314 10A.3 Example 4.14 (Model 4.15) ..........................................................315 10A.3.1 LINGO in Algebraic Form......................................... 315 10A.3.2 LINGO Solution Report ............................................. 316 10A.3.3 LINGO Codes (Alternative Form)............................ 316 10A.3.4 LINGO Solution Report (for Alternative Codes)............................................... 317 10A.4 Example 3.6 (Model 4.1) ..............................................................318 10A.4.1 LINGO in Algebraic Form......................................... 318 10A.4.2 LINGO Model Statistics ............................................. 318 10A.4.3 LINGO Solution........................................................... 318 10A.4.4 LINGO Codes (Alternative Form)............................ 319 10A.4.5 LINGO Solution for Alternative Codes................... 319 10A.5 Example 5.3 (Model 5.2) ..............................................................320 10A.5.1 LINGO Codes .............................................................. 320 10A.5.2 LINGO Solution Report ............................................. 321 10A.5.3 LINGO Alternative Codes ......................................... 321 10A.5.4 LINGO Solution Report (for Alternative Codes)............................................................................ 321 10A.6 Example 5.16..................................................................................322 10A.6.1 LINGO Codes .............................................................. 322 10A.6.2 LINGO Solution Report ............................................. 322 10A.7 Example 4.11 (Model 4.12) ..........................................................323 10A.7.1 LINGO Codes .............................................................. 323 10A.7.2 LINGO Solution Report ............................................. 324 10A.8 Example 5.10 (Model 5.7) ............................................................324 10A.8.1 LINGO Codes .............................................................. 324 10A.8.2 LINGO Solution Report ............................................. 325 xi 11