We consider an optimization problem for a dynamical system whose evolution depends on a collection of binary decision variables. We develop scalable approximation algorithms with provable suboptimality bounds to provide computationally tractable solution methods even when the dimension of the system and the number of the binary variables are large. The proposed method employs a linear approximation of the objective function such that the approximate problem is defined over the feasible space of the binary decision variables, which is a discrete set. To define such a linear approximation, we propose two different variation methods: one uses continuous relaxation of the discrete space and the other uses convex combinations of the vector field and running payoff. The approximate problem is a 0-1 linear program, which can be solved by existing polynomial-time exact or approximation algorithms, and does not require the solution of the dynamical system. Furthermore, we characterize a sufficient condition ensuring the approximate solution has a provable suboptimality bound. We show that this condition can be interpreted as the concavity of the objective function or that of a reformulated objective function.

+More

continuous relaxation of the discrete space polynomialtime exact or approximation algorithms variation binary decision variables linear approximation of the objective function provable suboptimality bounds method dynamical system optimization problem solution methods convex combinations of the vector field and running

Insoon Yang, Samuel A. Burden, Ram Rajagopal, S. Shankar Sastry, Claire J. Tomlin,.Approximation Algorithms for Optimization of Combinatorial Dynamical Systems. 61 (9),2644-2649.

Insoon Yang, et al."Approximation Algorithms for Optimization of Combinatorial Dynamical Systems" 61

Insoon Yang, Samuel A. Burden, Ram Rajagopal, S. Shankar Sastry, Claire J. Tomlin,"Approximation Algorithms for Optimization of Combinatorial Dynamical Systems"