Multilevel Optimization: Algorithms and Applications

Researchers working with nonlinear programming often claim "the word is non­ linear" indicating that real applications require nonlinear modeling. The same is true for other areas such as multi-objective programming (there are always several goals in a real application), stochastic programming (all data is uncer­ tain and therefore stochastic models should be used), and so forth. In this spirit we claim: The word is multilevel. In many decision processes there is a hierarchy of decision makers, and decisions are made at different levels in this hierarchy. One way to handle such hierar­ chies is to focus on one level and include other levels' behaviors as assumptions. Multilevel programming is the research area that focuses on the whole hierar­ chy structure. In terms of modeling, the constraint domain associated with a multilevel programming problem is implicitly determined by a series of opti­ mization problems which must be solved in a predetermined sequence. If only two levels are considered, we have one leader (associated with the upper level) and one follower (associated with the lower level).

1 Congested O-D Trip Demand Adjustment Problem: Bilevel Programming Formulation and Optimality Conditions.- 1 Introduction.- 2 Literature Review.- 3 Model Analysis.- 4 Necessary Optimality Conditions of the DAP.- 5 Conclusions.- 2 Determining Tax Credits for Converting Nonfood Crops to Biofuels: An Application of Bilevel Programming.- 1 Introduction.- 2 Mathematical Model.- 3 Description of Algorithms.- 4 Computational Results.- 5 Discussion.- 3 Multilevel Optimization Methods in Mechanics.- 1 Introduction.- 2 Presentation of the Multilevel Decomposition Methods.- 3 Large Cable Structures.- 4 Large Elastoplastic Structures.- 5 Validation and Improvements of Simplified Models.- 6 Extension to other Problems. Decomposition Algorithms for Nonconvex Minimization Problems.- 7 A Multilevel Method for the Approximation of a Nonconvex Minimum Problem by Convex ones.- 8 Multilevel Decomposition into two Convex Problems.- 9 Structures with Fractal Interfaces.- 4 Optimal Structural Design in Nonsmooth Mechanics.- 1 Introduction.- 2 Parametric Nonsmooth Structural Analysis Problems.- 3 Optimal Design Problems.- 4 Mathematical Analysis and Algorithms.- 5 Discussion.- References.- 5 Optimizing the Operations of an Aluminium Smelter Using Non-Linear Bi-Level Programming.- 1 Introduction.- 2 The Mathematical Model of the Aluminium Smelter.- 3 The Solution Algorithm.- 4 The Mathematical Model Representing the Multi-period Operations of the Aluminium Smelter.- 5 Concluding Remarks.- References.- 6 Complexity Issues in Bilevel Linear Programming.- 1 Introduction.- 2 Difficulty in Approximation.- 3 A Special Case Solvable in Polynomial Time.- 4 Regret Ratio in Decision Analysis.- 5 Future Directions.- References.- 7 The Computational Complexity of Multi-Level Bottleneck Programming Problems.- 1 Introduction.- 2 Problem Statement and Previous Complexity Results.- 3 Hardness Proof for Multi-Level Bottleneck Programs.- 4 Hardness Proof for Multi-Level Linear Programs.- 5 The Complexity of Bi-Level Programs.- 6 Discussion.- References.- 8 On the Linear Maxmin and Related Programming Problems.- 1 Introduction.- 2 Reformulations.- 3 Tools for Resolution.- 4 Solving the Linear Maxmin Problem.- 9 Piecewise Sequential Quadratic Programming for Mathematical Programs with Nonlinear Complementarity Constraints.- 1 Introduction.- 2 Application to Optimal Design of Mechanical Structures.- 3 The Piecewise Smooth Approach to NCP-MP.- 4 The PSQP Method for NCP-MPEC.- 5 Computational Testing of PSQP.- References.- 10 A New Branch and Bound Method for Bilevel Linear Programs.- 1 Introduction.- 2 The Equivalent Reverse Convex Program.- 3 Solution Method.- 4 Implementation Issues.- 5 Illustrative Example.- 11 A Penalty Method for Linear Bilevel Programming Problems.- 1 Introduction.- 2 Linear Bilevel Programming Problem.- 3 The Method.- 4 Globalization of the Solution.- 5 Numerical Examples.- 6 Concluding Remarks.- 12 An Implicit Function Approach to Bilevel Programming Problems.- 1 Introduction.- 2 Lipschitz Continuity of Optimal Solutions.- 3 Application of the Bundle Method.- 4 Non-uniquely Solvable Lower Level Problems.- 5 Nonconvex Lower Level Problems and Coupling Constraints in the Upper Level Problem.- 13 Bilevel Linear Programming, Multiobjective Programming, and Monotonic Reverse Convex Programming.- 1 Introduction.- 2 Optimization over the Efficient Set.- 3 Bilevel Linear Programming.- 4 Basic Properties of (FMRP).- 5 Different D.C. Approaches to (FMRP).- 14 Existence of Solutions to Generalized Bilevel Programming Problem.- 1 Introduction.- 2 Notations and Preliminaries.- 3 Parametric Implicit Variational Problem.- 4 Existence Results for Generalized Bilevel Problems.- 5 Final Remarks.- 15 Application of Topological Degree Theory to Complementarity Problems.- 1 Problem Specification and Topological Degree Theory.- 2 General Complementarity Problem.- 3 Sufficient Conditions for Solution Existence.- 4 Standard Complementarity Problem.- 5 Implicit Complementarity Problem.- 6 General Order Complementarity Problem.- References.- 16 Optimality and Duality in Parametric Convex Lexicographic Programming.- 1 Introduction.- 2 Orientation.- 3 Continuity.- 4 Global Optimality.- 5 Local Optimality.- 6 Duality.- 7 Bilevel Zermelo’s Problems.