# Writing a specific MILP problem

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?

• 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. Commented Mar 9, 2022 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 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. Commented Mar 9, 2022 at 15:10

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}.$$
• 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$? Commented Mar 9, 2022 at 16:05
• 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 $=$. Commented Mar 9, 2022 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". Commented Mar 9, 2022 at 16:55