MPC

MPC 2013, ISSUE 3



Mathematical Programming Computation, Volume 5, Issue 3, September 2013

TACO: a toolkit for AMPL control optimization

Christian Kirches, Sven Leyffer

We describe a set of extensions to the AMPL modeling language to conveniently model mixed-integer optimal control problems forODEorDAE dynamic processes. These extensions are realized as AMPL user functions and suffixes and do not require intrusive changes to theAMPL language standard or implementation itself. We describe and provide TACO, a Toolkit for AMPL Control Optimization that reads AMPL stub.nl files and detects the structure of the optimal control problem. This toolkit is designed to facilitate the coupling of existing optimal control software packages to AMPL.We discuss requirements, capabilities, and the current implementation. Using the example of the multiple shooting code for optimal control MUSCOD-II, a direct and simultaneous method for DAE-constrained optimal control, we demonstrate how the problem information provided by the TACO toolkit is interfaced to the solver. In addition, we show how the MS-MINTOC algorithm for mixed-integer optimal control can be used to efficiently solve mixed-integer optimal control problems modeled in AMPL. We use the AMPL extensions to model three control problem examples and we discuss how those extensions affect the representation of optimal control problems. Solutions to these problems are obtained by usingMUSCOD-II and MS-MINTOC inside the AMPL environment. A collection of further AMPL control models is provided on the web site http://mintoc.de. MUSCOD-II and MS-MINTOC have been made available on the NEOS Server for Optimization, using the TACO toolkit to enable input of AMPL models

Full Text: PDF



Mathematical Programming Computation, Volume 5, Issue 3, September 2013

GPU accelerated greedy algorithms for compressed sensing

Jeffrey D. Blanchard, Jared Tanner

For appropriate matrix ensembles, greedy algorithms have proven to be an efficient means of solving the combinatorial optimization problem associated with compressed sensing. This paper describes an implementation for graphics processing units (GPU) of hard thresholding, iterative hard thresholding, normalized iterative hard thresholding, hard thresholding pursuit, and a two-stage thresholding algorithm based on compressive sampling matching pursuit and subspace pursuit. The GPU acceleration of the former bottleneck, namely the matrix–vector multiplications, transfers a significant portion of the computational burden to the identification of the support set. The software solves high-dimensional problems in fractions of a second which permits large-scale testing at dimensions currently unavailable in the literature. The GPU implementations exhibit up to 70× acceleration over standard Matlab central rocessing unit implementations using automatic multi-threading.

Full Text: PDF



Mathematical Programming Computation, Volume 5, Issue 3, September 2013

A hybrid branch-and-bound approach for exact rational mixed-integer programming

William Cook, Thorsten Koch, Daniel E. Steffy, Kati Wolter

We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and theGMParithmetic library. Computational results are presented for a suite of test instances taken from the Miplib and Mittelmann libraries and for a new collection of numerically difficult instances.

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).