modelling a composite objective function (max + argmax) as an (integer) linear program

479 Views Asked by At

Suppose $\mathbf{x} = [x_1, x_2, \ldots, x_n]$, where $x_i \in \{0, 1\}$ are binary variables. We know for a fixed $\mathbf{w}$ the following problem is an Integer Linear Program: $$ \arg\max_{\mathbf{x}} \mathbf{x}\cdot\mathbf{w} $$

Define the function $f(\hat{\mathbf{x}}) $ to be: $$ f(\hat{\mathbf{x}}) = \begin{cases} a_1 & \text{ if } x_1 = 1, x_2 = 0, x_3 = 0, \ldots, x_n = 0 \\ a_2 & \text{ if } x_1 = 0, x_2 = 1, x_3 = 0, \ldots, x_n = 0 \\ \vdots \\ a_n & \text{ if } x_1 = 0, x_2 = 0, x_3 = 0, \ldots, x_n = 1 \\ \end{cases} $$

Hence for a fixed $\mathbf{w}$ the expression $f( \arg\max_{\mathbf{x}} \mathbf{x}.\mathbf{w} )$ has one of the values $a_1$, or $a_2$, $a_3$, ... . We want to find $\mathbf{w}$ that maximizes this expression. I other words, we wan to model the following objective as an Integer Linear Optimization problem: $$ \max_{\mathbf{w}} f( \arg\max_{\mathbf{x}} \mathbf{x}.\mathbf{w} ) $$

Note: for simplicity assume $n = 2$.