1
$\begingroup$

I am trying to formulate an optimization problem that can be described as a set of tanks $T$ where each tank $t$ has a maximum capacity of $\overline{r}_{t}$. I want to fill all tanks as much as possible with a common resource $r$ (provided). However, the tanks should be filled according to a pre-defined weighting $\omega_{t}$, so e.g. one tank should always contain twice the resouces of another.

However, when a tank hits its maximum capacity $\overline{r}_{t}$ it should be excluded from this constraint. The remaining tanks should still adhere to the weighting. This is where I'm struggling, as I cannot fix the weighting-relationship between all tanks.

Example (in reality all variables are continuous):

  • Tank1 has a capacity of 2 and a weight of 1
  • Tank2 has a capacity of 10 and a weight of 1
  • Tank3 has a capacity of 6 and a weight of 2

I expect the solution (resouces per tank) to be:

  • [1,1,2] if $r=4$
  • [2,2,4] if $r=8$
  • [2,3,6] if $r=11$ (Tank1 is full and it's weighting does not need to match any more)
  • [2,4,6] if $r=12$ (only Tank2 is getting filled from here)
  • [2,10,6] for any $r \ge 18$

Any solutions I identified so far seem overly complex and very inefficient. Is it possible to formulate this problem as a linear program and if not, do you have any hints on how to solve this elegantly and efficiently?

$\endgroup$
3
  • $\begingroup$ I would suggest editing your question, as portions are unclear. You have symbols popping up undefined. Also, you refer to "progress", but there does not seem to be a time index. $\endgroup$
    – prubin
    Jun 12 at 14:58
  • $\begingroup$ Let's say that you start with three tanks and the weighting is 30%, 20%, 50%. If tank 1 hits its limit first, how do you want the weighting to change? Should tanks 2 and 3 now have weights 28.6% and 71.4% respectively? $\endgroup$
    – prubin
    Jun 12 at 15:00
  • $\begingroup$ thanks a lot for you reply! I removed a constraint which is not directly relevant to my main problem and made the description unclear. I also added an example of my expected behaviour $\endgroup$
    – birnbaum
    Jun 12 at 16:23

1 Answer 1

3
$\begingroup$

Let variable $x_t\in[0,\bar{r}_t]$ be the level of tank $t$, introduce binary variable $y_t$ to indicate whether tank $t$ is full, and introduce variable $z\in[0,r]$. The following constraints do the job: \begin{align} \sum_t x_t &= \min\left(r,\sum_t \bar{r}_t\right) \tag1 \\ y_t = 0 &\implies x_t = \omega_t z &&\text{for all $t$} \tag2 \\ y_t = 1 &\implies x_t \ge \bar{r}_t &&\text{for all $t$} \tag3 \\ y_t = 1 &\implies \omega_t z \ge \bar{r}_t &&\text{for all $t$} \tag4 \end{align} If your solver supports indicator constraints, you can use these directly. Otherwise, you can use big-M constraints to linearize them. For example, constraint $(3)$ becomes $x_t \ge \bar{r}_t y_t$.

$\endgroup$
5
  • $\begingroup$ This presumes (harmlessly) that $r \le \sum_t \bar{r}_t.$ When that is not true, you just fill all the tanks and waste the rest. $\endgroup$
    – prubin
    Jun 12 at 19:06
  • $\begingroup$ I think your comment and my update to $(1)$ happened simultaneously. $\endgroup$
    – RobPratt
    Jun 12 at 19:07
  • 1
    $\begingroup$ Great minds often think alike? $\endgroup$
    – prubin
    Jun 12 at 20:34
  • $\begingroup$ Thanks a lot for your solution and hinting me to indicator constraints! One question: Why do you use $\leq$ in $(3)$ when $x_t$ is per definition capped at $\bar{r}_t$? Would $=$ work as well? $\endgroup$
    – birnbaum
    Jun 13 at 8:39
  • 1
    $\begingroup$ I used $\ge$ in $(3)$ because $\le$ is already enforced as an upper bound on $x_t$. Yes, you can use $=$ in $(3)$ if you prefer. $\endgroup$
    – RobPratt
    Jun 13 at 12:56

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.