# Logarithmic encoding of a choice
#
# Picks exactly one alternative while using logarithmically many binaries
# rather than one per alternative. The selection indicator is reconstructed
# from the bit pattern, trading a smaller variable count against a less
# transparent model.
#
# Technique: Select one of k alternatives with ceil(log2 k) binaries
# instead of k, using a binary expansion of the index.
#
# On this instance the optimum is 14 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Vielma, J. P. and Nemhauser, G. L. (2011). Modeling disjunctive
# constraints with a logarithmic number of binary variables and constraints.
# Mathematical Programming 128(1–2), 49–72.
model m
set A = {1, 2, 3, 4}
set Bt = {1, 2}
const v = {14, 9, 10, 13}, forall a in A
const bit = {{0, 0},
{1, 0},
{0, 1},
{1, 1}}, forall a in A, forall b in Bt
bin z, forall b in Bt
var 0 <= lam <= 1, forall a in A
max sum_{a in A}{v_{a} * lam_{a}}
constr sum_{a in A}{lam_{a}} = 1
# lam_a can only be positive when every bit of z matches the code of a
constr sum_{a in A}{bit_{a,b} * lam_{a}} <= z_{b}, forall b in Bt
constr sum_{a in A}{[1 - bit_{a,b}] * lam_{a}} <= 1 - z_{b}, forall b in Bt
end
import elytica
Read this through MCP: read with path: "formulations/logarithmic-encoding", or resource hlpl://formulations/logarithmic-encoding.