Mixed Integer Linear Programming problem maximizing projects but they can share resources

Question

I need help with this optimization problem. I'm sharing a simplified version for easier discussion.

For example, I have projects $x_i$ where $i=1,2,...5$.

Each project has factors $a_i, b_i, c_i$ with values that are different for each project. These factors tell how much resource each project is taking.

The optimization model is

$max\sum_ia_ix_i$

subject to

$\sum_ib_ix_i<100$

$\sum_ic_ix_i<500$

where $100$ and $500$ are available resources.

But one of the resources, $100$ hectares (ha), is actually a land resource which is tricky.

For example when projects $x_1$, $x_3$, and $x_4$ are chosen together, they can share the land resource.

So that if project $x_1$ takes 20 ha land, $x_3$ takes 30 ha land, and $x_4$ takes 40 land...when they are all activated they just take 40 ha of land resource.

I know the code should be a mixed-integer...but I could not think of a way to code the sharing of land such that for "synergistic" projects, only the maximum taker is accounted.

Thanks!

Answer 1

You do not need any additional variables. Instead of $$\sum_i b_i x_i <100,$$ you want to enforce $$\max_i b_i x_i <100,$$ which is equivalent to linear constraints $$b_i x_i <100 \quad \text{for all $i$}.$$

Answer 2

I'm assuming that what you mean is that the $x_i$ are binary indicators of whether the project goes ahead, and for some subset of them - for simplicity let's say $x_1,\ldots,x_k$, the total usage of resource $B$ is just the maximum of the $b_i$ associated with them? So the constraint is actually

$$\max_{1 \leq i \leq k} b_i x_i + \sum_{i = k + 1}^n b_i x_i < 100$$

We can then borrow from, for example, this answer, to introduce a new set of variables $u_i \in \{0, 1\}$ for $i \in \{1, \ldots, k\}$ and adding constraints that cause $u_i$ to indicate which of $x_i$ is measuring the "use" of the resource, i.e. $u_i = 1$ when $x_i = 1$ and $b_i = \max_{x_j = 1} b_j$. Then your usage constraint becomes

$$\sum_{i = 1}^k b_i u_i + \sum_{i = k+1}^n b_i x_i < 100$$

Note that this does have a few effects that may be undesirable:

1. It adds several more decision variables.

2. It adds many more constraints.

3. It may affect the convexity of the solution space.

So depending on the scale of your problem, you may find it more efficient to solve some relaxation of the original problem, then find a way to adjust that solution to give a (probably non-optimal) solution to the original.