APMonitor

  ---------------------------------------------------
  Solver         :  APOPT (v1.0)
  Solution time  :  0.0852 sec
  Objective      :  -2.
  Successful solution
  ---------------------------------------------------
  Objective:  2.0
  x:  2.0
  y:  2.0

$$ \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} $$

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.

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.

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

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.

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

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.

(:source lang=python:) from gekko import GEKKO m = GEKKO(remote=False) c = 2],[1?

1. row indices],[column indices],[values?

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]) (:sourceend:)

Additional Resources

• Dynamic Optimization with Discrete Variables
• Discrete Optimization
• Linear Programming
• Mixed Integer Nonlinear Programming (MINLP)

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

Integer variables are declared in APMonitor with the prefix int. The problem is solved with MATLAB, Julia, PythonApp 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

Gekko is a Python API to APMonitor.

$$ \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

Python Gekko is an interface

(:title Integer Linear Programming:) (:keywords integer, ILP, MILP, binary, discrete:) (:description Integer programming, also known as Integer Linear Programming, is where all of the variables are binary (0 or 1), integer (e.g. integer 0 to 10), or other discrete decision variables in optimization:)

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}, \\ & \text{and} && \mathbf{x} \in \mathbb{Z}^n, \end{align} $$

$$\max c^T x$$

$$\mathrm{subject to} Ax \le b$$

$$x \ge 0 $$

$$x \in \mathbb{Z}^n$$

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.

Integer Variables

Integer variables are declared in APMonitor with the prefix int.

APMonitor Model File

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

Python Gekko

$$\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}$$

(:source lang=python:) from gekko import GEKKO m = GEKKO() # create GEKKO model

1. create integer variables

x1 = m.Var(integer=True,lb=-5,ub=10) 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])) (:sourceend:)

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

Python Gekko

Integer variable x1 and Special Ordered Set x2 variables are solved with Python GEKKO. The sos1 Gekko function is used to create the SOS1 variable.

(:source lang=python:) from gekko import GEKKO m = GEKKO() # create GEKKO model x1 = m.Var(integer=True,lb=-5,ub=10)

1. create Special Ordered Set variable

x2 = m.sos1([0.5, 1.15, 2.6, 5.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])) (:sourceend:)

See Dynamic Optimization with Discrete Variables, Discrete Optimization, and MINLP Solutions