DrAmpl: a meta solver for optimization problem analysis

Optimization problems modeled in the AMPL modeling language (Fourer et al., in AMPL: a modeling language for mathematical programming, 2002) may be examined by a set of tools found in the AMPL Solver Library (Gay, in Hooking your solver to AMPL, 1997). DrAmpl is a meta solver which, by use of the AMPL Solver Library, dissects such optimization problems, obtains statistics on their data, is able to symbolically prove or numerically disprove convexity of the functions involved and provides aid in the decision for an appropriate solver. A problem is associated with a number of relevant solvers available on the NEOS Server for Optimization (Czyzyk et al., in IEEE J Comput Sci Eng 5:68–75, 1998) by means of a relational database. We describe the need for such a tool, the design of DrAmpl and some of its consequences, and keep in mind that a similar tool could be developed for other algebraic modeling languages.     

A Progressive Hedging based branch-and-bound algorithm for mixed-integer stochastic programs

Progressive Hedging (PH) is a well-known algorithm for solving multi-stage stochastic convex optimization problems. Most previous extensions of PH for mixed-integer stochastic programs have been implemented without convergence guarantees. In this paper, we present a new framework that shows how PH can be utilized while guaranteeing convergence to globally optimal solutions of mixed-integer stochastic convex programs. We demonstrate the effectiveness of the proposed framework through computational experiments.     

Mixing mixed-integer inequalities

Mixed-integer rounding (MIR) inequalities play a central role in the development of strong cutting planes for mixed-integer programs. In this paper, we investigate how known MIR inequalities can be combined in order to generate new strong valid inequalities.?Given a mixed-integer region S and a collection of valid “base” mixed-integer inequalities, we develop a procedure for generating new valid inequalities for S. The starting point of our procedure is to consider the MIR inequalities related with the base inequalities. For any subset of these MIR inequalities, we generate two new inequalities by combining or “mixing” them. We show that the new inequalities are strong in the sense that they fully describe the convex hull of a special mixed-integer region associated with the base inequalities.?We discuss how the mixing procedure can be used to obtain new classes of strong valid inequalities for various mixed-integer programming problems. In particular, we present examples for production planning, capacitated facility location, capacitated network design, and multiple knapsack problems. We also present preliminary computational results using the mixing procedure to tighten the formulation of some difficult integer programs. Finally we study some extensions of this mixing procedure. Received: April 1998 / Accepted: January 2001?Published online April 12, 2001     

A structure-conveying modelling language for mathematical and stochastic programming

We present a structure-conveying algebraic modelling language for mathematical programming. The proposed language extends AMPL with object-oriented features that allows the user to construct models from sub-models, and is implemented as a combination of pre- and post-processing phases for AMPL. Unlike traditional modelling languages, the new approach does not scramble the block structure of the problem, and thus it enables the passing of this structure on to the solver. Interior point solvers that exploit block linear algebra and decomposition-based solvers can therefore directly take advantage of the problem’s structure. The language contains features to conveniently model stochastic programming problems, although it is designed with a much broader application spectrum.     

Inexact Restoration for Euler Discretization of Box-Constrained Optimal Control Problems

The Inexact Restoration method for Euler discretization of state and control constrained optimal control problems is studied. Convergence of the discretized (finite-dimensional optimization) problem to an approximate solution using the Inexact Restoration method and convergence of the approximate solution to a continuous-time solution of the original problem are established. It is proved that a sufficient condition for convergence of the Inexact Restoration method is guaranteed to hold for the constrained optimal control problem. Numerical experiments employing the modelling language AMPL and optimization software Ipopt are carried out to illustrate the robustness of the Inexact Restoration method by means of two computationally challenging optimal control problems, one involving a container crane and the other a free-flying robot. The experiments interestingly demonstrate that one might be better-off using Ipopt as part of the Inexact Restoration method (in its subproblems) rather than using Ipopt directly on its own.     

Direct methods with maximal lower bound for mixed-integer optimal control problems

Many practical optimal control problems include discrete decisions. These may be either time-independent parameters or time-dependent control functions as gears or valves that can only take discrete values at any given time. While great progress has been achieved in the solution of optimization problems involving integer variables, in particular mixed-integer linear programs, as well as in continuous optimal control problems, the combination of the two is yet an open field of research. We consider the question of lower bounds that can be obtained by a relaxation of the integer requirements. For general nonlinear mixed-integer programs such lower bounds typically suffer from a huge integer gap. We convexify (with respect to binary controls) and relax the original problem and prove that the optimal solution of this continuous control problem yields the best lower bound for the nonlinear integer problem. Building on this theoretical result we present a novel algorithm to solve mixed-integer optimal control problems, with a focus on discrete-valued control functions. Our algorithm is based on the direct multiple shooting method, an adaptive refinement of the underlying control discretization grid and tailored heuristic integer methods. Its applicability is shown by a challenging application, the energy optimal control of a subway train with discrete gears and velocity limits.      

PySP: modeling and solving stochastic programs in Python

Although stochastic programming is a powerful tool for modeling decision-making under uncertainty, various impediments have historically prevented its wide-spread use. One factor involves the ability of non-specialists to easily express stochastic programming problems as extensions of their deterministic counterparts, which are typically formulated first. A second factor relates to the difficulty of solving stochastic programming models, particularly in the mixed-integer, non-linear, and/or multi-stage cases. Intricate, configurable, and parallel decomposition strategies are frequently required to achieve tractable run-times on large-scale problems. We simultaneously address both of these factors in our PySP software package, which is part of the Coopr open-source Python repository for optimization; the latter is distributed as part of IBM’s COIN-OR repository. To formulate a stochastic program in PySP, the user specifies both the deterministic base model (supporting linear, non-linear, and mixed-integer components) and the scenario tree model (defining the problem stages and the nature of uncertain parameters) in the Pyomo open-source algebraic modeling language. Given these two models, PySP provides two paths for solution of the corresponding stochastic program. The first alternative involves passing an extensive form to a standard deterministic solver. For more complex stochastic programs, we provide an implementation of Rockafellar and Wets’ Progressive Hedging algorithm. Our particular focus is on the use of Progressive Hedging as an effective heuristic for obtaining approximate solutions to multi-stage stochastic programs. By leveraging the combination of a high-level programming language (Python) and the embedding of the base deterministic model in that language (Pyomo), we are able to provide completely generic and highly configurable solver implementations. PySP has been used by a number of research groups, including our own, to rapidly prototype and solve difficult stochastic programming problems.     

Extensions of the generalized moment theorem and applications to distributed-parameter control systems

In this paper, we present extensions to the generalized moment theorem and apply it to optimal control problems for a certain class of distributed-parameter systems. We also apply it to the time-optimal control problem and extend the results of Ref. 1 pertaining to the largest controllable set, so that we can discuss the problem of recoverability for some distributed-parameter systems.The author wishes to express his gratitude to Professor P. K. C. Wang for his guidance and suggestions.     

Sample approximation technique for mixed-integer stochastic programming problems with expected value constraints

This paper deals with the theory of sample approximation techniques applied to stochastic programming problems with expected value constraints. We extend the results of Branda (Optimization 61(8):949–968, 2012c) and Wang and Ahmed (Oper Res Lett 36:515–519, 2008) on the rates of convergence to the problems with a mixed-integer bounded set of feasible solutions and several expected value constraints. Moreover, we enable non-iid sampling and consider Hölder-calmness of the constraints. We derive estimates on the sample size necessary to get a feasible solution or a lower bound on the optimal value of the original problem using the sample approximation. We present an application of the estimates to an investment problem with the Conditional Value at Risk constraints, integer allocations and transaction costs.     

Memory-efficient Implementation of Riccati Approach for Time-Dependent Optimal Control Problems in ODEs

We consider a time-dependent optimal control problem, where the state evolution is described by an ODE. There is a variety of methods for the treatment of such problems. We prefer to view them as boundary value problems and apply to them the Riccati approach for non-linear BVPs with separated boundary conditions. There are many relationships between multiple shooting techniques, the Riccati approach and the Pantoja method, which describes a computationally efficient stage-wise construction of the Newton direction for the discrete-time optimal control problem. We present an efficient implementation of this approach. Furthermore, the well-known checkpointing approach is extended to a ‘nested checkpointing’ for multiple transversals. Some heuristics are introduced for an efficient construction of nested reversal schedules. We discuss their benefits and compare their results to the optimal schedules computed by exhaustive search techniques. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Modeling languages and Condor: metacomputing for optimization

A generic framework is postulated for utilizing the computational resources provided by a metacomputer to concurrently solve a large number of optimization problems generated by a modeling language. An example of the framework using the Condor resource manager and the AMPL and GAMS modeling languages is provided. A mixed integer programming formulation of a feature selection problem from machine learning is used to test the mechanism developed. Due to this application’s computational requirements, the ability to perform optimizations in parallel is necessary in order to obtain results within a reasonable amount of time. Details about the simple and easy to use tool and implementation are presented so that other modelers with applications generating many independent mathematical programs can take advantage of it to significantly reduce solution times. Received: October 28, 1998 / Accepted: December 01, 1999?Published online June 8, 2000     

Furtivity and Masking Problems in Time-Dependent Electromagnetic Obstacle Scattering

In this paper, we consider furtivity and masking problems in time-dependent three-dimensional electromagnetic obstacle scattering. That is, we propose a criterion based on a merit function to minimize or to mask the electromagnetic field scattered by a bounded obstacle when hit by an incoming electromagnetic field and, with respect to this criterion, we drive the optimal strategy. These problems are natural generalizations to the context of electromagnetic scattering of the furtivity problem in time-dependent acoustic obstacle scattering presented in Ref. 1. We propose mathematical models of the furtivity and masking time-dependent three-dimensional electromagnetic scattering problems that consist in optimal control problems for systems of partial differential equations derived from the Maxwell equations. These control problems are approached using the Pontryagin maximum principle. We formulate the first-order optimality conditions for the control problems considered as exterior problems defined outside the obstacle for systems of partial differential equations. Moreover, the first-order optimality conditions derived are solved numerically with a highly parallelizable numerical method based on a perturbative series of the type considered in Refs. 2–3. Finally, we assess and validate the mathematical models and the numerical method proposed analyzing the numerical results obtained with a parallel implementation of the numerical method in several experiments on test problems. Impressive speedup factors are obtained executing the algorithms on a parallel machine when the number of processors used in the computation ranges between 1 and 100. Some virtual reality applications and some animations relative to the numerical experiments can be found in the website http://www.econ.unian.it/recchioni/w10/.     

MPC for the Burgers Equation Based on an LQG Design

We consider optimal control problems for semilinear parabolic PDEs where process and measurement noise can occur. We discuss the solution of such problems by using a Model Predictive Control (MPC) strategy. For the resulting sub-problems we will use a Linear Quadratic Gaussian (LQG) design. Thus we will discuss the efficient implementation of the LQG approach since it is the major computational part in the MPC scheme for this class of optimal control problems. We will present some numerical results for the Burgers equation. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Retract rational fields and cyclic Galois extensions

In [23], this author began a study of so-called lifting and approximation problems for Galois extensions. One primary point was the connection between these problems and Noether’s problem. In [24], a similar sort of study was begun for central simple algebras, with a connection to the center of generic matrices. In [25], the notion of retract rational field extension was defined, and a connection with lifting questions was claimed, which was used to complete the results in [23] and [24] about Noether's problem and generic matrices. In this paper we, first of all, set up a language which can be used to discuss lifting problems for very general “linear structures”. Retract rational extensions are defined, and proofs of their basic properties are supplied, including their connection with lifting. We also determine when the function fields of algebraic tori are retract rational, and use this to further study Noether’s problem and cyclic 2-power Galois extensions. Finally, we use the connection with lifting to show that ifp is a prime, then the center of thep degree generic division algebra is retract rational over the ground field. The author is grateful for NSF support under grant #MCS79-04473.     

Realizability of algebraic Galois extensions by strictly commutative ring spectra

We discuss some of the basic ideas of Galois theory for commutative -algebras originally formulated by John Rognes. We restrict our attention to the case of finite Galois groups and to global Galois extensions.

We describe parts of the general framework developed by Rognes. Central rôles are played by the notion of strong duality and a trace mapping constructed by Greenlees and May in the context of generalized Tate cohomology. We give some examples where algebraic data on coefficient rings ensures strong topological consequences. We consider the issue of passage from algebraic Galois extensions to topological ones by applying obstruction theories of Robinson and Goerss-Hopkins to produce topological models for algebraic Galois extensions and the necessary morphisms of commutative -algebras. Examples such as the complex -theory spectrum as a -algebra indicate that more exotic phenomena occur in the topological setting. We show how in certain cases topological abelian Galois extensions are classified by the same Harrison groups as algebraic ones, and this leads to computable Harrison groups for such spectra. We end by proving an analogue of Hilbert's theorem 90 for the units associated with a Galois extension.

     

Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.     

Optimal control problems of parabolic equations with an infinite number of variables and with equality constraints

Email: bahaa_gm{at}hotmail.com Received on December 6, 2005; Accepted on December 7, 2006 Optimal control problems of systems governed by parabolic equationswith an infinite number of variables and with additional equalityconstraints are considered. The extremum principle, as wellas sufficient condition of optimality, is formulated for theNeumann problem by using certain extensions of Dubovitskii–Milyutinmethod.     

The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming

A new deterministic algorithm for solving convex mixed-integer nonlinear programming (MINLP) problems is presented in this paper: The extended supporting hyperplane (ESH) algorithm uses supporting hyperplanes to generate a tight overestimated polyhedral set of the feasible set defined by linear and nonlinear constraints. A sequence of linear or quadratic integer-relaxed subproblems are first solved to rapidly generate a tight linear relaxation of the original MINLP problem. After an initial overestimated set has been obtained the algorithm solves a sequence of mixed-integer linear programming or mixed-integer quadratic programming subproblems and refines the overestimated set by generating more supporting hyperplanes in each iteration. Compared to the extended cutting plane algorithm ESH generates a tighter overestimated set and unlike outer approximation the generation point for the supporting hyperplanes is found by a simple line search procedure. In this paper it is proven that the ESH algorithm converges to a global optimum for convex MINLP problems. The ESH algorithm is implemented as the supporting hyperplane optimization toolkit (SHOT) solver, and an extensive numerical comparison of its performance against other state-of-the-art MINLP solvers is presented.