# Relaxing a relation between variables if one of them reaches its maximal value

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?

• 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.
– prubin
Jun 12 at 14:58
• 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?
– prubin
Jun 12 at 15:00
• 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 Jun 12 at 16:23

## 1 Answer

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

• 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.
– prubin
Jun 12 at 19:06
• I think your comment and my update to $(1)$ happened simultaneously. Jun 12 at 19:07
• Great minds often think alike?
– prubin
Jun 12 at 20:34
• 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? Jun 13 at 8:39
• 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. Jun 13 at 12:56