Mixed Integer Optimal Control

One often encounters problems in which manipulated variables or adjustable parameters must be selected from among a set of discrete values. Examples of discrete variables include ON/OFF state, selection of different feed lines, and other variables that are naturally integers. Many dynamic optimization problems are discrete in nature.

At first glance it might seem solving a discrete variable problem would be easier than a continuous problem. After all, for a variable within a given range, a set of discrete values within the range is finite whereas the number of continuous values is infinite. When searching for an optimum, it seems it would be easier to search from a finite set rather than from an infinite set.

This is not the case, however. Solving discrete problems is harder than continuous problems. This is because of the combinatorial explosion that occurs in all but the smallest problems. For example if we have two variables which can each take 10 values, we have 10*10 = 100 possibilities. If we have 10 variables that can each take 10 values, we have 10^10 possibilities. Even with the fastest computer, it would take a long time to evaluate all of these.

Discrete decision variables are those that have only certain levels or quantities that are acceptable at an optimal solution. Examples of discrete variables are binary (e.g. off/on or 0/1), integer (e.g. 4,5,6,7), or general discrete values that are not integer (e.g. 1/4 cm, 1/2 cm, 1 cm).

Integer Variables in Gekko

Integer variables are defined in Python Gekko with the integer=True option when declaring the variable. A Special Ordered Set is also possible to define discrete options that are not necessarily integers.

x = m.Var(lb=0,ub=1,integer=True) # binary variable (0-1)
y = m.Var(lb=0,ub=8,integer=True) # integer variable (0,1,..,7,8)
z = m.sos1([0.5,1.25,2.5]) # discrete variable (0.5,1.25,2.5)

[$[Get Code]]

Additional mixed-integer tutorials in APMonitor and Gekko.

Integer Variables in APMonitor

Integer or binary variables are defined in the APMonitor Modeling Language by appending a variable name with int. An binary decision variable is an integer variable with bounds between 0 and 1.

 ! Binary decision variable (0 or 1)
 Variables
   int_b >=0 <=1

The range of upper and lower bounds can be increased or decreased to any range to create a more general integer variable.

 ! Integer decision variable (-5 to 10)
 Variables
   int_v >=-5 <=10

Nonlinear programming solvers (such as IPOPT) may not return an integer solution because they are designed for continuous variables. Mixed Integer Nonlinear Programming solvers (such as APOPT) are equipped to solve for binary or integer variables. Select the appropriate solver option to either find an initial solution without integer variables or an integer solution. It is sometimes desirable to find a non-integer solution first because of the often significant reduction in computation time without the integer variables.

Exercise 1

Objective: Solve a discrete optimization problem with the branch and bound technique. Estimated time: 1 hour.

Branch and Bound Exercise (pdf)

Solution

The integer problem is solved with Python GEKKO. The option integer=True is used to switch the variable from continuous to integer form. The APOPT solver is required to solve problem with integer variables but other solvers such as IPOPT can provide a relaxed solution where the integer conditions are not enforced.

from gekko import GEKKO
m = GEKKO() # create GEKKO model
# create integer variables
x1 = m.Var(integer=True,lb=-1,ub=1)
x2 = m.Var(integer=True,lb=-1,ub=2)
m.Obj(4*x1**2-4*x2*x1**2+x2**2+x1**2-x1+1)
m.options.SOLVER = 1 # APOPT solver
m.solve()
print('x1: ' + str(x1.value[0]))
print('x2: ' + str(x2.value[0]))

[$[Get Code]]

Discrete Optimization Source (MATLAB and Python) and Video

Double Tank Control

Lotka Volterra Fishing Problem

Furnace Control

Additional Resources

Discussion Questions

Solving the continuous relaxation (IPOPT) and rounding to the nearest integer feels reasonable. Construct or recall a two-variable example where rounding the relaxed optimum is infeasible or badly suboptimal - and state what branch and bound does differently.
Why can adding a single integer variable make a smooth NLP exponentially harder, while adding one more continuous variable barely matters? What does the branch-and-bound tree look like for 20 binary decisions, and what lets solvers prune most of it?
A thermostat (on/off) and a control valve (0-100%) can regulate the same temperature. When must the on/off decision be modeled with integers inside the optimization, and when can a continuous solution with a switching implementation (PWM-style) avoid the MINLP entirely?
Modern scheduling problems - grid-battery dispatch against hourly prices, data-center load shifting between regions, unit commitment of generators - are MINLPs of exactly this page's form. Pick one: which decisions are the integers, which are continuous, and which constraint couples the two so the problem cannot decompose?

Tip: After Exercise 1, try: "I solved a small MINLP with APOPT and got {solution}. Walk the branch-and-bound tree with me: ask me to predict the relaxed solution at each branch before revealing it, and keep score of my predictions."

Dynamic Optimization