5

I would like to choose a set of $\beta_j$s that maximizes a simple linear objective function of the type

$$ \underset{\beta_j}{\operatorname{max}}\sum_{j=1}^{J}X_j\beta_j \\ $$

subject to the following constraints $$ \sum_{j=1}^{J}C_j(\beta_j)\beta_j \le M \\ \beta_j \in \Omega \\ $$

where $X_j$ ranks the $j$s using a metric, $C_j(\beta_j)$ can be thought as a marginal cost function that changes with the chosen $\beta_j$. $\beta_j$ can only be from a set of pre-selected set of integers $\Omega$. $M$ is some budget constraint.

In addition to this, I have a hard requirement that the assigned $\beta_j$ has to be higher for a $j$ with higher $X_j$ -

$$ \beta_j > \beta_k \quad \text{when} \quad X_j>X_k $$

what would be an elegant way of implementing this?

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
FightMilk
  • 215
  • 1
  • 5
  • 1
    Can you tell us explicitly what $C_j(\beta_j)$ is? It doesn't sound likely that $C_j(\beta_j)\beta_j$ is linear, and possibly is not linearizable, and therefore not representable as a MILP. – Mark L. Stone Mar 09 '22 at 15:07
  • @MarkL.Stone you are absolutely right, it is non-linear but pre-computable for all $\beta_j \in \Omega$. I solve it using the answer in https://or.stackexchange.com/questions/4521/linear-objective-function-with-non-linear-constraints.

    I decided to omit this detail in the question for brevity, but will edit the question if this is removing required details.

     – FightMilk Mar 09 '22 at 15:10

1 Answers1

6

A simple approach is to introduce a small constant tolerance $\epsilon>0$ and impose linear constraints $$\beta_j \ge \beta_k + \epsilon \quad \text{for all $j,k$ such that $X_j > X_k$}.$$ Because $\beta_j$ and $\beta_k$ are integers, you can take $\epsilon=1$.

An alternative approach that avoids $\epsilon$ is to impose conflict constraints based on the binary variables $z_{i,j}$ introduced in the linked answer: $$z_{i,j}+z_{\ell,k} \le 1 \quad \text{for all $i,j,k,\ell$ such that $X_j > X_k$ and $\omega_i \le \omega_\ell$}.$$

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • I am trying to implement the first solution and had a follow-up question. The way to implement this would be to order the data such that $X_j > X_k$ for $j = k+1$ and then set the constraint $\beta_j = \beta_k + \epsilon$ for $j=k+1$? – FightMilk Mar 09 '22 at 16:05
  • 2
    Yes, your suggested implementation uses $O(J)$ constraints ("transitive reduction") instead of $O(J^2)$, but make sure you have $\beta_k \ge \beta_j +\epsilon$ instead of $=$. – RobPratt Mar 09 '22 at 16:52
  • I am choosing this as my preferred solution as 1) it is simple and intuitive to explain to my business and also to implement and 2) this model will go into a software that needs to select the $\beta_j$ as an user changes inputs. The $\epsilon$ is a great input for the user if they want to "Create some more gaps between the $j$s". – FightMilk Mar 09 '22 at 16:55