2
$\begingroup$

Recently, I came across an optimization problem with binary decision variables which was constrained with a set of first-order differential equations (resulting from a continuous-time Markov chain model). The objective function is the sum of a partial set of probabilities which are obtained via the set of first-order differential equations. The binary variables are imposing whether a transition is possible from one state to another states according to a specific state transition diagram.

As there are solution approaches for solving a first-order differential equation system, a simple solution approach to this problem would be to search on the feasible region of binary decision variables and solve the resulting first-order differential equation system to obtain the objective function value. However, I'm still wondering if there are any exact solution method.

So, my question is two-folds:

  1. What are the other (preferably, exact) available solution approaches for tackling such problem?

  2. Is there any solver (open-source or commercial) for this kind of problem?

Any reference on introduction to modeling and solving these kind of problems is highly appreciated.

ps. I have seen some sources on optimization problems constrained with partial differential equations, which seems to be rooted in control theory. Are there any relation between these two types of problems?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Regarding my own method, it is not an exact method as I was actually talking about a local search method such as SA and TS. I've already thought about a branch & bound method, however I've had no success in finding a proper lower bound yet. Without a good lower bound, the branch & bound is doomed to searching all the feasible region. $\endgroup$ – Ehsan Aug 1 '12 at 11:24
0
$\begingroup$

The "discretize, then optimize" approach that Geoff mentioned is part of the APM MATLAB or APM Python packages that solve mixed-integer differential algebraic equation systems. We're developing this software in our research group at Brigham Young University. Below is a link to a presentation that we published recently at the 2012 INFORMS conference that gives more details and a couple example applications.

Hedengren, J.D., Mojica, J.L., Cole, W., Edgar, T.F., APOPT: MINLP Solver for Differential Algebraic Systems with Benchmark Testing, INFORMS National Meeting, Phoenix, AZ, Oct 2012.

There are a number of tutorial videos on the APMonitorCom YouTube channel if you are interested in numerical solution to these types of problems.

$\endgroup$
  • $\begingroup$ John, I appreciate that you're participating in the community with well thought-out answers, but this and several others you posted feel spammy to me, especially because you have been around long enough to know that you must disclose your affiliation as a developer of ADOPT in situations like this. $\endgroup$ – Aron Ahmadia May 10 '13 at 11:14
  • $\begingroup$ Aron, thanks for your feedback. I assumed that the above reference would disclose who is working on the APOPT solver both from the development and testing side. I noticed in this post that there still wasn't an answer to question #2. $\endgroup$ – John Hedengren May 10 '13 at 15:43
  • $\begingroup$ John, I appreciate you modifying your answer. See here for a discussion of how I approached this while I was moderator here, as well as a link to the official Stack Exchange policy. $\endgroup$ – Aron Ahmadia May 10 '13 at 20:37
  • $\begingroup$ Aron, thanks for the link and the additional explanation. $\endgroup$ – John Hedengren May 11 '13 at 5:35
  • $\begingroup$ To follow up on Aron's remarks, although it's annoying, every time you recommend using your software, you should disclose your affiliation. It's annoying, but it's the site policy because people rarely look elsewhere. $\endgroup$ – Geoff Oxberry May 11 '13 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.