International Workshop on Hybrid Systems: Modeling, Simulation and Optimization


Invited Speakers

Title:         Time-stepping methods for large scale differential variational inequalities (DVI) in nonsmooth dynamics

Authors:  Mihai Anitescu
                   Mathematics and Computer Science Division, Argonne National Laboratory, USA


We discuss recent advances in time-stepping methods for solving nonsmooth rigid body dynamics with contact and friction. The advantage of such methods is that they do not have to stop at every collision or stick-slip event while converging in a weak sense to the solution of the DVI. We discuss
methods for solving the sub problems, which are optimization problems with conic constraints, arising at each time step. We particularly emphasize an algorithm, recently developed with A. Tasora, that solves them in their dual cone complementarity form with a Gauss Seidel like iteration. We prove that the method is globally convergent. Through numerical experiments, we demonstrate that the method scales linearly with with an increasing size of
the problem and show that it is very competitive for the simulation of granular flow dynamics.


Title:         Semismooth Hybrid Automata

Authors:  Paul I. Barton, Mehmet Yunt
                 Chemical Engineering Department, Massachusetts Institute of Technology, USA


The determination of optimal mode sequences for hybrid systems with autonomous transitions is examined. A class of hybrid systems that exhibit a locally Lipschitz mapping between their parameters and their continuous states is introduced. Lipschitzian optimization methods such as bundle methods are explored for the solution of parametric optimization problems that have this class of hybrid systems embedded.


Title:         MPEC Strategies for Optimization of Chemical Process Dynamics

Authors:  B. T. Baumrucker, Lorenz T. Biegler
    Department of Chemical Engineering, Carnegie Mellon University, USA


With the development and widespread use of large-scale nonlinear programming (NLP) tools for process optimization, there has been an
associated application of NLP formulations with complementarity constraints in order to represent discrete decisions. Also known as
Mathematical Programs with Equilibrium Constraints (MPECs), these formulations can be used to model certain classes of discrete events and can be more efficient than a mixed integer formulation. In this talk, we consider MPEC formulations and solution strategies for
chemical engineering applications, particularly for a dynamic gas pipeline system. The results illustrate the effectiveness of MPEC
strategies as well as some novel operating strategies for pipeline networks.


Title:         Constrained and Distributed Hybrid Control

Authors:  Francesco Borrelli
Department of Mechanical Engineering, University of California at Berkeley, USA


Over the last few years we have focused on the development of distributed controller synthesis techniques for large scale hybrid systems with constraints. There is a wealth of practical problems of this type. However, at present systematic distributed control design for such systems is still at its infancy.
In this seminar I will first summarize our theoretical efforts, starting from constrained optimal control design for single systems. Then, I will show how these results can be used in order to develop a novel theory for distributed constrained optimal control for large scale hybrid systems.
During the talk several applications will be used in order to illustrate the benefits of the proposed approach.

Title:         Reformulations, Relaxations and Cutting Planes for Linear Generalized Disjunctive Programming

Authors:  Nicholas Sawaya, Ignacio E. Grossmann
    Department of Chemical Engineering, Carnegie Mellon University, USA


Generalized disjunctive programming (GDP) is an extension of the well-known disjunctive programming paradigm developed by Balas. The GDP formulation involves Boolean and continuous variables that are specified in algebraic constraints, disjunctions and logic propositions, which is an alternative representation to the traditional mixed integer programming (MIP) formulation. Our research in this class of problems, which has been motivated by its potential for improved modeling and solution methods, has led to the development of customized algorithms that exploit the underlying logical structure of the problem in both the linear and nonlinear cases. However, an outstanding question that has remained is the exact relationship between GDP and disjunctive programming.  In this work, we establish for the linear case new connections between disjunctive programming and generalized disjunctive programming, which provide new theoretical and computational insights that allow us to exploit the rich theory developed Balas. In particular, we propose a novel family of MIP reformulations corresponding to the original GDP model that result in tighter relaxations and stronger cutting planes than reported in previous work. We illustrate this theory on the strip-packing problem for which computational results are presented. We also describe the application of these ideas to the global optimization of bilinear GDP problems.


Title:         Iterative Relaxation Abstraction for Verification and Design of Hybrid Systems

Authors:  Bruce H. Krogh
    Electrical and Computer Engineering, Carnegie Mellon University, USA


Inspired by the success of counterexample guided abstraction refinement (CEGAR) techniques for verification of discrete systems, iterative relaxation abstraction (IRA) combines the capabilities of current tools for analysis of low-dimensional linear hybrid automata (LHA) with the power of linear programming (LP) to verify properties of models that cannot be handled by traditional reachability analysis. On each iteration, a low-dimensional abstraction is constructed using a subset of the continuous variables from the original LHA. Hybrid system reachability analysis generates a representation of all possible paths to forbidden states in the relaxation abstraction.  Infeasibility analysis determines if a path selected from this set represents a valid run of the LHA using the constraints along the path from the original high-dimensional LHA. If the constraints along the path are not feasible, LP techniques identify an irreducible infeasible subset of constraints from which the set of continuous variables is selected for the construction of the next relaxation abstraction. IRA stops if no paths to bad states remain or a legitimate violation of the reachability specification is found.  Following a review the use of LHA to model hybrid systems with linear and nonlinear continuous dynamics, the details of the IRA procedure for verification will be described and illustrated with some examples.  Recent extensions of IRA for parameter optimization will then be presented.


Title:         Analysis and numerical solution of hybrid differential algebraic systems

Authors:  Volker Mehrmann
Institut für Mathematik, Technische Universität Berlin, Germany


We discuss the analysis and numerical solution of hybrid dynamical systems. Our work is motivated by industrial applications arising in the modeling and control of automatic gearboxes. We survey the general theory of over-and underdetermined systems of nonlinear differential algebraic equations and show how this general theory can be extended to hybrid systems. We discuss the issues of consistent initialization after mode switching as well sliding modes. We present several numerical examples and indicate challenges and an outlook for future research.

This is joint work, partially with Peter Hamann (Daimler AG) and Lena Wunderlich (TU Berlin).


Title:         Differential Variational Inequalities and friends

Authors:  David Stewart

                   Department of Mathematics, University of Iowa


Differential Variational Inequalities is a framework for a class of hybrid systems that encompasses or relate to many proposed problems (such as Linear Complementarity Systems, Projected Dynamical Systems, Dynamic Complementarity Problems, and Convolution Complementarity Problems). Existence and uniqueness results have been obtained which will be presented, although there are still large gaps in our understanding of some issues, particularly regarding uniqueness of solutions.  An important indicator of the difficulty of these problems is the index, which will be described and illustrated.