Dedication ...................................................... v
List of Figures .............................................. xiii
List of Tables ................................................ xvi
Preface ....................................................... xix
Acknowledgments .............................................. xxii
1. INTRODUCTION ................................................. 1
1.1. Classification of Nonlinear Integer Programming
Formulations ............................................... 2
1.2. Examples of Applications ................................... 4
1.2.1. Resource allocation in production planning .......... 4
1.2.2. Portfolio selection ................................. 4
1.2.3. Redundancy optimization in reliability networks ..... 6
1.2.4. Chemical engineering ................................ 7
1.3. Difficulties and Challenges ................................ 8
1.4. Organization of the Book .................................. 10
1.5. Notes ..................................................... 11
2. OPTIMALITY, RELAXATION AND GENERAL SOLUTION
PROCEDURES .................................................. 13
2.1. Optimality Condition via Bounds ........................... 14
2.2. Partial Enumeration ....................................... 14
2.2.1. Outline of the general branch-and-bound method ..... 15
2.2.2. The back-track scheme .............................. 17
2.3. Continuous Relaxation and Lagrangian Relaxation ........... 24
2.3.1. Continuous relaxation .............................. 24
2.3.2. Lagrangian relaxation .............................. 25
2.3.3. Continuous bound versus Lagrangian bound ........... 26
2.4. Proximity between Continuous Solution and Integer
Solution .................................................. 28
2.4.1. Linear integer program ............................. 29
2.4.2. Linearly constrained separable convex integer
program ............................................ 31
2.4.3. Unconstrained convex integer program ............... 32
2.5. Penalty Function Approach ................................. 37
2.6. Optimality Conditions for Unconstrained Binary
Quadratic Problems ........................................ 38
2.6.1. General case ....................................... 38
2.6.2. Convex case ........................................ 42
2.7. Notes ..................................................... 44
3. LAGRANGIAN DUALITY THEORY ................................... 45
3.1. Lagrangian Relaxation and Dual Formulation ................ 45
3.2. Dual Search Methods ....................................... 52
3.2.1. Subgradient method ................................. 52
3.2.2. Outer Lagrangian linearization method .............. 57
3.2.3. Bundle method ...................................... 68
3.3. Perturbation Function ..................................... 70
3.4. Optimal Generating Multiplier and Optimal Primal-Dual
Pair ...................................................... 77
3.5. Solution Properties of the Dual Problem ................... 83
3.6. Lagrangian Decomposition via Copying Constraints .......... 88
3.6.1. General Lagrangian decomposition schemes ........... 88
3.6.2. 0-1 quadratic case ................................. 91
3.7. Notes ..................................................... 95
4. SURROGATE DUALITY THEORY .................................... 97
4.1. Conventional Surrogate Dual Method ........................ 97
4.1.1. Surrogate dual and its properties .................. 97
4.1.2. Surrogate dual search .............................. 99
4.2. Nonlinear Surrogate Dual Method .......................... 104
4.3. Notes .................................................... 112
5. NONLINEAR LAGRANGIAN AND STRONG DUALITY .................... 113
5.1. Convexifieation and Nonlinear Support: p-th power
Nonlinear Lagrangian Formulation ......................... 113
5.2. Nonlinear Lagrangian Theory Using Equivalent
Reformulation ............................................ 118
5.3. Nonlinear Lagrangian Theory Using
Logarithmic-Exponential Dual Formulation ................. 127
5.4. Generalized Nonlinear Lagrangian Theory for
Singly-Constrained Nonlinear Integer Programming
Problems ................................................. 137
5.5. Notes .................................................... 148
6. NONLINEAR KNAPSACK PROBLEMS ................................ 149
6.1. Continuous-Relaxation-Based Branch-and-Bound Methods ..... 150
6.1.1. Multiplier search method .......................... 151
6.1.2. Pegging method .................................... 157
6.2. 0-1 Linearization Method ................................. 159
6.2.1. 0-1 linearization ................................. 159
6.2.2. Algorithms for 0-1 linear knapsack problem ........ 161
6.3. Convergent Lagrangian and Domain Cut Algorithm ........... 164
6.3.1. Derivation of the algorithm ....................... 165
6.3.2. Domain cut ........................................ 170
6.3.3. The main algorithm ................................ 173
6.3.4. Multi-dimensional nonlinear knapsack problems ..... 176
6.4. Concave Nonlinear Knapsack Problems ...................... 181
6.4.1. Linear approximation .............................. 181
6.4.2. Domain cut and linear approximation method ........ 184
6.5. Reliability Optimization in Series-Parallel
Reliability Networks ..................................... 188
6.5.1 Maximal decreasing property ........................ 190
6.6. Implementation and Computational Results ................. 195
6.6.1. Test problems ..................................... 196
6.6.2. Heuristics for feasible solutions ................. 198
6.6.3. Numerical results of Algorithm 6.2 for singly
constrained cases ................................. 199
6.6.4. Numerical results of Algorithm 6.2 for
multiply constrained cases ........................ 201
6.6.5. Numerical results of Algorithm 6.3 ................ 202
6.6.6. Comparison results ................................ 203
6.7. Notes .................................................... 206
7. SEPARABLE INTEGER PROGRAMMING .............................. 209
7.1. Dynamic Programming Method ............................... 209
7.1.1. Backward dynamic programming ...................... 210
7.1.2. Forward dynamic programming ....................... 211
7.1.3. Singly constrained case ........................... 215
7.2. Hybrid Method ............................................ 217
7.2.1. Dynamic programming procedure ..................... 218
7.2.2. Incorporation of elimination procedure ............ 219
7.2.3. Relaxation of (RSPk) .............................. 221
7.3. Convergent Lagrangian and Objective Level Cut Method ..... 224
7.3.1. Motivation ........................................ 224
7.3.2. Algorithm description ............................. 227
7.3.3. Implementation of dynamic programming ............. 233
7.3.4. Computational experiment .......................... 236
7.4. Notes .................................................... 238
8. NONLINEAR INTEGER PROGRAMMING WITH A QUADRATIC
OBJECTIVE FUNCTION ......................................... 241
8.1. Quadratic Contour Cut .................................... 241
8.1.1. Ellipse of quadratic contour ...................... 242
8.1.2. Contour cuts of quadratic function ................ 243
8.2. Convergent Lagrangian and Objective Contour Cut Method ... 245
8.3. Extension to Problems with Multiple Constraints .......... 250
8.4. Extension to Problems with Indefinite q .................. 254
8.5. Computational Results .................................... 257
8.5.1. Test problems ..................................... 258
8.5.2. Computational results ............................. 260
8.5.3. Comparison with other methods ..................... 262
8.6. Note ..................................................... 264
9. NONSEPARABLE INTEGER PROGRAMMING ........................... 265
9.1. Branch-and-Bound Method based on Continuous Relaxation ... 265
9.1.1. Branching variables ............................... 267
9.1.2. Branching nodes ................................... 268
9.2. Lagrangian Decomposition Method .......................... 268
9.3. Monotone Integer Programming ............................. 272
9.3.1. Discrete polyblock method for {MIP) ............... 273
9.3.2. Convexity and monotonicity ........................ 277
9.3.3. Equivalent transformation using convexification ... 281
9.3.4. Polyblock and convexification method for (MIP) .... 284
9.3.5. Computational results ............................. 286
9.4. Notes .................................................... 290
10. UNCONSTRAINED POLYNOMIAL 0-1 OPTIMIZATION ................. 293
10.1.Roof Duality ............................................. 293
10.1.1.Basic concepts .................................... 294
10.1.2.Relation to other linearization formulations ...... 297
10.1.3.Quadratic case .................................... 299
10.2.Local Search ............................................. 300
10.3.Basic Algorithm .......................................... 301
10.4.Continuous Relaxation and its Convexification ............ 304
10.5.Unconstrained Quadratic 0-1 Optimization ................. 306
10.5.1.A polynomially solvable case ...................... 307
10.5.2.Equivalence to maximum-cut problem ................ 308
10.5.3.Variable fixation ................................. 309
10.6.Notes .................................................... 313
11.CONSTRAINED POLYNOMIAL 0-1 PROGRAMMING ..................... 315
11.1.Reduction to Unconstrained Problem ....................... 315
11.2.Linearization Methods .................................... 317
11.3.Branch-and-Bound Method .................................. 319
11.3.1.Upper bounds and penalties ........................ 319
11.3.2.Branch-and-bound method ........................... 320
11.4.Cutting Plane Methods .................................... 321
11.4.1.Generalized covering relaxation ................... 321
11.4.2.Lower bounding linear function .................... 324
11.4.3.Linearization of polynomial inequality ............ 326
11.5.Quadratic 0-1 Knapsack Problems .......................... 328
11.5.1.Lagrangian dual of {QKP) .......................... 328
11.5.2.Heuristics for finding feasible solutions ......... 335
11.5.3.Branch-and-bound method ........................... 339
11.5.4.Alternative upper bounds .......................... 341
11.6.Notes .................................................... 348
12.TWO LEVEL METHODS FOR CONSTRAINED POLYNOMIAL
0-1 PROGRAMMING ............................................ 349
12.1.Revised Taha's Method .................................... 349
12.1.1.Definitions and notations ......................... 350
12.1.2.Fathoming, consistency and augmentation ........... 352
12.1.3.Solution algorithm ................................ 357
12.2.Two-Level Method for p-Norm Surrogate Constraint
Formulation .............................................. 360
12.3.Convergent Lagrangian Method Using Objective Level
Cut ...................................................... 368
12.4.Computational Results .................................... 370
12.5.Notes .................................................... 371
13.MIXED-INTEGER NONLINEAR PROGRAMMING ........................ 373
13.1.Introduction ............................................. 373
13.2.Branch-and-Bound Method .................................. 375
13.3.Generalized Benders Decomposition ........................ 377
13.4.Outer Approximation Method ............................... 382
13.5.Nonconvex Mixed-Integer Programming ...................... 389
13.5.1.Convex relaxation ................................. 390
13.5.2.Convexification method ............................ 393
13.6.Notes .................................................... 394
14. GLOBAL DESCENT METHODS .................................... 397
14.1.Local Search and Global Descent .......................... 398
14.1.1.Local minima and local search ..................... 398
14.1.2.Identification of global minimum from among
local minima ...................................... 400
14.2.A Class of Discrete Global Descent Functions ............. 400
14.2.1.Condition (Dl) .................................... 403
14.2.2.Condition (D2) .................................... 403
14.2.3.Condition (D3) .................................... 405
14.3.The Discrete Global Descent Method ....................... 410
14.4.Computational Results .................................... 412
14.5.Notes .................................................... 416
References .................................................... 419
Index ......................................................... 433
List of Figures
1.1. The ARPA complex system (n = 7) ............................ 7
1.2. Superstructure of synthesization of a chemical
process [53] ............................................... 8
2.1. Diagram of the general branch-and-bound method ............ 16
2.2. Diagram of the back-track scheme .......................... 19
2.3. Diagram of the additive algorithm of Balas ................ 22
3.1. Illustration of the solution scheme for (SPj) ............. 50
3.2. Error bound d(λ*) - d(λk) in the subgradient method
with Rule 1 for stepsize for Example 3.1 .................. 57
3.3. Error bound d(λ*) - νk in the subgradient method with
Rule 1 for stepsize for Example 3.1 ....................... 58
3.4. Error bound d(λ*) - d(λk) in the subgradient method
with Rule 2 for stepsize for Example 3.1 .................. 58
3.5. Error bound d(λ*) - νk in the subgradient method with
Rule 2 for stepsize for Example 3.1 ....................... 59
3.6. Error bound d(λ*) - d(λk) in the subgradient method
with Rule 3 for stepsize for Example 3.1 .................. 59
3.7. Error bound d(λ*) - νk in the subgradient method with
Rule 3 for stepsize for Example 3.1 ....................... 60
3.8. Dual function of Example 3.3 .............................. 64
3.9. Perturbation function of Example 3.4 ...................... 72
3.10. Illustration of perturbation function w and decomposition
of Y ...................................................... 73
3.11.Perturbation function where there exists no subgradient
of ω at у = g(х*) ......................................... 80
3.12.Perturbation function where there exists a subgradient
of ω at у = g{х*) ......................................... 81
4.1. Surrogate constraints in the constraint space of
Example 4.1 .............................................. 105
4.2. p-norm surrogate constraints in the constraint space
with μ = (0.4, 0.6)T and b = (3, 2)T ..................... 107
4.3. p-norm surrogate constraints in the constraint space of
Example 4.1 with μ = (0.6316,0.3684)T .................... 111
5.1. Set S in {x1, X2} space .................................. 114
5.2. Set Sp in {x1p, x2p} space ................................ 114
5.3. Illustration of ωp(у) and ψp(у) for Example 3.4 with
p = 2 .................................................... 117
5.4. Contours of zp + λT{yp - bP) - r with different values
of p ..................................................... 118
5.5. ω1p and ψ1p of Example 3.4 with p = 3 ..................... 125
5.6. Illustration of ω(y) and ψ(у) for Example 3.4 with
b = 3.5 .................................................. 125
5.7. Illustration of ω1p(у) and ψ1p(у) for Example 3.4 with
p = 2 .................................................... 127
5.8. Illustration of the Lagrangian dual search for Example
5.3 ...................................................... 129
5.9. Illustration of the contour Cm(z, λ) = a for Example
5.3 (λ = 8, α = 1.8) ..................................... 130
5.10.Behavior of Cp(z, λ) = a (p = 0.7, α = 1) for
various A ................................................ 132
5.11.Behavior of Cp(z, λ) = a (λ = 0.7, α = 1) for
various p ................................................ 132
5.12. Contour Cp(z,4) = α for Example 5.3 (p = 1.2, α =
CP(P*, 4) = 1.2798) ...................................... 133
6.1. Linear approximation of fj(xj) ........................... 160
6.2. Linear Approximation of gj(xj) ........................... 160
6.3. Domain X and the feasible region of Example 6.4 .......... 166
6.4. Perturbation function z = w (y) with domain X of
Example 6.4 .............................................. 167
6.5. Domain X1 in Example 6.4.. 167
6.6. Perturbation function with domain X1 of Example 6.4 ...... 168
6.7. Perturbation function with domain X11 of Example 6.4 ...... 168
6.8. Perturbation function with domain X21 of Example 6.4 ...... 169
6.9. Partition of A \B ........................................ 170
6.10.Structural diagram of the convergent Lagrangian and
domain cut method under a branch-and-bound framework ..... 175
6.11.Domain X and the feasible region of Example 6.5 .......... 179
6.12.A series system with n components ........................ 189
6.13.A series system with redundancies ........................ 189
7.1. The perturbation function of Example 7.4 ................. 225
7.2. The perturbation function of problem (7.3.1) ............. 226
7.3. The perturbation function of problem (7.3.2) ............. 227
8.1. Contour cuts for case (a) ................................ 244
8.2. Contour cuts for case (b) ................................ 245
8.3. Perturbation function of Example 8.1 ..................... 246
8.4. Domain X and the objective contour cuts .................. 247
8.5. The revised domain X1 .................................... 248
8.6. Perturbation function of the revised problem on X1 ....... 248
8.7. Set Z1 = X \ Q1 .......................................... 258
8.8. Sets X1 = Y1 \ {x2} and Q2(x1) ............................ 258
9.1. Feasible region of the Example 9.2 ....................... 276
9.2. Illustration of Iteration 1 of Algorithm 9.2 for
Example 9.2 .............................................. 276
9.3. The nonconvex function h(x) .............................. 281
9.4. The convexified function/ht (y) with t defined
in (9.3.11) and p = 2 .................................... 281
9.5. The convexified function ht (y) with t defined in
(9.3.12) and p = 5 ....................................... 282
9.6. Feasible region of Example 9.3 ........................... 284
9.7. Convexified feasible region of Example 9.3 ............... 284
9.8. A 12-link complex reliability system ..................... 287
12.1.Diagram of revised Taha's method ......................... 358
12.2.Diagram of the p-norm surrogate-constraint algorithm ..... 365
13.1.Example 13.1 of {MINLP) .................................. 375
13.2.Branch-and-bound search tree for Example 13.1 ............ 376
13.3.Branch-and-bound search tree for Example 13.3 ............ 378
14.1.Illustrations of Vμ1(y), Vμ2(y), Aμ1(y) = у•Vμ1(y) and
Aμ2(y) = у•Vμ2(y) in Example with с = μ = 0.5
andr = l ................................................. 402
14.2.Illustration of the discrete global descent function ..... 409
List of Tables
1.1. Multiple discrete local minimizers of a convex function .... 9
6.1. Values of Pm(z) in dynamic programming for Example
6.3 ...................................................... 165
6.2. List of noninferior points for a 4-subsystem problem ..... 194
6.3. Comparison of node selection rules (n = 200, m = 1) ...... 200
6.4. Numerical results for {QP1) with single constraint ....... 200
6.5. Numerical results for (QP2) with single constraint ....... 201
6.6. Numerical results for (POLY) with single constraint ...... 201
6.7. Numerical results for (SAMP) with single constraint ...... 201
6.8. Numerical results for (LCROP) with single constraint ..... 202
6.9. Numerical results for (LCOST) with single constraint ..... 202
6.10.Numerical results for (QP1) with multiple constraints .... 203
6.11.Numerical results for (QP2) with multiple constraints .... 203
6.12.Numerical results for (POLY) with multiple constraints ... 203
6.13.Numerical results for (SAMP) with multiple constraints ... 204
6.14.Numerical results for (LCROP) with multiple
constraints .............................................. 204
6.15.Numerical results for (CCKP) ............................. 204
6.16.Comparison results for convex knapsack problems .......... 205
6.17.Comparison results for nonconvex knapsack problems ....... 206
6.18.Comparison results for multidimensional knapsack
problems ................................................. 207
7.1. Solution process for Example7.1 using backward dynamic
programming .............................................. 213
7.2. Solution process for Example 7.1 using forward dynamic
programming .............................................. 214
7.3. Dynamic programming table for Example 7.2 ................ 217
Domination and upper bounds at Iteration 1 of
Algorithm 7.1 for Example 7.3 ............................ 223
Domination and upper bounds at Iterati on 2 of
Algorithm 7.1 for Example 7.3 ............................ 224
7.6. Iteration process of Example 7.5 ......................... 235
7.7. Numerical results for (PIP) (r = 0.62) ................... 238
7.8. Numerical results for (QIPi) (r = 0.62) .................. 238
7.9. Numerical results for (QIPLi) (r = 0.65) ................. 238
7.10.Numerical results for (QIP2) (r = 0.70) .................. 239
7.11.Numerical results for [QIPL2) (r = 0.70) ................. 239
8.1. Coefficients in the test problems for Algorithm 8.1
and its extensions ....................................... 259
8.2. Numerical results for convex q(x) (r = 0.6) .............. 261
8.3. Numerical results for concave q(x) (r = 0.6) ............. 261
8.4. Numerical results for indefinite q(x) (r = 0.6) .......... 262
8.5. Numerical results for problem (SMV) ...................... 262
8.6. Comparison results for convex problems ................... 263
8.7. Comparison results for nonconvex problems ................ 264
9.1. Numerical results for test problems with a polynomial
objective function ....................................... 288
9.2. Numerical results for test problems with a quadratic
objective function ....................................... 288
9.3. Numerical results for test problems with a mini max ob
jective function ......................................... 288
9.4. Numerical results for the reliability optimization
problem of the 12-link complex network ................... 289
9.5. Comparison results for problems with a minimax ob
jective function (n = 15) for different m ................ 289
9.6. Comparison results of the discrete polyblock method ...... 290
10.1.Illustrative example of mapping g\ ....................... 303
12.1.Numerical results with the revised Taha's algorithm
(r = 0.5) ................................................ 371
12.2.Numerical results with the objective level cut algorithm
(r = 0.5) ................................................ 372
12.3.Numerical results with the p-th power surrogate algorithm
(r = 0.5) ................................................ 372
13.1.Summary of the branch-and-bound method for
Example 13.3 ............................................. 377
13.2.Solution process of the GBD method for Example 13.3 ...... 383
13.3.Solution process of the OA method for Example 13.3 ....... 389
14.1.U1 and U2 local minimizers for
Example 1.1 .............................................. 399
14.2.Numerical results for Problems 14.1-14.5 ................. 417
|
