5
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Mar 9, 2022 at 15:07
  • $\begingroup$ @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 or.stackexchange.com/questions/4521/…. I decided to omit this detail in the question for brevity, but will edit the question if this is removing required details. $\endgroup$
    – FightMilk
    Commented Mar 9, 2022 at 15:10

1 Answer 1

6
$\begingroup$

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$}.$$

$\endgroup$
3
  • $\begingroup$ 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$? $\endgroup$
    – FightMilk
    Commented Mar 9, 2022 at 16:05
  • 2
    $\begingroup$ 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 $=$. $\endgroup$
    – RobPratt
    Commented Mar 9, 2022 at 16:52
  • $\begingroup$ 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". $\endgroup$
    – FightMilk
    Commented Mar 9, 2022 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.