How to handle real-world (soft) constraints in an optimization problem?

Question

_{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.

Answer 1

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.

Answer 2

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.

Answer 3

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.