Search

Multiparametric programming and control has received a lot of attention in the past twenty years with significant advances reported in the open literature. Most existing algorithms for multiparametric programming typically suffer from a computational slowdown with respect to the number of parameters, constraints and variables resulting from the large expansion of active set combinations that must be considered. In this work, we present a novel parallel combinatorial algorithm for the solution of multiparametric Quadratic programs (mpQP) and multiparametric Linear Programs (mpLP) (i), generating better exploration rules that greatly reduces the number of active set combinations that must be considered and (ii) a high-performance parallelization scheme for this algorithm that scales well with the number of cores. The proposed algorithm is validated on numerous computational examples, including scaling analysis of the parallel algorithm up to 48 CPU cores and generating optimal Pareto fronts for the Markowitz Portfolio Selection Problem. In large problem instances, speedups of over a factor of 500 are observed. [ABSTRACT FROM AUTHOR]

• Proposed parameter transformation yields mp-QP problems with special topology properties. • New solution strategy enabled by parameter transformation. • Solution delivered as two compact statements, or optionally, in the classic explicit format. • Significant improvements on speed of calculation and size of offline solutions. • New framework for the analysis and calculation of multiparametric problems. An innovative paradigm is presented in this paper for convex multiparametric quadratic programming (mp-QP), and made possible by a convenient transformation of the vector of parameters, and expansion of the corresponding parameter space. Solutions of mp-QP problems are now presented in a highly compact form, in place of deriving explicit expressions for all critical regions and optimizer functions, as is the standard practice in the field. This represents two significant advantages over the state-of-the art mp-QP algorithms: firstly, this paradigm offers a much less expensive path for solution calculation; secondly, these compact solutions require minimal storage requirements. This is particularly significant for mp-QP problems including many inequality constraints, which can now be addressed with minimal computational burden. Compact solutions may then be explored to obtain the explicit solutions for the original mp-QP problems if required, where the original parameter dependence and bounds are recovered. [ABSTRACT FROM AUTHOR]

Abstract: This work presents a methodology to derive explicit multiparametric controllers for nonlinear systems, combining model approximation techniques and multiparametric model predictive control (mp-MPC) algorithms. Particular emphasis is given to an approach that applies a nonlinear model reduction technique, based on balancing of empirical gramians, which generates a reduced order model suitable for nonlinear mp-MPC algorithms. This approach is compared with a recently proposed method that uses a meta-modelling based model approximation technique which can be directly combined with standard multiparametric programming algorithms. The methodology is illustrated for two nonlinear models, of a distillation column and a train of CSTRs, respectively. [Copyright &y& Elsevier]

Abstract: This paper proposes an explicit solution to the model predictive control of linear systems subject to non-convex polyhedral constraints. These constraints are modeled as the union of a finite number of convex polyhedra. The algorithm is based on calculating the explicit solution to a modified problem with linear constraints defined as the convex hull of the original ones and classifying its regions by their relation with the regions of the explicit solution to the original problem. Some of the regions are divided, and a procedure based on sum-of-squares programming is designed to determine which of the possible solutions are in fact optimal. Finally, the online algorithm is shown to be better in terms of computational cost and memory requirements than an algorithm based on obtaining and comparing the solutions of the problem using as constraints the polyhedra whose union forms the non-convex regions, both theoretically and by the results of an example. [Copyright &y& Elsevier]

Abstract: This work introduces two algorithms for the solution of pure integer and mixed-integer bilevel programming problems by multiparametric programming techniques. The first algorithm addresses the integer case of the bilevel programming problem where integer variables of the outer optimization problem appear in linear or polynomial form in the inner problem. The algorithm employs global optimization techniques to convexify nonlinear terms generated by a reformulation linearization technique (RLT). A continuous multiparametric programming algorithm is then used to solve the reformulated convex inner problem. The second algorithm addresses the mixed-integer case of the bilevel programming problem where integer and continuous variables of the outer problem appear in linear or polynomial forms in the inner problem. The algorithm relies on the use of global multiparametric mixed-integer programming techniques at the inner optimization level. In both algorithms, the multiparametric solutions obtained are embedded in the outer problem to form a set of single-level (M)(I)(N)LP problems – which are then solved to global optimality using standard fixed-point (global) optimization methods. Numerical examples drawn from the open literature are presented to illustrate the proposed algorithms. [ABSTRACT FROM AUTHOR]

This paper presents a solution method for the general (mixed integer) parametric linear complementarity problem pLCP( q( θ), M), where the matrix M has a general structure and integrality restriction can be enforced on the solution. Based on the equivalence between the linear complementarity problem and mixed integer feasibility problem, we propose a mixed integer programming formulation with an objective of finding the minimum 1-norm solution for the original linear complementarity problem. The parametric linear complementarity problem is then formulated as multiparametric mixed integer programming problem, which is solved using a multiparametric programming algorithm. The proposed method is illustrated through a number of examples. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we present recent developments in multiparametric nonlinear programming. For the case of convex problems, we highlight key issues regarding the full characterization of the parametric solution space and we discuss, through an illustrative example problem, four alternative state-of-the-art multiparametric nonlinear programming algorithms. We also identify a number of main challenges for the non-convex case and highlight future research directions. [Copyright &y& Elsevier]

The multiparametric 0-1-Integer Programming (0-1-IP) problem relative to the objective function is a family of 0-1-IP problems which are related by having identical constraint matrix and righthand-side vector. In this paper we present an algorithm to perform a complete multiparametric analysis relative to a generalized min max objective function such that the min sum and min max are particular cases. [ABSTRACT FROM AUTHOR]

For multiparametric convex nonlinear programming problems we propose a recursive algorithm for approximating, within a given suboptimality tolerance, the value function and an optimizer as functions of the parameters. The approximate solution is expressed as a piecewise affine function over a simplicial partition of a subset of the feasible parameters, and it is organized over a tree structure for efficiency of evaluation. Adaptations of the algorithm to deal with multiparametric semidefinite programming and multiparametric geometric programming are provided and exemplified. The approach is relevant for real-time implementation of several optimization-based feedback control strategies. [ABSTRACT FROM AUTHOR]

Multiparametric programming considers optimization problems where the data are functions of a parameter vector and describes the optimal value and an optimizer as explicit functions of the parameters. In this paper, we consider a linear program where the right-hand side is an affine function of a parameter vector; we propose an algorithm for approximating its solution. Given a full-dimensional simplex in the parameter space and an optimizer for each simplex vertex, the algorithm formulates the linear interpolation of the given solutions as an explicit function of the parameters, giving a primal feasible approximation of an optimizer inside the simplex. If the resulting absolute error in the objective exceeds a prescribed tolerance, then the algorithm subdivides the simplex into smaller simplices where it applies recursively. We propose both a basic version and a refined version of the algorithm. The basic version is polynomial in the output size, provided a polynomial LP solver is used; the refined version may give a smaller output. A global error bound for the optimizer is derived and some computational tests are discussed. [ABSTRACT FROM AUTHOR]