# Product of two binary variables
#
# Maximises a quadratic objective over binary selections subject to a
# cardinality limit. The quadratic term is linearised exactly with one
# auxiliary binary per pair, which is tight because the three inequalities
# force z to equal the product at every 0/1 point.
#
# Technique: Replace the product x_i·x_j by an auxiliary binary z_ij with z
# ≤ x_i, z ≤ x_j, z ≥ x_i + x_j − 1.
#
# On this instance the optimum is 19 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Glover, F. and Woolsey, E. (1974). Technical Note—Converting
# the 0-1 Polynomial Programming Problem to a 0-1 Linear Program. Operations
# Research 22(1), 180–182. doi:10.1287/opre.22.1.180
model m
set I = {1, 2, 3, 4}
set P = {1, 2, 3, 4, 5, 6}
const a = {1, 1, 1, 2, 2, 3}, forall p in P
const b = {2, 3, 4, 3, 4, 4}, forall p in P
const q = {7, 8, 1, 4, 3, 1}, forall p in P
const k = 3
bin x, forall i in I
bin z, forall p in P
max sum_{p in P}{q_{p} * z_{p}}
# z_p may only be 1 when both endpoints of pair p are chosen
constr z_{p} <= x_{alpha(p)}, forall p in P
constr z_{p} <= x_{beta(p)}, forall p in P
# and must be 1 when both are, so the product is represented exactly
constr z_{p} >= x_{alpha(p)} + x_{beta(p)} - 1, forall p in P
constr sum_{i in I}{x_{i}} <= k
end
import elytica
def alpha(p):
return {1: 1, 2: 1, 3: 1, 4: 2, 5: 2, 6: 3}[p]
def beta(p):
return {1: 2, 2: 3, 3: 4, 4: 3, 5: 4, 6: 4}[p]
Read this through MCP: read with path: "formulations/binary-product", or resource hlpl://formulations/binary-product.