Disclaimer: I'm not an expert in this field; I've just worked with people who do this sort of thing.
Binary decisions are always solved using a glorified guess-and-check algorithm
Setting aside the differential equations for a moment, any integer component of a mixed-integer linear (or nonlinear) programming solver is probably going to use some sort of branch-and-bound or branch-and-cut approach to solving the mixed-integer part of the problem. These approaches are sophisticated ways to do guess-and-check, and there are pathological cases where every possible value of the binary decision variable will be tested.
The first approach you mentioned is exact (provided you can solve the differential equations exactly), and solves the problem. In practice, I think as long as you can solve the differential equations numerically to high accuracy, you will probably obtain the correct optimal objective function value.
What are the other available solution approaches for tackling such a problem?
There are a few that I know of:
- Discretize, then optimize: Differential equations are typically solved numerically (unless you can construct a solution otherwise), and these numerical solutions are constructed from discrete equations. Also known as a collocation approach, you would essentially pick a quadrature rule (for example, something like a Radau method) along with specified time steps for your differential equations. The quadrature rule and the time steps transform the system of differential equations into a system of nonlinear algebraic equations, so your optimization problem becomes a mixed-integer nonlinear program that you then solve. This approach is probably not exact unless the time step is sufficiently small so that the numerical solution of the ODE is accurate. It generally creates a large system of constraints. Larry Biegler's papers are probably good references for this approach. This approach is also referred to as "collocation".
- Optimize, then discretize: Replace your optimization problem with necessary optimality conditions under constraint qualification. One reformulation uses the Karush-Kuhn-Tucker (KKT) conditions and a Slater point constraint qualification; there are others. Then discretize the resulting KKT conditions and solve. For binary decision variables, I'm not sure how this approach would work, because the KKT conditions don't apply, but if your decision variables were continuous, this approach would make a lot more sense. The KKT conditions are not sufficient for optimality unless the objective function and constraints are convex; generally, ODE-constrained optimization problems do not satisfy these convexity conditions.
- Optimize without discretizing: Construct a sequence of relaxations and restrictions of your original problem while using a branch-and-bound approach similar to that in nonconvex optimization. Paul Barton publishes papers using this approach; he is one of my PhD advisers. This approach is exact, but requires a lot of mathematics and programming infrastructure.
Relationship to PDE-constrained optimization
The first two approaches I mentioned in the list above are also used in PDE-constrained optimization. The third has not yet been developed for the PDE case. I suspect it may be viable, but I don't know if it is.
