Mixed Integer Nonlinear Programming (eBook)
XX, 692 Seiten
Springer New York (Verlag)
978-1-4614-1927-3 (ISBN)
Many engineering, operations, and scientific applications include a mixture of discrete and continuous decision variables and nonlinear relationships involving the decision variables that have a pronounced effect on the set of feasible and optimal solutions. Mixed-integer nonlinear programming (MINLP) problems combine the numerical difficulties of handling nonlinear functions with the challenge of optimizing in the context of nonconvex functions and discrete variables. MINLP is one of the most flexible modeling paradigms available for optimization; but because its scope is so broad, in the most general cases it is hopelessly intractable. Nonetheless, an expanding body of researchers and practitioners - including chemical engineers, operations researchers, industrial engineers, mechanical engineers, economists, statisticians, computer scientists, operations managers, and mathematical programmers - are interested in solving large-scale MINLP instances.
Mixed Integer Nonlinear Programming 3
FOREWORD 5
PREFACE 7
CONTENTS 15
PART I: Convex MINLP 19
ALGORITHMS AND SOFTWARE FORCONVEX MIXED INTEGER NONLINEAR PROGRAMS 20
1. Introduction. 20
2. MINLP. 22
2.1. MINLP problem classes. 22
2.2. Basic elements of MINLP methods. 23
3. Algorithms for convex MINLP. 25
3.1. NLP-Based Branch and Bound. 25
3.2. Outer Approximation. 27
3.3. Generalized Benders Decomposition. 28
3.4. Extended Cutting Plane. 30
3.5. LP/NLP-Based Branch-and-Bound. 31
4. Implementation techniques for convex MINLP. 32
4.1. Linearization generation. 33
4.2. Branching rules. 35
4.2.1. Strong-branching. 35
4.2.2. Pseudo-costs. 36
4.3. Node selection rules. 37
4.4. Cutting planes. 38
4.4.1. Gomory cuts. 39
4.4.2. Mixed integer rounding. 39
4.4.3. Disjunctive inequalities. 40
4.5. Heuristics. 41
4.5.1. Diving heuristics. 42
4.5.2. Feasibility pumps. 42
5. Software. 44
5.1. -ECP 44
5.2. Bonmin. 44
5.3. DICOPT. 45
5.4. FilMINT. 45
5.5. MINLP BB. 46
5.6. SBB. 46
6. Computational study.
46
6.1. Problems 46
6.2. Computational results. 49
7. Conclusions. 50
Acknowledgments. 50
SUBGRADIENT BASED OUTER APPROXIMATION FOR MIXED INTEGER SECOND ORDER CONE PROGRAMMING* 59
1. Introduction. 59
2. Preliminaries. 61
3. Feasible nonlinear subproblems. 62
4. Infeasible nonlinear subproblems. 64
5. The algorithm. 66
6. Numerical experiments. 71
7. Summary. 74
Acknowledgements. 75
PERSPECTIVE REFORMULATION AND APPLICATIONS 78
1. Introduction. 78
1.1. Motivation. 78
1.2. The importance of formulation. 79
1.3. The perspective reformulation. 80
2. Perspective functions and convex hulls. 81
2.1. Using perspective functions to obtain convex hulls. 81
2.2. Computational challenges. 82
3. Simple sets. 82
3.1. The convex hull of a point and a convex set. 82
3.2. The convex hull of a ray and a convex set. 84
3.3. A simple quadratic set. 85
3.4. A larger quadratic set. 85
3.5. A simple non-quadratic set. 87
4. Applications. 88
4.1. Separable Quadratic UFL. 88
4.2. Network design with congestion constraints. 89
4.3. Scheduling with controllable processing times. 90
4.4. The unit commitment problem. 91
4.5. Stochastic service system design. 92
4.6. Portfolio selection. 93
5. Computational approaches. 94
5.1. NLP solvers. 94
5.2. SOCP solvers. 95
5.3. LP solvers. 96
6. Computational results. 97
6.1. Separable quadratic uncapacitated facility location. 97
6.2. Stochastic service design. 100
7. Conclusions. 103
Acknowledgments. 104
PART II: Disjunctive Programming 107
GENERALIZED DISJUNCTIVE PROGRAMMING: A FRAMEWORK FOR FORMULATION AND ALTERNATIVE ALGORITHMS FOR MINLP OPTIMIZATION 108
1. Introduction. 108
2. Generalized disjunctive programming. 109
2.1. Formulation. 110
2.2. Illustrative example. 110
2.3. Solution methods.
112
2.3.1. MINLP reformulation 112
2.3.2. Logic-Based Methods. 114
2.3.3. Example. 115
2.4. Special cases.
117
2.4.1. Linear generalized disjunctive programming 117
2.4.2. Nonconvex generalized disjunctive programs. 122
3. Conclusions. 127
Aknowledgments. 128
DISJUNCTIVE CUTS FOR NONCONVEX MINLP 131
1. Motivation: nonconvex MINLP. 131
2. Lower bounds of an MINLP. 135
3. Disjunctions in MINLP. 136
4. Disjunctive cuts in nonconvex MINLP. 140
5. A procedure to generate disjunctive cuts. 144
6. Experimental results. 146
7. Concluding remarks. 149
Acknowledgments. 149
PART III: Nonlinear Programming 159
SEQUENTIAL QUADRATIC PROGRAMMING METHODS 160
1. Introduction. 160
1.1. Notation. 163
1.2. Background. 163
1.3. Infeasible problems. 165
2. Local properties of SQP methods. 169
2.1. Equality constraints. 170
2.1.1. Newton’s method and SQP. 171
2.1.2. Local convergence. 172
2.1.3. Properties of the Newton step. 173
2.1.4. Calculation of the Newton step. 175
2.2. Inequality constraints. 176
3. The formulation of modern SQP methods. 178
3.1. Review of line-search and trust-region methods. 179
3.1.1. Line-search methods: the unconstrained case. 179
3.1.2. Trust-region methods: the unconstrained case. 181
3.2. The Han-Powell method. 181
3.2.1. Quasi-Newton approximations. 182
3.2.2. Properties of the merit function. 185
3.2.3. Extensions. 186
3.3. Sequential unconstrained methods. 195
3.4. Filter methods. 197
3.4.1. Trust-region filter methods. 198
3.4.2. Line-search filter methods. 200
3.5. SQP methods based on successive LP and QP. 200
4. SQP issues relevant to MINLP.
203
4.1. Treatment of linear constraints 203
4.2. Treatment of infeasibilities. 204
4.3. Infeasibility detection. 204
4.4. Solving a sequence of related QP subproblems. 205
Acknowledgments. 206
APPENDIX
207
A. Methods for quadratic programming 207
A.1. Primal active-set methods. 208
A.1.1. Nonbinding-direction methods. 210
A.1.2. Binding-direction methods. 213
A.2. Dual active-set methods. 216
A.2.1. A dual nonbinding direction method. 217
A.2.2. Finding an initial dual-feasible point. 220
A.2.3. The Goldfarb-Idnani method. 220
A.3. QP regularization. 220
A.4. Solving the KKT system. 225
A.4.1. Variable-reduction methods. 225
A.4.2. The Schur complement method. 226
A.5. Finding an initial feasible point. 228
USING INTERIOR-POINT METHODS WITHIN AN OUTER APPROXIMATION FRAMEWORK FOR MIXED INTEGER NONLINEAR PROGRAMMING 238
1. Introduction. 238
2. Outer approximation. 240
3. Interior-point methods. 241
3.1. Challenges when using interior-point methods. 244
4. The exact primal-dual penalty approach. 246
4.1. Setting and updating the penalty parameters. 248
4.2. Infeasibility detection. 249
5. Special forms of convex NLPs. 250
6. Numerical results. 251
7. Conclusion. 254
Acknowledgements. 254
PART IV: Expression Graphs 257
USING EXPRESSION GRAPHS IN OPTIMIZATION ALGORITHMS 258
1. Introduction. 258
2. Derivative computations. 260
3. Bound computations. 266
4. Presolve and constraint propagation. 269
5. Convexity detection. 270
6. Outer approximations. 271
7. Concluding remarks. 271
Acknowledgment. 271
SYMMETRY IN MATHEMATICAL PROGRAMMING 274
1. Introduction. 274
1.1. Notation. 276
2. Literature review. 277
2.1. Symmetry in Linear Programming. 277
2.2. Symmetry in Mixed-Integer Linear Programming. 277
2.3. Symmetry in Semidefinite Programming. 279
2.4. Automatic symmetry detection. 280
3. Groups of a mathematical program. 281
4. Automatic computation of the formulation group. 283
5. Symmetry breaking constraints. 284
6. An application to the Kissing Number Problem. 285
6.1. Computational results on the KNP. 289
7. Conclusion. 290
Acknowledgements. 290
REFERENCES 290
PART V:
295
USING PIECEWISE LINEAR FUNCTIONS FOR SOLVING MINLPS 296
1. Introduction. 296
2. Linearizing 1Dand separable functions. 298
3. Piecewise linearization of nonseperable functions. 302
4. Controlling the approximation error. 309
5. MIP relaxations of mixed integer nonlinear programs. 314
6. Computational results. 317
7. Future directions. 320
REFERENCES 321
AN ALGORITHMIC FRAMEWORK FOR MINLP WITH SEPARABLE NON-CONVEXITY 324
1. Introduction. 324
2. Our algorithmic framework. 325
2.1. The lower-bounding convex MINLP relaxation 327
2.2. The upper-bounding non-convex NLP restriction 331
2.3. The refinement technique. 332
2.4. The algorithmic framework. 332
2.5. Convergence analysis. 334
3. Computational results. 336
3.1. Uncapacitated Facility Location (UFL) problem. 337
3.2. Hydro Unit Commitment and Scheduling problem. 338
3.3. Nonlinear Continuous Knapsack problem. 342
3.4. GLOBALLib and MINLPLib instances. 348
4. Summary. 355
Acknowledgments. 355
REFERENCES 355
GLOBAL OPTIMIZATION OF MIXED-INTEGER SIGNOMIAL PROGRAMMING PROBLEMS 357
1. Introduction. 357
2. The problem formulation. 357
2.1. Piecewise linear functions using special ordered sets. 359
3. The transformation technique. 361
3.1. Transformations for positive terms. 361
3.1.1. Examples of the transformation technique. 363
3.2. Transformations for negative terms. 363
3.2.1. Example of the transformation technique. 364
3.3. Relationships between the transformations. 365
4. The SGO algorithm. 366
4.1. The preprocessing step. 366
4.2. Solving the convex MINLP problem. 368
4.3. Termination criteria. 368
4.4. Updating the PLFs. 368
5. An illustrative example. 370
6. Computational results. 372
7. Conclusions. 373
PART VI: Mixed-Integer Quadraticaly Constrained Optimization 378
THE MILP ROAD TO MIQCP 379
1. Introduction. 379
1.1. Notation and terminology. 381
2. Convex relaxations and valid inequalities. 381
2.1. Lifting, convexification, and relaxation. 382
2.2. Valid linear inequalities. 383
2.3. Valid second-order-cone inequalities. 384
2.4. Valid semidefinite inequalities. 385
2.5. The strength of valid inequalities. 385
2.5.1. Simple bounds. 385
2.5.2. Binary integer grid. 386
2.5.3. The nonnegative orthant and standard simplex. 386
2.5.4. Half ellipsoid. 388
2.5.5. Bounded quadratic form. 389
3. Convex relaxations and valid inequalities: Related topics.
390
3.1. Another approach to convexification 390
3.2. A SOCP relaxation. 391
3.3. Results relating simple bounds and the binary integer grid. 392
3.4. Completely positive programming. 393
3.5. Higher-order liftings and projections. 394
4. Dynamic approaches for generating valid inequalities. 395
4.1. A procedure for generating disjunctive cuts. 396
4.2. Computational insights. 400
4.3. Working with only the original variables. 404
5. Computational case study. 405
6. Conclusion. 407
Acknowledgements. 408
REFERENCES 408
LINEAR PROGRAMMING RELAXATIONS OF QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMS 412
1. Introduction. 412
2. Relaxations of QCQP problems. 414
2.1. PSD relaxation. 414
2.2. RLT relaxation. 415
3. Our framework. 415
3.1. Initial relaxation. 416
3.2. PSD cuts. 416
3.3. Sparsi cation of PSD cuts. 417
4. Computational results. 419
4.1. Instances. 419
4.2. E ectiveness of each class of cuts. 420
5. Conclusions. 423
Acknowledgments. 424
6. Appendix. 424
EXTENDING A CIP FRAMEWORK TO SOLVE MIQCP 432
1. Introduction. 432
2. Problem definition. 434
3. A constraint handler for quadratic constraints. 434
3.1. Presolving. 435
3.2. Separation. 436
3.3. Propagation. 437
3.4. Enforcement. 438
4. A constraint handler for Second-Order Cone constraints. 439
5. Primal heuristics. 440
6. Computational experiments. 440
7. Conclusions. 445
Acknowledgments. 446
REFERENCES 446
APPENDIX 448
PART VII: Combinatorial Optimization 450
COMPUTATION WITH POLYNOMIAL EQUATIONS AND INEQUALITIES ARISING IN COMBINATORIAL OPTIMIZATION 451
1. Introduction. 451
2. Solving combinatorial systems of equations. 458
2.1. Linear algebra certificates. 458
2.2. Linear algebra relaxations. 460
2.3. Nullstellensatz Linear Algebra Algorithm (NulLA). 462
2.4. Experimental results 466
2.5. Application: The structure of non-3-colorable graphs. 468
3. Adding polynomial inequalities. 470
3.1. Sums of squares, SDP, and feasibility of semialgebraic sets. 471
3.2. Semidefinite programming relaxations. 474
3.3. Theta bodies. 475
3.4. Application: cuts and exact finite sets. 476
4. Recovering solutions in the feasible case. 477
Acknowledgements. 479
APPENDIX 479
REFERENCES 483
MATRIX RELAXATIONS IN COMBINATORIAL OPTIMIZATION 486
1. Introduction 486
2. Matrix relaxations 489
3. Graph partition 491
3.1. Max-k-Cut 491
3.2. Max-Cut 492
3.3. k-Equicut 493
3.4. Approximation results for graph partition. 493
4. Stable sets, cliques and coloring 495
4.1. Stable sets and Cliques. 495
4.2. Coloring. 497
4.3. Approximation results for coloring 499
5. Bandwidth of graphs. The minimum bandwidth problem 499
6. Quadratic assignments. 502
7. Optimal mixing rate of Markov chains. 504
8. Computational progress. 505
8.1. Interior-point methods 506
8.2. Projection methods 508
8.3. Further solution approaches for SDP. 510
Acknowledgements. 511
REFERENCES 511
A POLYTOPE FOR A PRODUCT OF REAL LINEAR FUNCTIONS IN 0/1 VARIABLES 515
1. Introduction. 515
2. Products of nonnegative integer variables. 516
3. Linear integer formulation. 517
4. Facets. 519
5. Inequality characterization 523
6. Separation. 526
7. Ideal points 527
8. A generalization 529
Acknowledgments. 530
REFERENCES 530
PART VIII: Complexity 532
ON THE COMPLEXITY OF NONLINEAR MIXED-INTEGER OPTIMIZATION 533
1. Introduction. 533
2. Preliminaries. 534
2.1. Presentation of the problem. 534
2.2. Encoding issues for solutions. 534
2.3. Approximation algorithms and schemes. 535
3. Incomputability. 536
4. Hardness and inapproximability. 538
4.1. Hardness results from quadratic Diophantine equations in fixed dimension. 539
4.2. Inapproximability of nonlinear optimization in varying dimension. 540
5. Approximation schemes. 541
5.1. Mixed-integer polynomial optimization in fixed dimension over linear constraints: FPTAS and weak FPTAS 541
5.1.1. The summation method. 541
5.1.2. Rational generating functions. 542
5.1.3. Efficient summation using rational generating functions 544
5.1.4. Extension to the mixed-integer case by discretization. 545
5.1.5. Open question. 546
6. Polynomial-time algorithms 546
6.1. Fixed dimension: Continuous polynomial optimization. 547
6.2. Fixed dimension: Convex and quasi-convex integer poly-nomial minimization 548
6.3. Fixed dimension: Convex integer maximization. 553
7. Strongly polynomial-time algorithms: Submodular function minimization. 554
Acknowledgments. 554
REFERENCES 555
THEORY AND APPLICATIONS OF N-FOLD INTEGER PROGRAMMING 558
1. Introduction. 558
2. Applications. 560
2.1. Multiway tables. 560
2.1.1. Multi-index transportation problems. 561
2.1.2. Privacy in statistical databases. 563
2.2. Multicommodity ows 566
2.2.1. The many-commodity transshipment problem. 568
2.2.2. The multicommodity transportation problem. 569
3. Theory 571
3.1. Graver bases and nonlinear integer programming. 572
3.1.1. Graver bases. 572
3.1.2. Separable convex integer minimization. 574
3.1.3. Specializations and extensions. 580
3.2. N-fold integer programming. 583
3.2.1. Graver bases of n-fold products 583
3.2.2. N-fold integer programming in polynomial time 585
3.2.3. Weighted separable convex integer minimization. 586
4. Discussion. 589
4.1. Universality of n-fold integer programming. 589
4.2. Graver complexity of graphs and digraphs 590
Acknowledgements. 590
REFERENCES 591
PART IX: Applications 593
MINLP APPLICATION FOR ACH INTERIORS RESTRUCTURING 594
1. Introduction 594
2. Problem overview. 595
3. MINLP formulation. 596
3.1. Input information. 596
3.2. Variables. 598
3.3. Objective function. 599
3.4. Constraints. 600
4. Discrete MINLP reformulation. 604
4.1. Input Information 604
4.2. Variables. 605
4.3. Objective function 605
4.4. Constraints. 605
5. Solution technique 607
5.1. Decoupling the MINLP 607
5.1.1. Facility capacity problem formulation. 608
5.1.2. Facility utilization problem formulation. 610
5.2. Algorithm. 613
5.2.1. Initialization. 613
5.2.2. Calculate input parameters for FCM. 613
5.2.4. Convergence check after FCM. 614
5.2.5. Calculate input parameters for FUM. 614
5.2.6. Solving the FUM. 615
5.2.7. Convergence check after FUM 615
5.2.8. Implementation. 615
5.2.9. Algorithm convergence. 615
6. Computational example 616
6.1. Inputs. 616
6.2. Results. 621
7. Summary 625
Acknowledgements 626
REFERENCES 626
A BENCHMARK LIBRARY OF MIXED-INTEGER OPTIMAL CONTROL PROBLEMS 627
1. Introduction 627
2. Classi cations. 630
2.1. Model classi cation. 631
2.1.1. ODE model. 631
2.1.2. DAE model. 631
2.1.3. PDE model. 632
2.1.4. Outer convexi cation 632
2.1.5. State-dependent switches. 632
2.1.6. Boolean variables. 632
2.1.7. Multistage processes. 633
2.1.8. Unstable dynamics. 633
2.1.9. Network topology. 633
2.2. Classi cation of the optimization problem. 633
2.2.1. Minimum time. 633
2.2.2. Minimum energy. 633
2.2.3. Tracking problem. 634
2.2.4. Periodic processes. 634
2.2.5. Equilibrium constraints. 634
2.2.6. Complementarity constraints. 634
2.2.7. Vanishing constraints. 635
2.3. Solution classi cation. 635
2.3.1. Bang-bang arcs. 635
2.3.2. Path{constrained arcs. 635
2.3.3. Sensitivity{seeking arcs. 636
2.3.4. Chattering arcs. 636
2.3.5. Sliding mode 636
3. F-8 ight control. 636
3.1. Model and optimal control problem. 636
3.2. Results. 637
4. Lotka Volterra shing problem. 638
4.1. Model and optimal control problem. 639
4.2. Results. 639
4.3. Variants. 639
5. Fuller's problem. 640
5.1. Model and optimal control problem. 640
5.2. Results. 640
5.3. Variants. 640
6. Subway ride. 641
6.1. Model and optimal control problem. 641
6.2. Results. 643
6.3. Variants. 643
7. Resetting calcium oscillations. 644
7.1. Model and optimal control problem. 645
7.2. Results. 646
7.3. Variants. 647
8. Supermarket refrigeration system. 647
8.1. Model and optimal control problem. 647
8.2. Results. 649
8.3. Variants. 649
9. Elchtest testdrive. 650
9.1. Model and optimal control problem. 650
9.2. Results. 653
10. Elliptic track testdrive. 653
10.1. Model and optimal control problem 653
10.2. Results. 654
10.3. Variants. 655
11. Simulated moving bed. 655
11.1. Model and optimal control problem. 655
11.2. Results. 659
12. Discretizations to MINLPs. 659
12.1. General AMPL code. 660
12.2. Lotka Volterra shing problem. 660
12.3. F-8 ight control. 661
13. Conclusions and outlook. 662
Acknowledgements. 663
REFERENCES 663
IMA HOT TOPICS WORKSHOP PARTICIPANTS 667
IMA SUMMER PROGRAMS 671
IMA “HOT TOPICS/SPECIAL” WORKSHOPS 672
SPRINGER LECTURE NOTES FROM THE IMA 674
THE IMA VOLUMES IN MATHEMATICS AND ITS APPLICATIONS 675
| Erscheint lt. Verlag | 2.12.2011 |
|---|---|
| Reihe/Serie | The IMA Volumes in Mathematics and its Applications | The IMA Volumes in Mathematics and its Applications |
| Zusatzinfo | XX, 692 p. |
| Verlagsort | New York |
| Sprache | englisch |
| Themenwelt | Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge |
| Informatik ► Theorie / Studium ► Algorithmen | |
| Mathematik / Informatik ► Mathematik ► Analysis | |
| Mathematik / Informatik ► Mathematik ► Angewandte Mathematik | |
| Mathematik / Informatik ► Mathematik ► Finanz- / Wirtschaftsmathematik | |
| Technik | |
| Schlagworte | CONVEX MINLP • disjunctive programming • Nonlinear Programming |
| ISBN-10 | 1-4614-1927-1 / 1461419271 |
| ISBN-13 | 978-1-4614-1927-3 / 9781461419273 |
| Informationen gemäß Produktsicherheitsverordnung (GPSR) | |
| Haben Sie eine Frage zum Produkt? |
PDF (Wasserzeichen)DRM: Digitales Wasserzeichen
Dieses eBook enthält ein digitales Wasserzeichen und ist damit für Sie personalisiert. Bei einer missbräuchlichen Weitergabe des eBooks an Dritte ist eine Rückverfolgung an die Quelle möglich.
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen dafür einen PDF-Viewer - z.B. den Adobe Reader oder Adobe Digital Editions.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen dafür einen PDF-Viewer - z.B. die kostenlose Adobe Digital Editions-App.
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich
