Preface |
|
xi | |
List of Figures |
|
xvii | |
List of Tables |
|
xxi | |
I Starters |
|
1 | (58) |
|
|
3 | (22) |
|
1.1 The Computational Problem Solving Cycle |
|
|
3 | (3) |
|
1.2 Example: Simple Knapsack Models |
|
|
6 | (3) |
|
1.3 An Example: The Eilon Simple Knapsack Model |
|
|
9 | (2) |
|
1.4 Scoping Out Post-Solution Analysis |
|
|
11 | (7) |
|
|
11 | (2) |
|
|
13 | (1) |
|
|
14 | (1) |
|
|
14 | (1) |
|
|
15 | (1) |
|
|
15 | (1) |
|
|
16 | (2) |
|
1.5 Parameter Sweeping: A Method for Post-Solution Analysis |
|
|
18 | (1) |
|
|
19 | (1) |
|
1.7 Summary of Vocabulary and Main Points |
|
|
20 | (1) |
|
|
21 | (2) |
|
|
23 | (2) |
|
2 Constrained Optimization Models: Introduction and Concepts |
|
|
25 | (18) |
|
2.1 Constrained Optimization |
|
|
25 | (4) |
|
2.2 Classification of Models |
|
|
29 | (4) |
|
2.2.1 (1) Linear Program (LP) |
|
|
30 | (1) |
|
2.2.2 (2) Integer Linear Program (ILP) |
|
|
31 | (1) |
|
2.2.3 (3) Mixed Integer Linear Program (MILP) |
|
|
31 | (1) |
|
2.2.4 (4) Nonlinear Program (NLP) |
|
|
32 | (1) |
|
2.2.5 (5) Nonlinear Integer Program (NLIP) |
|
|
33 | (1) |
|
2.2.6 (6) Mixed Integer Nonlinear Program (MINLP) |
|
|
33 | (1) |
|
|
33 | (2) |
|
2.4 Computational Complexity and Solution Methods |
|
|
35 | (2) |
|
|
37 | (3) |
|
2.5.1 Greedy Hill Climbing |
|
|
37 | (2) |
|
2.5.2 Local Search Metaheuristics: Simulated Annealing |
|
|
39 | (1) |
|
2.5.3 Population Based Metaheuristics: Evolutionary Algorithms |
|
|
39 | (1) |
|
|
40 | (1) |
|
|
40 | (1) |
|
|
41 | (2) |
|
|
43 | (16) |
|
|
43 | (1) |
|
|
43 | (2) |
|
|
45 | (3) |
|
3.4 Post-Solution Analysis of LPs |
|
|
48 | (5) |
|
3.5 More than One at a Time: The 100% Rule |
|
|
53 | (4) |
|
|
57 | (1) |
|
|
58 | (1) |
II Optimization Modeling |
|
59 | (102) |
|
4 Simple Knapsack Problems |
|
|
61 | (20) |
|
|
61 | (1) |
|
4.2 Solving a Simple Knapsack in Excel |
|
|
61 | (1) |
|
4.3 The Bang-for-Buck Heuristic |
|
|
62 | (2) |
|
4.4 Post-Solution Analytics with the Simple Knapsack |
|
|
64 | (8) |
|
4.4.1 Sensitivity Analysis |
|
|
64 | (7) |
|
4.4.2 Candle Lighting Analysis |
|
|
71 | (1) |
|
4.5 Creating Simple Knapsack Test Models |
|
|
72 | (2) |
|
|
74 | (1) |
|
|
74 | (4) |
|
|
78 | (3) |
|
|
81 | (16) |
|
|
81 | (1) |
|
5.2 The Generalized Assignment Problem |
|
|
82 | (3) |
|
5.3 Case Example: GAP 1-c5-15-1 |
|
|
85 | (1) |
|
5.4 Using Decisions from Evolutionary Computation |
|
|
86 | (9) |
|
|
95 | (1) |
|
|
95 | (1) |
|
|
96 | (1) |
|
6 The Traveling Salesman Problem |
|
|
97 | (14) |
|
|
97 | (1) |
|
|
98 | (1) |
|
|
99 | (7) |
|
|
99 | (2) |
|
6.3.2 Heuristic Algorithms |
|
|
101 | (2) |
|
6.3.2.1 Construction Heuristics |
|
|
101 | (1) |
|
6.3.2.2 Iterative Improvement or Local Search |
|
|
102 | (1) |
|
6.3.3 Putting Everything Together |
|
|
103 | (3) |
|
|
106 | (1) |
|
|
107 | (2) |
|
|
109 | (2) |
|
7 Vehicle Routing Problems |
|
|
111 | (8) |
|
|
111 | (1) |
|
|
112 | (1) |
|
|
113 | (3) |
|
|
113 | (1) |
|
7.3.2 Heuristic Algorithms |
|
|
114 | (7) |
|
7.3.2.1 Construction Heuristics |
|
|
115 | (1) |
|
7.3.2.2 Iterative Improvement or Local Search |
|
|
115 | (1) |
|
|
116 | (1) |
|
|
117 | (1) |
|
|
117 | (2) |
|
8 Resource-Constrained Scheduling |
|
|
119 | (10) |
|
|
119 | (1) |
|
|
120 | (1) |
|
|
121 | (4) |
|
|
121 | (1) |
|
8.3.2 Heuristic Algorithms |
|
|
122 | (8) |
|
|
123 | (1) |
|
|
123 | (1) |
|
8.3.2.3 Iterative Improvement or Local Search |
|
|
123 | (2) |
|
|
125 | (2) |
|
|
127 | (1) |
|
|
127 | (2) |
|
|
129 | (20) |
|
|
129 | (1) |
|
9.2 Locating One Service Center |
|
|
130 | (2) |
|
9.2.1 Minimizing Total Distance |
|
|
130 | (2) |
|
9.2.2 Weighting by Population |
|
|
132 | (1) |
|
9.3 A Naive Greedy Heuristic for Locating n Centers |
|
|
132 | (4) |
|
9.4 Using a Greedy Hill Climbing Heuristic |
|
|
136 | (4) |
|
|
140 | (6) |
|
|
146 | (1) |
|
|
147 | (2) |
|
|
149 | (12) |
|
10.1 Quick Introduction: Two-Sided Matching Problems |
|
|
149 | (1) |
|
10.2 Narrative Description of Two-Sided Matching Problems |
|
|
150 | (2) |
|
10.3 Representing the Problem |
|
|
152 | (2) |
|
10.4 Stable Matches and the Deferred Acceptance Algorithm |
|
|
154 | (1) |
|
10.5 Once More, in More Depth |
|
|
155 | (1) |
|
10.6 Generalization: Matching in Centralized Markets |
|
|
156 | (1) |
|
10.7 Discussion: Complications |
|
|
157 | (2) |
|
10.8 For More Information |
|
|
159 | (2) |
III Metaheuristic Solution Methods |
|
161 | (42) |
|
11 Local Search Metaheuristics |
|
|
163 | (16) |
|
|
163 | (1) |
|
11.2 Greedy Hill Climbing |
|
|
163 | (7) |
|
11.2.1 Implementation in Python |
|
|
165 | (2) |
|
11.2.2 Experimenting with the Greedy Hill Climbing Implementation |
|
|
167 | (3) |
|
|
170 | (2) |
|
11.4 Running the Simulated Annealer Code |
|
|
172 | (1) |
|
11.5 Threshold Accepting Algorithms |
|
|
172 | (3) |
|
|
175 | (1) |
|
|
175 | (2) |
|
11.8 For More Information |
|
|
177 | (2) |
|
12 Evolutionary Algorithms |
|
|
179 | (18) |
|
|
179 | (2) |
|
12.2 EPs: Evolutionary Programs |
|
|
181 | (7) |
|
|
181 | (3) |
|
12.2.2 Applying the EP Code to the Test Problems |
|
|
184 | (1) |
|
|
184 | (4) |
|
12.3 The Basic Genetic Algorithm (GA) |
|
|
188 | (7) |
|
|
188 | (5) |
|
12.3.2 Applying the Basic GA Code to a Test Problem |
|
|
193 | (1) |
|
|
193 | (2) |
|
|
195 | (1) |
|
12.5 For More Information |
|
|
195 | (2) |
|
13 Identifying and Collecting Decisions of Interest |
|
|
197 | (6) |
|
13.1 Kinds of Decisions of Interest (DoIs) |
|
|
197 | (2) |
|
|
199 | (2) |
|
|
201 | (1) |
|
|
202 | (1) |
|
13.5 For More Information |
|
|
202 | (1) |
IV Post-Solution Analysis of Optimization Models |
|
203 | (76) |
|
|
205 | (14) |
|
|
205 | (1) |
|
14.2 Decision Sweeping with the GAP 1-c5-15-1 Model |
|
|
205 | (2) |
|
14.3 Deliberating with the Results of a Decision Sweep |
|
|
207 | (7) |
|
|
214 | (1) |
|
|
214 | (2) |
|
14.6 For More Information |
|
|
216 | (3) |
|
|
219 | (10) |
|
15.1 Introduction: Reminders on Solution Pluralism and Parameter Sweeping |
|
|
219 | (1) |
|
15.2 Parameter Sweeping: Post-Solution Analysis by Model Re-Solution |
|
|
220 | (5) |
|
15.2.1 One Parameter at a Time |
|
|
221 | (1) |
|
15.2.2 Two Parameters at a Time |
|
|
222 | (1) |
|
15.2.3 N Parameters at a Time |
|
|
222 | (1) |
|
|
223 | (2) |
|
15.2.5 Active Nonlinear Tests |
|
|
225 | (1) |
|
15.3 Parameter Sweeping with Decision Sweeping |
|
|
225 | (1) |
|
|
226 | (1) |
|
|
226 | (1) |
|
15.6 For More Information |
|
|
227 | (2) |
|
16 Multiattribute Utility Modeling |
|
|
229 | (14) |
|
|
229 | (1) |
|
16.2 Single Attribute Utility Modeling |
|
|
230 | (4) |
|
16.2.1 The Basic Framework |
|
|
230 | (1) |
|
16.2.2 Example: Bringing Wine |
|
|
231 | (3) |
|
16.3 Multiattribute Utility Models |
|
|
234 | (5) |
|
16.3.1 Multiattribute Example: Picking a Restaurant |
|
|
235 | (1) |
|
16.3.2 The SMARTER Model Building Methodology |
|
|
236 | (48) |
|
16.3.2.1 Step 1: Purpose and Decision Makers |
|
|
236 | (1) |
|
16.3.2.2 Step 2: Value Tree |
|
|
236 | (1) |
|
16.3.2.3 Step 3: Objects of Evaluation |
|
|
236 | (1) |
|
16.3.2.4 Step 4: Objects-by-Attributes Table |
|
|
237 | (1) |
|
16.3.2.5 Step 5: Dominated Options |
|
|
237 | (1) |
|
16.3.2.6 Step 6: Single-Dimension Utilities |
|
|
237 | (1) |
|
16.3.2.7 Step 7: Do Part I of Swing Weighting |
|
|
238 | (1) |
|
16.3.2.8 Step 8: Obtain the Rank Weights |
|
|
238 | (1) |
|
16.3.2.9 Step 9: Calculate the Choice Utilities and Decide |
|
|
239 | (1) |
|
|
239 | (1) |
|
|
240 | (1) |
|
16.6 For More Information |
|
|
240 | (3) |
|
17 Data Envelopment Analysis |
|
|
243 | (10) |
|
|
243 | (4) |
|
|
247 | (1) |
|
17.3 Demonstration of DEA Concept |
|
|
247 | (3) |
|
|
250 | (1) |
|
|
250 | (1) |
|
17.6 For More Information |
|
|
250 | (3) |
|
18 Redistricting: A Case Study in Zone Design |
|
|
253 | (26) |
|
|
253 | (1) |
|
18.2 The Basic Redistricting Formulation |
|
|
254 | (1) |
|
18.3 Representing and Formulating the Problem |
|
|
255 | (3) |
|
18.4 Initial Forays for Discovering Good Districting Plans |
|
|
258 | (9) |
|
18.5 Solving a Related Solution Pluralism Problem |
|
|
267 | (5) |
|
|
272 | (3) |
|
|
275 | (1) |
|
18.8 For More Information |
|
|
276 | (3) |
V Conclusion |
|
279 | (10) |
|
|
281 | (8) |
|
|
281 | (1) |
|
19.2 Revisiting Post-Solution Analysis |
|
|
281 | (3) |
|
|
284 | (5) |
|
|
285 | (2) |
|
|
287 | (2) |
A Resources |
|
289 | (2) |
|
|
289 | (2) |
Bibliography |
|
291 | (12) |
Index |
|
303 | |