I'm given the following linear programming problem:
There are 2 different companies that a firm can invest in: Company A and Company B. These investments yield returns based on how much is invested, as follows:
For Company A,
$0$ return for investment $< 10M$
$1 \rm{M}$ return for $10 \rm{M} \leq$ investment $< 20 \rm{M}$
$1.5 \rm{M}$ return for $20 \rm{M} \leq$ investment $< 30 \rm{M}$
$1.7 \rm{M}$ return for $30 \rm{M} \leq$ investment
For Company B,
- $0$ return for investment $< 15 \rm{M}$
- $2 \rm{M}$ return for $15 \rm{M} \leq$ investment $< 30 \rm{M}$
- $2.5 \rm{M}$ return for $30 \rm{M} \leq$ investment
You are given a budget of $\$ 50 \rm{M}$. Find the optimal set of investments to make to maximize return.
I know this is a pretty trivial example, but I'm trying to figure out how to frame it mathematically. My approach was to break out the different investment ranges for each company into separate decision variables, and then add binary variables so that we can make those investment ranges mutually exclusive (for example, you cannot invest make 2 separate investments into a company). Here's what I have so far.
Objective function
\begin{align*} 0P_1 + P_2 + 1.5P_3 + 1.7P_4 + 0P_5 + 2P_6 + 2.5P_7 &= Z \ \end{align*}
Constraints
\begin{align*} P_1 + P_2 + P_3 + P_4 + P_5 + P_6 + P_7 &\leq 50 \ \end{align*}
\begin{align*} P_1 &\geq 0 \ \end{align*}
\begin{align*} P_1 &< 10 \ \end{align*}
\begin{align*} P_2 &\geq 10 \ \end{align*}
\begin{align*} P_2 &< 20 \ \end{align*}
\begin{align*} P_3 &\geq 20 \ \end{align*}
\begin{align*} P_3 &< 30 \ \end{align*}
\begin{align*} P_4 &\geq 30 \ \end{align*}
\begin{align*} P_5 &\geq 0 \ \end{align*}
\begin{align*} P_5 &< 15 \ \end{align*}
\begin{align*} P_6 &\geq 15 \ \end{align*}
\begin{align*} P_6 &< 30 \ \end{align*}
\begin{align*} P_7 &\geq 30 \ \end{align*}
\begin{align*} P_1 &\leq M_1y_1 \text{ such that } y_1 \text{ is a binary variable and } M_1 \text{ is a very large number } > 1e10 \ \end{align*}
\begin{align*} P_2 &\leq M_2y_2 \text{ such that } y_2 \text{ is a binary variable and } M_2 \text{ is a very large number } > 1e10 \ \end{align*}
\begin{align*} P_3 &\leq M_3y_3 \text{ such that } y_3 \text{ is a binary variable and } M_3 \text{ is a very large number } > 1e10 \ \end{align*}
\begin{align*} P_4 &\leq M_4y_4 \text{ such that } y_4 \text{ is a binary variable and } M_4 \text{ is a very large number } > 1e10 \ \end{align*}
\begin{align*} P_5 &\leq M_5y_5 \text{ such that } y_5 \text{ is a binary variable and } M_5 \text{ is a very large number } > 1e10 \ \end{align*}
\begin{align*} P_6 &\leq M_6y_6 \text{ such that } y_6 \text{ is a binary variable and } M_6 \text{ is a very large number } > 1e10 \ \end{align*}
\begin{align*} P_7 &\leq M_7y_7 \text{ such that } y_7 \text{ is a binary variable and } M_7 \text{ is a very large number } > 1e10 \ \end{align*}
\begin{align*} y_1 + y_2 + y_3 + y_4 &\leq 1 \ \end{align*}
\begin{align*} y_5 + y_6 + y_7 &\leq 1 \end{align*}
The problem is, when I implement this in Python (using PuLP), it tells me that the problem is infeasible. What's wrong with my formulation here?
