When No Violation Is Found: Probabilistic Certification and Benders Cuts

What a conditional miss bound means, how certification costs grow, and how sampled scenario cuts support mixed-integer robust optimization.

Many scenarios have been checked, and no violation has appeared. Can the current design be accepted? Low costs in the scenarios already inspected are insufficient. We need to know how readily the search would have found a violation if one remained.

The previous mellowmax note examined how Markov-chain visit frequencies and sampling bias affect an optimization direction. Soft separation uses such probabilistic scenario searches to find violations. Certifying a fixed design requires a bound on the probability of missing a remaining violation. That bound determines the cost of certification and its role in mixed-integer Benders methods.

1. Valid cuts from sampled scenarios

Let f(x) be the investment cost of design x and Qi(x) the optimal operating cost under scenario i. With m scenarios, the robust optimization problem is

F⋆=minx∈XF(x)F(x):=f(x)+Q⋆(x)Q⋆(x):=max1≤i≤mQi(x)

The set X may include integer variables such as facility-opening decisions. Introducing an auxiliary variable θ gives a constraint θ≥Qi(x) for each scenario. A master problem approximates these constraints with a subset of cuts and produces a candidate (x¯,θ¯). Separation checks whether its θ is too small.

Assume linear recourse is feasible and finite for every design and scenario under consideration, with strong duality. Using a dual feasible region Π that does not depend on the design, write

Qi(x)=maxπ∈ΠπT(h−Ex−Uξi)

Here h is the right-hand-side vector, E and U describe how design and uncertainty enter that vector, and ξi contains the scenario data. Fix an optimal dual solution π¯i obtained by solving scenario i at the current design. Then

ai(x):=π¯iT(h−Ex−Uξi)ai(x)≤Qi(x)≤maxjQj(x)

so θ≥ai(x) is a valid Benders cut for the robust problem. Scenario i need not be the worst one. If the current θ is 100 and the sampled scenario costs 120, that scenario can cut off the candidate even if the actual maximum cost is 150. The cut from an optimal dual solution equals 120 at the current point.

Dual feasibility makes the cut valid; dual optimality at the current point makes it tight there. The event requiring a probability bound is failure to discover a remaining violation.

2. The probability bounded by ρ

Fix a candidate (x¯,θ¯) and define its set of violating scenarios as

V:={i:Qi(x¯)>θ¯}

Initially, use zero cost tolerance and count one check as selecting a scenario and evaluating its cost exactly.

Suppose V is nonempty. Let ℋt contain both the optimization history before certification and every check so far. For every possible history in which no violation has yet been found, require

Pr(It+1∉V∣ℋt)≤ρ<1

With ρ = 0.9, the next check has at most a 90% probability of missing and at least a 10% probability of detecting a violation. The actual miss probability need not equal 90%.

Applying this conditional bound repeatedly gives, for a fixed violating candidate,

Pr(⋂t=1,…,K{It∉V}∣ℋ0)≤ρK

The checks need not be independent. The bound must instead remain valid conditional on what has already been observed. An average miss frequency of 90% over an entire run does not establish this condition.

For 0 < ρ < 1 and a per-candidate false-certification allowance βℓ between zero and one, choose

Kℓ=⌈log(1βℓ)log(1ρ)⌉

and finish certification after that many consecutive checks without a violation. We choose βℓ as a target; we must justify ρ as a property of the search. This allowance controls the procedure’s probability of accepting a violating candidate.

3. Stationary probabilities and reaching the violation set

Let P be the Markov transition matrix at the fixed design. From a current scenario i outside V, the probability of missing a violation on the next check is

Pr(It+1∉V∣It=i)=1−∑j∈VP(i,j)

Using ρ = 0.9 therefore requires at least a 0.1 probability of entering V from every reachable state in which no violation has been found. If some state cannot reach V in one transition, such a one-transition bound fails. Several transitions could form one checking unit, but both its probability bound and its cost would need to be recalculated.

Consider standard Metropolis-Hastings on 100 scenarios, with independent uniform proposals over the entire set. The target is px(i)∝exp(Qi(x)w), with w > 0. If the current scenario is nonviolating and the proposal violates, the proposed cost is higher, so acceptance has probability one.

Number of violating scenarios Detection probability per check Miss probability per check
50 0.50 0.50
10 0.10 0.90
1 0.01 0.99

Applying ρ = 0.9 in the last case underestimates the certification error. Lowering the temperature can increase the violating scenario’s stationary probability, but leaves its probability of first being proposed unchanged. Frequent visits in stationarity and rapid discovery from the current state are different properties.

Numerically, 0.950 is about 0.00515, whereas 0.9950 is about 0.605. For the same 50 checks, the upper bound on consecutive misses changes sharply depending on whether the justified one-check bound is 0.9 or 0.99.

4. Do later candidates require an explosion in checks?

The number of certification attempts is usually unknown in advance. Giving every attempt the same error allowance makes it difficult to control the probability of any false certification over the entire run. Indexing actual certification attempts by ℓ, one allocation of a total error budget β is

βℓ=βℓ(ℓ+1),ℓ=1,2,…∑ℓ=1∞βℓ=β

The series telescopes to β. If each attempt’s error probability is bounded by βℓ even conditional on its starting history, the union bound controls the overall error by β despite dependence between attempts. Xu and Jiang, Section 4.2

Substituting this allocation into the checking rule gives

Kℓ=⌈log(1β)+log(ℓ)+log(ℓ+1)log(1ρ)⌉

For fixed β and ρ, Kℓ grows logarithmically in ℓ. Setting β = 0.01 and ρ = 0.9 gives the following checking limits.

Certification attempt ℓ Checks required with β = 0.01 and ρ = 0.9
1 51
10 89
100 132
1,000 175
10,000 219

A tenfold increase in the attempt index adds about 44 checks. If the first N attempts all use their full allowances, the total is O(Nlog(N)). Total runtime also depends on the time per LP solve and the number of candidates produced by branch-and-bound.

5. Allocating the error budget more evenly

Suppose there are exactly N attempts, all have the same ρ and checking cost, and every attempt runs to its limit without early stopping. Ignoring rounding, minimizing the total number of checks gives

minβ1,…,βN>0∑ℓ=1Nlog(1βℓ)log(1ρ)∑ℓ=1Nβℓ≤β

Convexity of the negative logarithm gives the optimal allocation βℓ=βN. With N = 100, β = 0.01, and ρ = 0.9, equal allocation requires 88 checks each, or 8,800 in total. The earlier schedule requires 11,370 over its first 100 attempts, so equal allocation uses about 22.6% fewer checks in this comparison.

N must be an enforced limit. Expecting to finish after roughly 100 attempts, allocating the entire budget accordingly, and then certifying attempt 101 in the same way exceeds the budget. Further attempts require a reserve.

When the count is unknown, a possible alternative with a prespecified a ≥ 1 is

βℓ=βa(a+ℓ−1)(a+ℓ)∑ℓ=1∞βℓ=β,a≥1

Its sum remains β, and a = 1 recovers the original schedule. When ℓ is much smaller than a, βℓ≈βa, so early allocations are nearly uniform. A larger a reserves more budget for later attempts but permits less error initially, requiring more early checks. It can be costly when a run finishes quickly.

6. The checking limit versus actual checks

Once a violation is found, its cut can be added and certification stopped. For a fixed violating candidate, let T be the first detection time. Under the conditional miss bound,

𝔼[min(T,Kℓ)]=∑t=0Kℓ−1Pr(T>t)≤∑t=0Kℓ−1ρt≤11−ρ

With ρ = 0.9, the expected number of checks is at most 10. This bound is unchanged whether the checking limit is 51 or 219. A candidate with no violation, however, has nothing to discover and must use its full checking allowance.

An allocation that minimizes runtime therefore also depends on which candidates are rejected quickly and which reach the end of certification. The arithmetic advantage of equal allocation need not transfer directly to actual runs.

The value of ρ has a particularly large effect. As ρ approaches one,

Kℓ≈log(1βℓ)1−ρ

For βℓ=10−4, ρ = 0.9 requires 88 checks and ρ = 0.99 requires 917. Error-budget allocation should be examined together with the search’s ability to discover rare violations.

7. Continuing a separate chain for each integer design

In continuous optimization, an analysis can let the chain track designs that move by small steps. Branch-and-bound candidates need not behave that way. A design that opens only facility A may be followed immediately by one that opens only B.

Split x into integer variables xz and continuous variables xc. Consider retaining, for each integer assignment, the last scenario, the last continuous design, and the number of oracle calls.

Visit Opening decisions (A, B) Capacities (A, B) Chain used
1 (1, 0) (50, 0) Create the A-only chain
2 (0, 1) (0, 70) Create the B-only chain
3 (1, 0) (52, 0) Resume the A-only chain

If the A-only chain ended its first visit at scenario 17, the third visit starts there. What is retained is the scenario index. Capacities have changed, so costs and acceptance probabilities must be evaluated at the new design.

Even with the same integer assignment, a capacity jump from 50 to 500 can make the old state poorly suited to the current design. One can use a single transition after a small continuous change and extra transitions at the fixed new design after a large change. Xu and Jiang, Section 4.1

Although chain memory is maintained by assignment, the cuts derived earlier are valid over the entire design domain and can accumulate in a shared cut pool. Extra transitions help search for scenarios; failure to find a violation still requires certification.

8. Certified upper bounds and solver termination

The candidate-processing sequence is:

  1. When branch-and-bound presents an integer-feasible candidate, select its assignment’s chain and take transitions according to the design change.
  2. If a violating scenario is found, add its valid Benders cut.
  3. Otherwise, fix the candidate and certify it using its allocated error budget. Add a cut if a violation appears; accept the proposed upper bound if every check misses.
  4. Use the difference between a certified upper bound and a valid global lower bound to decide when to stop.

Cost tolerance and error probability must be distinguished. If the certification target is relaxed to Q⋆(x¯)≤θ¯+εcert, the objective upper bound must be

U=f(x¯)+θ¯+εcert

The tolerance εcert has cost units and must be added to the bound. The violation set must also be changed to scenarios exceeding the relaxed threshold, and ρ must be justified for missing that set. The dimensionless β is the budget for falsely certifying that condition.

If a valid global lower bound L and the certified candidate’s U satisfy U−L≤εopt, then, on the event that every certificate used is correct,

0≤F(x¯)−F⋆≤U−L≤εopt

With the total error budget respected, that event has probability at least 1 − β. The guarantee depends on both the conditional certification bound and a valid lower bound. Implementation must account for cost tolerance in incumbent comparisons and pruning. Discarding promising nodes using uncertified sample values and adjusting the upper bound only at the end does not preserve this argument.

For practical certification, the paper describes using empirical quantiles from warm-start samples and reports ρ = 0.9 and εcert=100 in its mixed-integer experiments. Xu and Jiang, EC.9

That empirical choice does not automatically establish a conditional bound for every candidate and history without a detected violation. Estimates may be optimistic if the samples emphasize easy candidates or miss rare violations. Experiments comparing certification schedules should therefore check the final candidate against every scenario as well as report LP counts and runtime. This separates lower checking cost from the effect of incorrectly accepting candidates.