6
$\begingroup$

I have an optimization problem that I'm attempting to tackle. As you can see in the image below, there's a graph network through which water flows. I've drawn out the problem in the image to explain it clearly.

The objective is for Final1 node to receive water with component A having values between a range. The component A at any node is measured by a volume-weighted average of component A measures from its predecessor nodes.

Node_A = (Predecessor1_Vol x Predecessor1_A + Predecessor2_Vol x Predecessor2_A .....) /(Predecessor1_Vol + Predecessor2_Vol .....)

All of the above are decision variables (D.V.) in the optimization problem. The "vol" variables have to remain as D.V. since this is part of a bigger problem. There is flexibility on "component A" variables and can or not be D.V. as they were introduced only for this subproblem.

All numbers in the image are just examples of what the optimization can come up with. In the current formulation, all are decision variables except the concentration at "Start" nodes, which are given.

However, framing the problem this way makes it nonlinear (reason described in the image). Since I am using a linear solver "cbc", the solver just says that quadratic constraints cannot be supported.

I am reaching out to this community to find out if this problem can be linearised or formulated in another way to get the same output.

enter image description here

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Without reading very carefully, it sounds like you have a variant of the pooling problem. With that as a key-word you will find a are number of articles presenting different ideas to attack this nonlinear problem. $\endgroup$
    – Johan Löfberg
    Commented Jun 7, 2021 at 6:25
  • 2
    $\begingroup$ +1 for the pooling problem. I don't see a way of linearizing this. However, if you rewrite those equations as Mid2_A*(Vol_F3 + Vol_F4) = Vol_Start3*Start3_A + Vol_Start4*Start4_A you will see that it is "just" quadratic. That means, a solver like Gurobi will be able to solve it. Not sure if there are any free solvers that are any good. $\endgroup$
    – Walter Sebastian Gisler
    Commented Jun 7, 2021 at 13:15
  • 1
    $\begingroup$ Yes this is the pooling problem, which has also been investigated from the wastewater point of view, sciencedirect.com/science/article/abs/pii/S0263876215005109 might be starting point for a literature review. I think SCIP as a free solver can solve this, or as mentioned Gurobi. $\endgroup$
    – user3680510
    Commented Jun 7, 2021 at 14:25
  • $\begingroup$ Hi @user3680510: I tried to install SCIP and interface it with Pyomo but I have been unsucessful and it's been really troublesome so far. I also tried to use IPOPT for a bigger problem (40 start nodes, 8 final nodes and 50 intermediate nodes) with the above scenario as a constraint and the solver has run for 7 hours straight and hasn't given a solution yet. Any idea how much time solvers generally take for a pooling problem with an intermediate sized network ? $\endgroup$
    – Nisith Singh
    Commented Jun 9, 2021 at 2:17
  • 1
    $\begingroup$ Pooling problems are in general very hard to solve, so do not expect global optimal solution. You could also easily test each solver without installing it locally via the neos-server. With pyomo there is a description at the bottom: neos-guide.org/neos-interfaces . I would try at least baron, gurobi, antigone, scip. $\endgroup$
    – user3680510
    Commented Jun 9, 2021 at 8:19

0

Reset to default