11
$\begingroup$

Cross-posted at Stats.SE (aka Cross Validated)

I am working on a problem which involves optimizing for minimum power consumption in a large compressor network interconnected through pipelines (think of a connected graph with nodes as compressors and arcs as pipelines). I need to impose a constraint when two or more compressors share a single pipeline on their discharge side, i.e. , their individual discharge pressures should ideally be equal.

Now, when I read in the historical plant operational data recorded through the sensors, I notice that these variables are fairly close but not precisely equal already. This could likely be due to sensor error. My question is how to model such constraints in an optimization problem so that you account for the slight variability among the variables instead of imposing a strict equality constraint.

$\endgroup$
  • 1
    $\begingroup$ Impose a bound on the absolute value of the differences. Here's an answer on handling absolute values in constraints. $\endgroup$ – Marcus Ritt Jun 8 '19 at 3:02
  • 2
    $\begingroup$ Cross-post on CV.SE stats.stackexchange.com/q/412055/49024 $\endgroup$ – Marcus Ritt Jun 8 '19 at 3:38
  • 2
    $\begingroup$ Doesn’t even need absolute values (and the binary variables that come with them). Just need something like $-\delta \le p_1-p_2 \le \delta$. $\endgroup$ – LarrySnyder610 Jun 8 '19 at 4:34
  • 1
    $\begingroup$ @LarrySnyder61 Depending on the software, use of abs in a convex way, as in this case, in an optimization problem formulation does not necessarily cause binary variables to be used, and doesn't in moist modern systems. A cleaner formulation using abs has readability advantages. Note that the link to handling absolute values in constraints in Marcus Ritt 's comment was for a no-convex use of abs, due to having a non-zero lower bound on abs, as opposed to only an upper bound as in this case. $\endgroup$ – Mark L. Stone Jun 8 '19 at 12:33
  • 1
    $\begingroup$ @LarrySnyder610 I think your answer is best. Could you add it, so the OP can accept? $\endgroup$ – Marcus Ritt Jun 10 '19 at 6:33
13
$\begingroup$

Essentially you are trying to constrain $|p_1-p_2|$, where $p_1$ and $p_2$ are the pressures. Normally this must be done using binary variables (see this question, which @MarcusRitt linked to), but in this case, binary variables are not needed (since the lower bound on the absolute value is 0, as @MarkLStone pointed out).

In short, you can simply use the following constraints: $$-\delta \le p_1 - p_2 \le \delta,$$ where $\delta>0$ is your desired level of deviation from equality.

$\endgroup$
  • 3
    $\begingroup$ Actually, the way I think of it is that f(x) = abs(x) is a convex function of x. And modeling f(x) <= 0 should always be easy when f(x) is convex. Thus your linear trick is perfect. Doing f(x) >= 0 should be hard when f is convex. For that you would need binary variables in the f(x) = abs(x) case. To model f(x) >= t you need to model the disjunction f(x) >= t OR f(x) <= -t. $\endgroup$ – Jeff Linderoth Jun 11 '19 at 1:01
  • $\begingroup$ @JeffLinderoth maybe post that comment on the Q or A here? $\endgroup$ – LarrySnyder610 Jun 11 '19 at 1:08
6
$\begingroup$

Answers by Larry Snyder and Mark H have already pointed out the options of (1) constraining the absolute value of the discrepancy, or (2) including abs(discrepancy) in a "penalty function" to be added to the objective function.

These are useful methods, but depending on the problem you may wish to tweak them a bit, since they have some quirks that may not always be desirable - especially if there are several of these soft constraints in the problem.

If you rely on bounding abs(discrepancy), then you are effectively telling the solver that any discrepancy greater than X is absolutely forbidden, and any discrepancy less than or equal to X is absolutely fine. You will often get solutions that are close to the maximum discrepancy, even when it would be easy to reduce this. In some problems, that might be okay; in others, it's not.

For example, I recently worked on a problem where we needed to assign work to employees, trying to keep as close as possible to each employee's requested workload. There were a few cases where "as close as possible" was not close at all - e.g. Bob has requested 20 hours of work, but we only have 10 hours available in his region. In order to accommodate this sort of case, we have to set the cap to at least ten hours - but that doesn't mean we want 10-hour discrepancies for every employee! (And it's not practical to micro-manage the maximum discrepancy for each individual employee.)

Minimising sum(abs(discrepancy)) avoids this issue. However, it means that (e.g.) one 9-hour discrepancy is considered better than ten 1-hour discrepancies, which is probably unreasonable - you can end up with a solution that's good across most of the problem but poor in some regions.

One option, if you have an appropriate solver, is to use a penalty function based on the sum of squared discrepancies. This tends to balance discrepancies through the system - the larger any one discrepancy is, the more pressure there is to reduce it. This often gives nice solutions, but if you have an integer problem it can take a long time to solve.

The option that we ended up using is to combine these ideas:

  • Define a low and high tolerance. Any discrepancy within the low tolerance will be considered "free"; any discrepancy above the high tolerance is forbidden.
  • For each employee (= "group of compressors sharing a pipeline" in your problem), define variable discrepancy as the difference between requested and allocated hours, or between pressures.
  • For each employee (etc.) define abs_discrepancy GE discrepancy and GE -discrepancy
  • Constraint abs_discrepancy LE high_tolerance
  • For each employee (etc.) define nonfree_discrepancy GE 0 and GE abs_discrepancy - low_tolerance
  • Minimise sum of nonfree_discrepancy over all employees.

This effectively approximates a quadratic penalty function with three linear pieces: flat from 0 to low tolerance, then with a cost between low and high tolerances, then infinite gradient past high tolerance.

In our problem, this had the benefit of helping with solution time. We found that for the min(sum(abs(discrepancy))) formulation, the solver reached near-optimal solutions quickly and then spent a lot of time grinding away trying to make very small improvements, but it was difficult to quantify exactly what tolerances to set for stopping before optimality. Setting the low tolerance meant that when an employee's discrepancy was inside that tolerance, the solver didn't need to keep fine-tuning their workload.

$\endgroup$
  • $\begingroup$ This is very interesting. Do you have any theories about why the optimizer would be "grinding away"? In most cases I would have expected it either to reach the tolerance of the solver (and do so somewhat quickly) or to choose the high-tolerance. I don't understand why it should grind. Could it be a weakness in the solver? $\endgroup$ – Mark H Jun 17 '19 at 23:58
  • $\begingroup$ @MarkH Solver (Gurobi) is pretty good, and it has plenty of options for stopping based on gap and run-time. The challenge for us was figuring out constraint settings that will give sensible behavior in all cases, in a system that needs to run regularly without ongoing support from the OR team. $\endgroup$ – Geoffrey Brent Jun 18 '19 at 1:54
  • $\begingroup$ @MarkH For example: in some cases, it may be that the work available fits very nicely to the available staff, so that the theoretical minimum discrepancy is very close to zero. In those cases, defining stopping criterion based on % of lower bound is not helpful. There's also a user acceptance angle to it: if the solver stops when the optimization is "99% done" but the non-optimal 1% is concentrated on one or two employees and really obvious, that's not going to be popular. $\endgroup$ – Geoffrey Brent Jun 18 '19 at 1:59
4
$\begingroup$

The answer by @LarrySnyder610 is a good one. There is however a supplementary/alternative technique that I feel is worth mentioning. Its appropriateness depends on how "soft" the constraints really are.

This technique involves introducing a new non-negative variable, $x$ say, together with the two constraints $$ p_1 - p_2 \leq x $$ and $$ p_2 - p_1 \leq x. $$ (We assume that $p_1$ and $p_2$ are also both non-negative, which should be true for pressure.)

We now incorporate $x$ into the objective function as part of a "helper function" so that $x$ is minimized. This is a little tricky to get right. This component of the objective needs to be weighted appropriately. It needs to be given a low weighting relative to other objective components, but not so low that it introduces numerical instability issues.

This technique is "softer" than the $-\delta \leq p_1 - p_2 \leq \delta$ technique that has been discussed. It is particularly valuable in the situation where "all other things being equal" we wish for $p_1$ and $p_2$ to be the same, but are happy for some divergence to occur if it provides objective improvement.

Usually this technique would not be used in isolation, but would be combined with the other via the domain of $x$ being restricted to $[0,\delta]$.

It often means that we can make $\delta$ a bit larger, confident in the knowledge that this extra flexibility will only be used when needed.

Obviously, the applicability of this technique depends on the problem specifics. In this case it depends on whether having occasional slight pressure imbalance is a reasonable thing or not.

$\endgroup$

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.