Integer/Binary Variables in Optimization

Binary (0 or 1) or the more general integer (select integer 0 to 10), or other discrete decision variables are frequently used in optimization. Examples of discrete variables include ON/OFF state (0 or 1 binary), selection of multiple options (0 to 5 integers), and other variables that are naturally integers.

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. There are numerical solvers such as APOPT and Bonmin that use methods such branch and bound and outer approximations to efficiently solve problems with binary, integer, or discrete variables.

Binary Variables

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)
   int_b >=0 <=1

Integer Variables

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)
   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.

Discrete Variables

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).

See Dynamic Optimization with Discrete Variables and Discrete Optimization.