Quadratic programming

Defines quadratic programming (QP), including quadratically-constrained programming (QCP), mixed integer quadratic programming (MIQP), and mixed-integer quadratically-constrained programming (MIQCP).

OPL supports quadratic programming (QP), including quadratically-constrained programming (QCP), mixed integer quadratic programming (MIQP), and mixed-integer quadratically-constrained programming (MIQCP).

Conventionally, a quadratic program is formulated this way:

Minimize 1/2 x^TQx + c^Tx

subject to Ax ~ b

with these bounds lb ≤ x ≤ ub

where the relation ~ may be any combination of equal to, less than or equal to, greater than or equal to, or range constraints. As in other problem formulations, l indicates lower and u upper bounds. Q is a matrix of objective function coefficients. That is, the elements Q jj are the coefficients of the quadratic terms xj^ 2, and the elements Q ij and Q ji are summed to make the coefficient of the term x i x j.

Here is an example of quadratic objective problem:

dvar float x[0..2] in 0..40;


maximize
  x[0] + 2 * x[1] + 3 * x[2]
  - 0.5 * 
    ( 33*x[0]^2 + 22*x[1]^2 + 11*x[2]^2 
    - 12*x[0]*x[1] - 23*x[1]*x[2] );

subject to {
  ct1:  - x[0] +     x[1] + x[2] <= 20;
  ct2:    x[0] - 3 * x[1] + x[2] <= 30;
}

Here is an example of quadratic constraint problem.

dvar float x[0..2] in 0..40;


maximize
  x[0] + 2 * x[1] + 3 * x[2]
  - 0.5 * ( 33 * x[0]^2 + 22 * x[1]^2 + 11 * x[2]^2 
          - 12 * x[0] * x[1] - 23 *x [1] * x[2] );

subject to {
  ct1:  - x[0] +     x[1] + x[2] <= 20;
  ct2:    x[0] - 3 * x[1] + x[2] <= 30;
  ct3:    x[0]^2 + x[1]^2 + x[2]^2 <= 1.0;
}

Quadratic programming is described in detail in the IBM ILOG CPLEX Optimizer User’s Manual.

Refer to the sections:

• Solving Problems with a Quadratic Objective (QP)

• Solving Problems with Quadratic Constraints (QCP)

• Solving Mixed Integer Programming Problems (MIP)

for information on MIQP and MIQCP.