This thesis studies three approaches for solving linear programs with complementarity constraints (LPCC). The focus of Chapter 2 lies on difference-of-convex (DC) penalty formulations and the associated difference-of-convex algorithm (DCA) for computing stationary solutions of LPCCs. We concentrate on three such formulations and establish connections between their stationary solutions and those of the LPCC. Additionally, improvements of the DCA are proposed to remedy certain drawbacks in a straightforward adaptation of the DCA to these formulations. Extensive numerical results, including comparisons with an existing nonlinear programming solver and the mixed-integer formulation, are presented to elucidate the effectiveness of the overall DC approach.', 'On Chapter 3 we present a global optimization algorithm for LPCCs, based on a logical Benders approach introduced by Hu et al. (2008). Complementarity pieces are selected from an ever-updating branch-and-bound tree formed from satisfiability clauses, and then discarded by means of a hybrid cut generating procedure which combines an $\\ell_1$-norm formulation with a sequential sparsification process. Numerical results show that the number of iterations decreases as compared with the base method.', 'Finally, Chapter 4 shows a numerical study for a global-local approach to find good quality local optima for stochastic LPCCs derived from stochastic linear bilevel programs with \\textit{here-and-now} and \\textit{wait-and-see} outer and inner level decisions, respectively. We approach the stochastic problem via Sample Average Approximation and we analyze how local solvers for LPCC perform when the starting point is the global solution of a subsampled LPCC, in terms of their proximity to the global solution of the stochastic LPCC. Experiments on a Bilevel Network Newsvendor Problem allow us to present a simple technique to improve the solutions provided by the local solvers by taking advantage of degeneracy of the inner level problems.

Last modified

• 10/14/2019

Creator

• Francisco Ivan Jara Moroni

DOI

• https://doi.org/10.21985/n2-86kj-yn55

Subject

• Industrial Engineering and Management Sciences

Keyword

• Algorithms
• Bilevel programming
• global optimization
• stationary
• difference of convex
• Complementarity constraints

Date created

• 2018-01-01

Resource type

• Dissertation

Rights statement

• In Copyright