Is there a way to formulate the following Linear Program in a mixed-integer LP that I could solve with most linear programs in R/Python that support Mixed Integer Linear Programs (MILP)?

So my question is: How can I use a combination of integer, binary and continuous variables to reformulate the constraints (1) below?

Constants: $C_i$ (factor exposure), $x_i^a$ (initial weight)

Decision variables: $x_i$ (portfolio weight)

Portfolio Maximization:

$\max_{x_{i}}\sum_{i=1}^{N}x_{i}\cdot C_{i}$

subject to:

(1) $\boldsymbol{1}_{\left\{ x_{i}\geq x_{i}^{a}\right\} }\left(x_{i}-x_{i}^{a}\right)\in\{0\}\cup\left[0.025,\infty\right],\forall i$ (Minimum purchase size of 0.025)


$\boldsymbol{1}_{\left\{ x_{i}\geq x_{i}^{a}\right\} }=\begin{cases} 1 & \text{if } x_{i} \geq x_{i}^{a}\\ 0 & \text{otherwise} \end{cases}$

  • $\begingroup$ did you already try something with binary variables? it seems rather standard $\endgroup$ – LinAlg Oct 25 '20 at 22:56
  • $\begingroup$ Hi, Yes I tried but I cannot figure out how to do it since there is a combination of semi-continous constraint (xi has to be 0 or above something), but this only for case when xi is bigger than xi^a => I only want to contraint the purchase, for a sale the ticket size doesn't matter $\endgroup$ – Adrien A. Oct 26 '20 at 2:17

Introduce a small constant tolerance $\epsilon > 0$, binary decision variables $y_i^1$ and $y_i^2$, and linear constraints \begin{align} y_i^1 + y_i^2 &\le 1 &&\text{for all $i$} \tag1\\ (0-x_i^a) y_i^1 + 0.025 y_i^2 \le x_i - x_i^a &\le -\epsilon y_i^1 + (1-x_i^a)y_i^2 &&\text{for all $i$} \tag2\\ \end{align} Constraints $(1)$ and $(2)$ enforce $x_i - x_i^a \le -\epsilon \lor x_i - x_i^a = 0 \lor x_i - x_i^a \ge 0.025$. Explicitly, the three cases are \begin{align} (y_i^1,y_i^2)=(1,0): && -x_i^a \le x_i - x_i^a &\le -\epsilon \\ (y_i^1,y_i^2)=(0,0): && 0 \le x_i - x_i^a &\le 0 \\ (y_i^1,y_i^2)=(0,1): && 0.025 \le x_i - x_i^a &\le 1-x_i^a \\ \end{align}

More simply, introduce a binary decision variable $z_i$ and linear constraints $$-x_i^a (1-z_i) + 0.025 z_i \le x_i - x_i^a \le (1-x_i^a)z_i \text{ for all $i$}$$

If $z_i=0$, the constraint implies $-x_i^a \le x_i - x_i^a \le 0$, so $x_i \le x_i^a$.

If $z_i=1$, the constraint implies $0.025 \le x_i - x_i^a \le 1-x_i^a$, so $x_i \ge x_i^a + 0.025$.

  • $\begingroup$ Thanks RobPratt! Actually I was more interested in how to solve for the first constraint in my problem. I edited the question where I only focus on (1). Do you know how would that work? $\endgroup$ – Adrien A. Oct 26 '20 at 2:12
  • $\begingroup$ I edited my answer to match your edited question. Just check the three cases for $(y_i^1,y_i^2)$ to see how it works. $\endgroup$ – RobPratt Oct 26 '20 at 2:18
  • $\begingroup$ Hi Rob, I tried but it doesn't seem to work. Maybe in (2) it should be (1-yi2)xia at the end? $\endgroup$ – Adrien A. Oct 26 '20 at 2:30
  • $\begingroup$ I edited my question and removed the 100 to make it simpler $\endgroup$ – Adrien A. Oct 26 '20 at 2:31
  • $\begingroup$ I added details of the three cases. What didn't work? $\endgroup$ – RobPratt Oct 26 '20 at 3:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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