3
$\begingroup$

I am building a small model that trades water and buys water. For simplicity reasons, I am only discussing the relevant constraints: $\sf varWaterIn_h$ is the amount in litres of water bought per hour, while $\sf varWaterOut_h$ is the amount in litres of water sold per hour. We have a water price defined as $\sf parWaterPrice$ and the prefixes var and par stand for variables and parameters. In addition $M$ stands for a very large number, where we can assume it's sufficiently large. $\sf varFlagIn$ and $\sf varFlagOut$ are binary constraints.

To prohibit water buying and water selling at the same time, we have the following constraints for every hour:

\begin{align}{\sf varWaterIn_h} &\leq M\cdot\sf varFlagIn_h\\{\sf varWaterOut_h} &\leq M \cdot \sf varFlagOut_h\\{\sf varFlagIn_h + varFlagOut_h} &\leq 1\end{align}

In addition there is also somewhere a constraint that specify that all water inflows and outflows needs to be the same, as you cannot have somewhere randomly generating water out of nowhere. It looks like:

$$\sf \dots + varWaterIn_h \dots = \dots + varWaterOut_h + \dots$$

Let us assume that we want to maximise the objective function:

$$\sf \sum_h parWaterPrice_h \cdot (varWaterIn_h - varWaterOut_h)$$

Now, when I specify it as this, I get a satifying answer, where we only have either $\sf varWaterIn_h$ or $\sf varWaterOut_h$. However, it occurs to me that if we just specify the objective function, without the binary constraints, it should work too right?

Meaning:

\begin{align}\max&\quad\sf\sum_h parWaterPrice_h \cdot (varWaterIn_h - varWaterOut_h)\\\text{s.t.}&\quad\sf\dots + varWaterIn_h \dots = \dots + varWaterOut_h + \dots\end{align}

Since we maximize our revenue, so it is impossible that the optimum would be buying and selling water at the same time right? Or am I missing something?

The reason for wanting to specify it as a LP rather than an ILP is the speed at which a LP can be solved.

$\endgroup$
3
  • $\begingroup$ As your model stands, a solver might find optimal solutions where $\sf in_h, out_h > 0$ in the same period. In postprocessing, you can transform any solution where $\sf in_h, out_h > 0$ in the same period to a solution where either $\sf in_h > 0$ or $\sf out_h > 0$. Both solutions will have the same objective value. Whether this transformation is valid in general depends on the full model, but I'd guess you're safe. $\endgroup$
    – ktnr
    Aug 18, 2021 at 8:01
  • $\begingroup$ By transformation, you mean reducing the values of $\sf varWaterIn_h$ and $\sf varWaterOut_h$ such that either one of them becomes zero at hour $h$ right? $\endgroup$
    – Snowflake
    Aug 18, 2021 at 9:23
  • $\begingroup$ Yes, subtract the smaller value from the larger one and set the smaller one to 0. $\endgroup$
    – ktnr
    Aug 18, 2021 at 11:27

1 Answer 1

4
$\begingroup$

Yes, you can drop the big-M constraints and the binary variables, if there are no other constraints involving $\sf varWaterIn$ and $\sf varWaterOut$.

Note that if you take any optimal solution and increase both $\sf varWaterIn_h$ and $\sf varWaterOut_h$ by the same amount, you get another optimal solution (the costs offset each other and the input-output balance is maintained). Similarly, if you have an optimal solution where both variables are positive and you decrease both by the same amount (preserving nonnegativity), you get another optimal solution. What that tells us is that, for the single-constraint model, a solution both buying and selling at the same time is not an extreme point of the feasible region. Since the simplex method (or the barrier method with crossover) only finds extreme point solutions, you can be confident the solution will not both buy and sell simultaneously.

That said, if there are other constraints involving the variables, then we no longer know that bumping both variables in a period up or down by the same amount yields a feasible solution. So you would need to confirm that by additional analysis.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.