MIQP

Mixed-Integer Quadratic Programming

A quadratic objective with some decisions restricted to integers.

In plain terms

You know the shape of a good answer, but not which options belong in it. Which three suppliers, which handful of positions, which machines to run — and then how much of each. Choosing the members and sizing them pull against each other, because dropping one option changes the right amount for all the others. This class solves both halves at once.

The technical picture

Mixed-integer quadratic programming puts integrality and curvature in the same model: a quadratic objective, linear constraints, and a subset of variables that must take whole-number or yes/no values. Selecting a subset and sizing what you selected stop being two problems and become one.

Solving the continuous part first and rounding afterwards is the usual shortcut, and it is not reliable: dropping a decision changes which quantities are optimal for the ones that survive. Quicopt picks the discrete decisions and the continuous quantities together, and reports whether the answer was proved.

Mathematical model▾

Minimize a quadratic objective subject to linear constraints, with a subset of variables restricted to integers.

x min s.t. \frac{1}{2} x^{⊤} Q x + c^{⊤} x A x \leq b x_{i} \in Z (i \in I)

where Q \in R^{n \times n} is symmetric and I indexes the integer variables.

Example

From install to solved model: a small, self-contained example, copy-paste ready.

Install the client

$ pip install "quicopt[mathopt]"

Copy the example

miqp.py

from ortools.math_opt.python import mathopt
from quicopt import Client

# An MIQP: the /problems/qp objective, plus a discrete choice. Each variable
# needs its own switch, and at most one switch may be on. Turning on y costs
# (0-1)^2 = 1; turning on x costs (1-2)^2 = 4. So the quadratic alone does not
# decide it — the binary choice does.
model = mathopt.Model(name="miqp")
x = model.add_variable(lb=0.0, name="x")
y = model.add_variable(lb=0.0, name="y")
bx = model.add_binary_variable(name="bx")
by = model.add_binary_variable(name="by")
model.add_linear_constraint(x <= 3 * bx)
model.add_linear_constraint(y <= 3 * by)
model.add_linear_constraint(bx + by <= 1)
model.minimize((x - 1) * (x - 1) + (y - 2) * (y - 2))

client = Client()
result = client.solve(model)
print(result.display)

Run it

$ python miqp.py

What you’ll see

├── shots
│   ├── 1 · primal-dual · global   1.0   0.02s  ◀ best
│   ├── 2 · primal                 1.0    2.0s
│   └── 3 · primal                 1.0    2.0s
├── status:     optimal
├── feasible:   true
├── objective:  1.0000000000000089
├── x:          bx=0, by=1, x=0, y=2.0  (4 variables)
└── solve_time: 2.0009 s

Docs, API reference and more examples live in the Developer Hub →