1
$\begingroup$

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!

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you...your solution makes total sense.. let me try it and get back to you. Thanks again! $\endgroup$ Commented Oct 28, 2021 at 7:19
0
$\begingroup$

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$}.$$

$\endgroup$
1
  • $\begingroup$ Thank you very much. Actually, this worked. My actual problem is more complicated and I'm trying to fit this concept into the actual problem. $\endgroup$ Commented Oct 30, 2021 at 2:30

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.