Open Problems in Optimization and Data Analysis

Preface......Page 5
Citation......Page 12
Contents......Page 14
Contributors......Page 16
 1 Introduction......Page 19
 2 Some Open and Challenging Problems......Page 21
 3 Concluding Remarks......Page 24
 References......Page 25
 1 Introduction......Page 27
 2 Bharathi–Kempe–Salek Conjecture......Page 28
 3 Approximation of Influence Spread......Page 29
 4 Active Friending......Page 32
 5 Rumor Blocking and Source Detection......Page 34
 References......Page 37
 1 Introduction......Page 41
  2.1 M-Estimates with a Bounded ρ-Function......Page 43
  2.4 Asymptotic Normality......Page 44
  2.5 Equivariance......Page 45
 3 Robust Local Estimation, Multivariate Least Trimmed Absolute Deviation Estimation......Page 46
  3.1 Least Trimmed Absolute Deviation Estimator, LTAD......Page 47
  3.2 Mixed Integer Programming Formulation......Page 48
  3.4 Solution of LP Relaxation......Page 49
  3.6 Conclusions and Open Problems......Page 50
 4 Optimization Techniques for Robust Multivariate Location and Scatter Estimation......Page 51
   4.1.1 Least Trimmed Euclidean Distance Estimator......Page 52
  4.2 Detection of Scatter Outliers......Page 53
  4.4 Conclusions and Open Problems......Page 55
 5 Robust Regression with Penalized Trimmed Squares (PTS)......Page 56
   5.1.2 Huber-Type Estimator as a Convex Quadratic Program......Page 57
  5.2 Least Trimmed Squares......Page 58
  5.3 Penalized Trimmed Squares......Page 59
   5.3.1 Quadratic Mixed Integer Programming for PTS......Page 60
   5.3.2 Fast-PTS......Page 61
   5.4.1 -Insensitive Penalized Trimmed Squares......Page 62
   5.4.3 Conclusions and Open Problems......Page 63
 References......Page 64
Optimal Location Problems for Electric Vehicles Charging Stations: Models and Challenges......Page 66
 1 Introduction......Page 67
 2 Demand Forecasting......Page 68
  3.1 Point Demand Location Models......Page 70
  3.2 Flow Covering Models......Page 71
 4 Challenges......Page 73
 References......Page 75
 1 Demand Selection Problems......Page 78
  1.1 EOQ with Market Choice......Page 79
   1.1.1 EOQ Model with Infinite Production Rate......Page 80
  1.2 Selective Newsvendor......Page 81
  1.3 Requirements Planning with Demand Selection......Page 83
   1.3.1 ELSP with Order Selection......Page 84
   1.3.2 ELSP with Market Choice......Page 85
   1.4.1 Selective Newsvendor with Correlated Customer Demands......Page 86
   1.4.3 Selective Newsvendor with Non-normal Demands......Page 87
 2 Supplier Selection Problems......Page 88
  2.1 Supplier Selection with Deterministic Demand......Page 89
  2.2 Supplier Selection with Uncertain Demand......Page 91
  2.3 Supplier Selection with Unreliable Suppliers......Page 92
   2.4.1 Integrated Economic Lot-Sizing and Supplier Selection......Page 94
   2.4.3 All-or-Nothing Supplier Reliability......Page 95
 3 Combined Supplier and Demand Selection Problems......Page 96
 References......Page 98
Open Problems in Green Supply Chain Modeling and Optimization with Carbon Emission Targets......Page 100
 2 Open Problems: Formulation and Optimization Issues......Page 101
 References......Page 106
 1 Introduction......Page 108
 2 Capacitated Vehicle Routing Problem......Page 109
  3.1 Open Vehicle Routing Problem......Page 115
  3.2 Vehicle Routing Problem with Time Windows......Page 116
  4.1 One Commodity Pickup and Delivery Problem......Page 118
  4.2 Vehicle Routing Problem with Simultaneous Pickup and Delivery......Page 119
  5.1 Split Delivery Vehicle Routing Problem......Page 121
  5.5 Multi-Vehicle Covering Tour Problem......Page 122
  5.9 Periodic Vehicle Routing Problem......Page 123
  5.12 Green Vehicle Routing Problem......Page 124
  5.14 School Bus Routing and Scheduling Problem......Page 126
  5.16 Team Orienteering Problem......Page 127
  6.1 Vehicle Routing Problem with Stochastic Demands......Page 128
  6.2 Vehicle Routing Problem with Stochastic Demands and Customers......Page 130
  6.4 Vehicle Routing Problem with Fuzzy Demands......Page 131
  7.1 The Chinese Postman Problem......Page 132
  7.3 The Capacitated Arc Routing Problem......Page 133
  8.1 Location Routing Problem......Page 134
  8.2 Location Routing Problem with Stochastic Demands......Page 136
  8.3 Inventory Routing Problem......Page 138
  8.5 Ship Routing Problem......Page 139
 References......Page 140
 1 Introduction......Page 145
 2 The New Mathematical Models......Page 148
 3 Computational Results......Page 153
 4 Extensive Results with Some Statistical Analyses......Page 158
 References......Page 163
 1 Introduction......Page 166
  2.1 A Mathematical Model......Page 168
  3.1 Mathematical Model......Page 172
  4.1 A Mathematical Model......Page 174
  4.2 Some Open Problems......Page 178
  5.1 Mathematical Model......Page 179
  5.2 Existing Methods and Challenges......Page 182
 References......Page 183
 1 Introduction......Page 186
 2 Generalizations and Open Problems......Page 188
 References......Page 194
 1 Introduction......Page 197
 2 Main Application Areas......Page 198
  3.1 Impact of DG on Rigidity......Page 200
  4.1 DGP in Given Dimensions......Page 201
  4.4 Isometric Embeddings......Page 202
  4.5 Matrix Completion......Page 203
  5.1 Combinatorial Characterization of Rigidity......Page 204
   5.1.1 Rigidity of Frameworks......Page 205
   5.1.2 Infinitesimal Rigidity......Page 206
   5.1.3 Generic Properties......Page 208
   5.1.5 Combinatorial Characterization of Rigidity in the Plane......Page 209
   5.1.6 Combinatorial Characterization of Rigidity in Space......Page 210
   5.1.8 Relevance......Page 211
   5.2.1 Complexity in the TM Model......Page 212
   5.2.2 Complexity of Graph Rigidity......Page 214
   5.2.3 NP-Hardness of the DGP......Page 215
   5.2.5 EDMs and PSD Matrices......Page 217
   5.2.6 Relevance......Page 218
   5.3.1 Either Finite or Uncountable......Page 219
   5.3.2 Loop Flexes......Page 220
   5.3.3 Solution Sets of Protein Backbones......Page 221
   5.3.4 Clifford Algebra......Page 224
   5.3.5 Phase Transitions Between Flexibility and Rigidity......Page 225
   5.3.6 Relevance......Page 226
   5.4.1 Determining Nanostructures from Spectra......Page 227
   5.4.2 Protein Shape from NOESY Data......Page 229
 6 Conclusion......Page 230
 References......Page 231
  1.1 Problem Definition......Page 238
   1.1.3 Optimization Problem of the Inscribed Ball in Polyhedral Set......Page 239
 2 Problem Formulation......Page 240
  3.1 Some Notations......Page 241
  3.2 A Few Preliminary Results......Page 242
  3.3 Expression of r1 via r2......Page 243
  3.4 Existence of Global Maximum of r12 + r22......Page 245
  3.5 Green Candidate and Red Candidate......Page 246
 4 Maximum of r12 + r22 Type 1 PT Case......Page 248
  4.1 Max Q(cotβ- ycotβ- tanα,y): Searching on the Green Line of the Domain......Page 249
  4.2 Max Q(1,y): Searching on the Red Line of the Domain......Page 251
 5 Maximum of r12 + r22 Type 2 QR Case......Page 253
 6 Maximum of r12 + r22......Page 254
  7.1 The Cutting Line Goes Through All Three Sides of the Triangle......Page 255
  7.2 Malfatti n=2 Problem as Corollary......Page 257
 Appendix......Page 259
 References......Page 260
 1 Introduction......Page 262
  2.1 Initial Solution......Page 264
   2.2.1 K-Means Heuristic......Page 266
   2.2.2 H-Means Heuristic......Page 267
   2.2.3 J-Means Heuristic......Page 268
   2.3.2 Nested VND......Page 269
 3 General Variable Neighborhood Search......Page 271
  4.1 Instances......Page 272
  4.2 Parameters......Page 273
  4.4 Medium and Large Instances......Page 274
 5 Conclusions and Open Problems......Page 275
 Appendix 1: Small Instances......Page 276
 Appendix 2: Medium and Large Instances......Page 281
 References......Page 282
 1 Introduction......Page 284
 2 Algorithm Portfolios......Page 286
 3 Open Problems in Designing Algorithm Portfolios......Page 287
  3.1 Selection of Constituent Algorithms......Page 288
  3.2 Allocation of Computation Budget......Page 290
  3.3 Interaction of Constituent Algorithms......Page 293
  3.4 The Role of Parallelism......Page 294
 4 Conclusions......Page 295
 References......Page 296
 1 Introduction......Page 298
 2 Quasi-Integrality and the Integral Simplex Method......Page 300
 3 All-Integer Pivots......Page 304
 4 Cycling for All-Integer Pivots......Page 312
 5 Some Open Questions......Page 314
 References......Page 315
 1 Introduction......Page 317
  1.1 About Jacques F. Benders......Page 318
 2 Benders Decomposition Method......Page 319
  3.1 Problem 1: What Is the Theoretical Proof of the Effectiveness of Acceleration Methods of Benders Decomposition Algorithm?......Page 322
  3.3 Problem 3: Is There an Optimal Way to Decompose a Given Problem?......Page 323
  3.4 Problem 4: Fluctuation of the Upper Bound (in a Minimization Problem)......Page 324
  3.5 Problem 5: Does Producing More Optimality than Feasibility Cuts Lead to Faster Convergence of Benders Algorithm?......Page 326
  3.6 Problem 6: In Multi-Cut Generation Strategies, What Is the Optimal Number of Cuts to Be Generated in Each Iteration So that the Master Problem Is Not Overloaded?......Page 327
 References......Page 328
An Example of Nondecomposition in Data Fitting by Piecewise Monotonic Divided Differences of Order Higher Than Two......Page 330
 1 Introduction......Page 331
 2 The Example......Page 333
 References......Page 340