# Product of a binary and a bounded continuous variable
#
# Switches a continuous quantity on or off inside the objective. The four
# inequalities pin the auxiliary variable to the product at every integer
# point of the binary, which is the standard Glover linearization and is
# exact rather than a relaxation.
#
# Technique: z = y·x with y binary and 0 ≤ x ≤ U becomes z ≤ Ux, z ≤ y, z ≥
# y − U(1 − x), z ≥ 0.
#
# On this instance the optimum is 52 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Glover, F. (1975). Improved linear integer programming
# formulations of nonlinear integer problems. Management Science 22(4),
# 455–460. doi:10.1287/mnsc.22.4.455
model m
set I = {1, 2, 3}
const p = {4, 6, 6}, forall i in I
const c = {6, 4, 4}, forall i in I
const U = 5
bin y, forall i in I
int 0 <= q <= 5, forall i in I
int 0 <= z <= 5, forall i in I
max sum_{i in I}{p_{i} * z_{i}} - sum_{i in I}{c_{i} * y_{i}}
# z_i = y_i * q_i, exact at every 0/1 value of y
constr z_{i} <= U * y_{i}, forall i in I
constr z_{i} <= q_{i}, forall i in I
constr z_{i} >= q_{i} - U * [1 - y_{i}], forall i in I
constr sum_{i in I}{y_{i}} <= 2
end
import elytica
Read this through MCP: read with path: "formulations/product-binary-continuous", or resource hlpl://formulations/product-binary-continuous.