Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Convex Relaxations in Mixed-Integer Optimization - Methods and Control Applications


R. Vujanic


Systems that involve discrete components (e.g., on/off decisions, switches and symbolic reasoning) and continuous quantities (such as physical measurements of voltages, concentrations and positions in space) arise in several practical and industrial contexts. However, when decision problems associated to these systems are cast as mathematical optimization problems, the resulting models are affected by severe computational challenges. Even modest problem sizes can be unsolvable by general purpose solvers when the models contain discrete variables. Further, the required computation time and memory can vary significantly between two instances of the same size, which hinders the practitioners' ability in allocating sufficient computational resources when such optimization problems have to be solved repeatedly -- as is typically the case in a control context. These impediments significantly inhibit the usefulness of discrete models in practical applications.

To alleviate these difficulties, in this Thesis we have developed computational schemes to obtain approximate solutions for several problem structures that are of wide practical interest. They are computationally attractive, and equipped with guarantees on the approximation strength.

Two main approaches are used in order to derive our schemes.

The Lagrangian duality framework is the first, and it is used to tackle large scale, structured optimization problems. The ever increasing availability of large amounts of data and communication (the ``big data'' revolution), as well as the appeal in operating more efficiently large engineered systems, such as power systems, are some of the reasons why large scale optimization is flourishing. The Lagrangian duality framework is useful in this context because it allows one to decompose the problem in smaller pieces, but in contrast to the convex counterpart, when applied to models with discrete decisions (mixed-integer optimization problems) it is generally unable to produce global optimal solutions. In fact, the solutions recovered may not only be suboptimal, but even infeasible. In this Thesis we derive new structural properties of the solutions that can be recovered from the dual, and using these results we develop solution methods that are guaranteed to produce globally feasible solutions in a distributed fashion. They are simple to implement and the quality of the solutions they produce improves (in relative terms) as the size of the problems is increased. Roughly speaking, the reason why we can achieve this is that these instances resemble more and more convex problems the larger they become. We illustrate the efficacy of our methods with extensive experimentations on problems stemming from power systems management and supply chain optimization.

The second approach is based on linear relaxations, and it is used in the context of optimizing systems affected by uncertainty. We investigate two structures in this setting.

In the first one, we look into problems affected by endogenous uncertainty, i.e., by uncertainty that depends on the decisions taken. We derive a robust counterpart in this case, and show how this framework can be useful for scheduling problems. As an illustrative example, we study the problem of integrating industrial power consumers in network reserve mechanisms.

The second one is related to the robust control of mixed-integer input linear systems. We derive a control scheme in which the mixed-integer optimal control problem is first relaxed, and a projection function is applied to the resulting relaxed control sequence. This procedure rectifies it into a solution satisfying the integrality conditions on the inputs, while state constraints satisfaction is guaranteed by applying a robust reformulation of the problem. The key ingredient here is the design of a suitable projection function. We find the class of Pulse-Width-Modulated (PWM) systems particularly well suited for this approach: we provide a projection function for this case and demonstrate how our controller performs on different converter topologies. The results indicate a substantial performance improvement with respect to a plain MPC implementation -- at the same computational cost. We finally investigate approaches to reduce the necessary conservatism by adapting the idea of affine recourse for the robust control of MLD hybrid systems.


Type of Publication:

(03)Ph.D. Thesis

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@PhDThesis { Xxx:2014:IFA_5067,
    author={R. Vujanic},
    title={{Convex Relaxations in Mixed-Integer Optimization - Methods
	  and Control Applications}},
Permanent link