Integer Linear Programming

Integer Linear Programming (ILP) is a type of optimization problem where the variables are integer values and the objective function and equations are linear.

$$ \begin{align} & \text{maximize} && \mathbf{c}^\mathrm{T} \mathbf{x}\\ & \text{subject to} && A \mathbf{x} \le \mathbf{b} \\ & && \mathbf{x} \ge \mathbf{0} \\ &&& \mathbf{x} \in \mathbb{Z}^n \end{align} $$

A Mixed-Integer Linear Programming (MILP) problem has continuous and integer variables. Mixed-Integer Nonlinear Programming (MINLP) also includes nonlinear equations and requires specialized MINLP solvers such as APOPT. MINLP solvers can also solve MILP or ILP problems although other solvers such as CPLEX, Gurobi, or FICO Xpress are specialized commercial solvers for MILP. APMonitor and GEKKO solve MINLP problems. The following integer linear programming (ILP) problem has a two potential maximum values at (1,2) and (2,2).

$$\begin{align} \max & \text{ } y \\ -x +y & \leq 1 \\ 3x +2y & \leq 12 \\ 2x +3y & \leq 12 \\ x,y & \ge 0 \\ x,y & \in \mathbb{Z} \end{align}$$

APMonitor Model File

Integer variables are declared in APMonitor with the prefix int. The problem is solved with MATLAB, Julia, Python or through the APMonitor Online Interface.

  Variables
    int_x >= 0
    int_y >= 0
  End Variables

  Intermediates
    x = int_x
    y = int_y
  End Intermediates

  Equations
    maximize y
    -x+y<=1
    3*x+2*y<=12
    2*x+3*y<=12
  End Equations

Python Gekko

Gekko is a Python API to APMonitor. The same ILP problem is solved with Gekko.

from gekko import GEKKO
m = GEKKO()
x,y = m.Array(m.Var,2,integer=True,lb=0)
m.Maximize(y)
m.Equations([-x+y<=1,
             3*x+2*y<=12,
             2*x+3*y<=12])
m.options.SOLVER = 1
m.solve()
print('Objective: ', -m.options.OBJFCNVAL)
print('x: ', x.value[0])
print('y: ', y.value[0])
  ---------------------------------------------------
  Solver         :  APOPT (v1.0)
  Solution time  :  0.0852 sec
  Objective      :  -2.
  Successful solution
  ---------------------------------------------------
  Objective:  2.0
  x:  2.0
  y:  2.0

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. It is selected with m.options.SOLVER=1. 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.

Solution in Matrix Form

Another representation is matrix form. Gekko function qobj defines a linear or quadratic objective and axb defines the `Ax\leb` constraint.

from gekko import GEKKO
m = GEKKO(remote=False)
c = [0,1]
A = [[-1,1],[3,2],[2,3]]
b = [1,12,12]
z = m.Array(m.Var,2,integer=True,lb=0)
m.qobj(c,x=z,otype='max')
m.axb(A,b,x=z,etype='<=')
m.options.SOLVER = 1
m.solve()
print('Objective: ', -m.options.OBJFCNVAL)
print('x: ', z[0].value[0])
print('y: ', z[1].value[0])

Solution in Sparse Matrix Form

For large-scale problems, it is more efficient to solve the problem in sparse matrix form. The matrix arguments are passed to Gekko in coordinate (COO) list form. COO list form is [row indices],[values] for a vector and [row indices],[column indices],[values] for a matrix.

from gekko import GEKKO
m = GEKKO(remote=False)
c = [[2],[1]]
A = [[1,1,2,2,3,3],[1,2,1,2,1,2],[-1,1,3,2,2,3]]
b = [[1,2,3],[1,12,12]]
z = m.Array(m.Var,2,integer=True,lb=0)
m.qobj(c,x=z,otype='max',sparse=True)
m.axb(A,b,x=z,etype='<=',sparse=True)
m.options.SOLVER = 1
m.solve()
print('Objective: ', -m.options.OBJFCNVAL)
print('x: ', z[0].value[0])
print('y: ', z[1].value[0])

Additional Resources

💬