MPC

MPC 2017, ISSUE 4



Mathematical Programming Computation, Volume 9, Issue 4, December 2017

A branch-and-bound algorithm for instrumental variable quantile regression

Guanglin Xu, Samuel Burer

This paper studies a statistical problem called instrumental variable quantile regression (IVQR). We model IVQR as a convex quadratic program with complementarity constraints and—although this type of program is generally NPhard—we develop a branch-and-bound algorithm to solve it globally. We also derive bounds on key variables in the problem, which are valid asymptotically for increasing sample size. We compare our method with two well known global solvers, one of which requires the computed bounds. On random instances, our algorithm performs well in terms of both speed and robustness.

Full Text: PDF



Mathematical Programming Computation, Volume 9, Issue 4, December 2017

Lift-and-project cuts for convex mixed integer nonlinear programs

Mustafa R. Kilinc, Jeff Linderoth, James Luedtke

We describe a computationally effective method for generating lift-and-project cuts for convex mixed-integer nonlinear programs (MINLPs). The method relies on solving a sequence of cut-generating linear programs and in the limit generates an inequality as strong as the lift-and-project cut that can be obtained from solving a cut-generating nonlinear program. Using this procedure, we are able to approximately optimize over the rank one lift-and-project closure for a variety of convex MINLP instances. The results indicate that lift-and-project cuts have the potential to close a significant portion of the integrality gap for convex MINLPs. In addition, we find that using this procedure within a branch-and-cut solver for convex MINLPs significantly reduces the total solution time for many instances.We also demonstrate that combining lift-and-project cuts with an extended formulation that exploits separability of convex functions yields significant improvements in both relaxation bounds and the time to calculate the relaxation. Overall, these results suggest that with an effective separation routine, like the one proposed here, lift-and-project cuts may be as effective for solving convex MINLPs as they have been for solving mixed-integer linear programs.

Full Text: PDF



Mathematical Programming Computation, Volume 9, Issue 4, December 2017

Lifted collocation integrators for direct optimal control in ACADO toolkit

Rien Quirynen, Sebastien Gros, Boris Houska, Moritz Diehl

This paper presents a class of efficient Newton-type algorithms for solving the nonlinear programs (NLPs) arising from applying a direct collocation approach to continuous time optimal control. The idea is based on an implicit lifting technique including a condensing and expansion step, such that the structure of each subproblem corresponds to that of themultiple shooting method for direct optimal control.We establish the mathematical equivalence between the Newton iteration based on direct collocation and the proposed approach, and we discuss the computational advantages of a lifted collocation integrator. In addition, we investigate different inexact versions of the proposed scheme and study their convergence and computational properties. The presented algorithms are implemented as part of the open-source ACADO code generation software for embedded optimization. Their performance is illustrated on a benchmark case study of the optimal control for a chain of masses. Based on these results, the use of lifted collocationwithin direct multiple shooting allows for a computational speedup factor of about 10 compared to a standard collocation integrator and a factor in the range of 10–50 compared to direct collocation using a general-purpose sparse NLP solver.

Full Text: PDF



Mathematical Programming Computation, Volume 9, Issue 4, December 2017

On the computational efficiency of subgradient methods: a case study with Lagrangian bounds

Antonio Frangioni, Bernard Gendron, Enrico Gorgone

Subgradient methods (SM) have long been the preferred way to solve the large-scale Nondifferentiable Optimization problems arising from the solution of Lagrangian Duals (LD) of Integer Programs (IP). Although other methods can have better convergence rate in practice, SM have certain advantages that may make them competitive under the right conditions. Furthermore, SMhave significantly progressed in recent years, and new versions have been proposed with better theoretical and practical performances in some applications.We computationally evaluate a large class of SM in order to assess if these improvements carry over to the IP setting. For this we build a unified scheme that covers many of the SMproposed in the literature, comprised some often overlooked features like projection and dynamic generation of variables. We fine-tune the many algorithmic parameters of the resulting large class of SM, and we test them on two different LDs of the Fixed-Charge Multicommodity Capacitated Network Design problem, in order to assess the impact of the characteristics of the problem on the optimal algorithmic choices. Our results show that, if extensive tuning is performed, SM can be competitive with more sophisticated approaches when the tolerance required for solution is not too tight, which is the case when solving LDs of IPs.

Full Text: PDF




Imprint and privacy statement

For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2020 by Zuse Institute Berlin (ZIB).