How do you formulate a project selection problem with binary variables and monthly budget constraints?

Conditions

• Each project has an associated cost and net return.
• Budget constraints apply to specific time periods (e.g., months).
• Decisions are binary (select or do not select).

Reasoning, step by step

1. Define binary variables $X_i \in \{0, 1\}$ for each project $i$.
2. Identify the net return for each project.
3. Formulate the objective function: Maximize $\sum (\text{return}_i \cdot X_i)$.
4. Identify the cost for each project in each time period.
5. Formulate the budget constraints: $\sum (\text{cost}_{i,t} \cdot X_i) \le \text{Budget}_t$ for each period $t$.
6. Specify the domain restriction $X_i \in \{0, 1\}$.

Example

For four projects with returns 217, 125, 88, and 109, the objective is to maximize $217X_1 + 125X_2 + 88X_3 + 109X_4$. The January budget constraint is $58X_1 + 44X_2 + 26X_3 + 23X_4 \le 120$. The February constraint is $25X_1 + 29X_2 + 13X_3 + 17X_4 \le 80$. The March constraint is $43X_1 + 25X_2 + 23X_3 + 29X_4 \le 95$.

Common misconceptions

• Assuming $X_i$ can take fractional values (e.g., selecting half a project).
• Forgetting to include the binary constraint $X_i \in \{0, 1\}$.
• Confusing the objective function coefficients (returns) with the constraint coefficients (costs).

Watch the explanation

Explore next

• What is the optimal solution for the given project selection example?
• Why are binary variables used instead of continuous variables in project selection?
• How does the fixed cost problem differ from the project selection problem?