Is this reducible to a standard optimization problem?

51 Views Asked by At

There are $N$ agents who needs to be allocated $K$ discrete resources. There is a bottleneck threshold utility $R$ per agent. The $i$th agent has utility $r_{ij}$ if he is allocated $j$th resource. The objective is to allocate resources in order to maximize the number of agents who could exceed the threshold utility. Mathematically,

$$ \max_{x_{ij}}\sum_{i=1}^{N}\mathbf{1}_{\sum_{j=1}^{K}x_{ij}r_{ij}>R}\\ \sum_{i=1}^{N}x_{ij}\le 1 \;\;\forall j\in\{1,2,\cdots, K\}\\ x_{ij}\in\{0,1\} $$

$x_{ij}$ denotes whether $i$th agent is allocated $j$th resource. First equation maximizes the number of agents who exceed R utility. Second equation makes sure each resource is allocated to maximum one agent.

1

There are 1 best solutions below

8
On BEST ANSWER

Yes, this is easily written as a MILP through standard big-M modelling. Introduce new binary variables $E_i$ and the constraints

$\sum_{j=1}^{K}x_{ij}r_{ij} \geq R - M(1-E_i)$

where $M$ is a sufficiently large constant (but as small as possible) to ensure the constraint is redundant when $E_i$ is $0$ (standard big-M arguments). Now maximize $\sum E_i$. Note that you cannot use strict inequalities.

If $r_{ij}\geq 0$, $M=R$ works and the right-hand side simplifies to $RE_i$