ors-methods

Proof & Algorithm Methodology (ors-methods)

When to trigger

• The model and claims exist (ors-theory-development) and now must be proved or guaranteed.
• You need to pick a proof strategy or design an algorithm with provable guarantees.
• A reviewer says "the proof of Theorem X has a gap" or "the rate is not established."

Match the machinery to the result

Operations Research is mathematically rigorous: the contribution lives or dies on the soundness and strength of the analysis. Pick technique by methodology:

Result you need	Typical machinery
Optimality / strong duality	LP/conic duality, KKT, polyhedral / total unimodularity, submodularity
Approximation guarantee	LP/SDP rounding, primal-dual, greedy + submodular bounds
Complexity / hardness	reductions (NP-hardness), oracle lower bounds
Convergence & rate	monotonicity/Lyapunov, fixed-point/contraction, first-order analysis
Steady-state / stability	Foster-Lyapunov, regenerative arguments, fluid/diffusion limits
Stochastic comparison / bounds	coupling, stochastic dominance, martingale/concentration inequalities
MDP / dynamic decisions	dynamic programming, value/policy iteration, ADP with error bounds
Heavy-traffic / asymptotics	functional CLT, weak convergence, state-space collapse

Algorithm design with guarantees

• State what the algorithm guarantees: exact/optimal, an approximation factor, an ε-stationary point, or a regret/convergence rate — and under which assumptions.
• Give complexity (time, iterations, oracle calls; per-iteration cost and total).
• Separate the method from its proof of correctness/convergence; a fast heuristic without analysis is not an OR methodological contribution on its own.

Simulation methodology (when the analysis is empirical-stochastic)

• Specify the estimator and argue consistency; quantify error with valid confidence intervals (batch means, regenerative, or replication-based).
• Use variance reduction (common random numbers, control variates) and justify it.
• For ranking-and-selection / simulation optimization, state the statistical guarantee (e.g., probability of correct selection) and the budget rule.

Proof hygiene OR reviewers expect

• Every assumption used is invoked explicitly where the proof needs it.
• Long proofs go to an e-companion (which must not be longer than the manuscript); the main text keeps the key idea and a proof sketch.
• Constants and rates are tracked, not hidden in "O(·)" when tightness is claimed.

Methodology pushback patterns and the OR fix

Referee remark	Underlying defect	Fix that meets the OR bar
"Proof of Theorem X has a gap"	an assumption invoked implicitly	name where each hypothesis is used; add a lemma to bridge the step
"The rate is asserted, not established"	rate read off numerical curves	prove it analytically (Lyapunov / contraction / first-order) with tracked constants
"Algorithm has no guarantee"	a fast heuristic without analysis	attach an approximation factor, ε-stationarity, or regret/convergence bound
"Bound may not be tight"	only an upper bound shown	exhibit a matching instance, or reframe explicitly as best-known
"Simulation conclusions unreliable"	point estimates, no error control	report CIs (batch-means/regenerative) and variance reduction with the rule
"Structural result not connected to the application"	theorem floats free of the decision	show the guarantee changes the operational policy it motivates

Operations Research, as the INFORMS flagship, lives on soundness and strength of analysis: a heuristic without a guarantee is an INFORMS Journal on Computing artifact, not an OR methodological contribution. The machinery table above exists so each claim is discharged by analysis a referee can verify line by line.

Worked machinery walk-through (illustrative)

Target result: an approximation algorithm for a stochastic-covering problem with a claimed 1.5-factor guarantee (illustrative). Machinery selection from the table: LP-rounding + primal-dual for the factor; concentration (martingale) to control the stochastic constraint; an oracle lower bound to argue the factor cannot be pushed below 1.5 without stronger assumptions. Proof hygiene: each of the three assumptions (bounded second moment, independence across stages, integral demand) is cited exactly where the argument needs it; the full rounding analysis goes to the e-companion, the main text keeps the primal-dual sketch and the tight-instance construction. This produces a theorem-grade result and a tightness statement — the combination OR referees reward over a bare upper bound.

Anti-patterns

• A "proof" that silently adds an assumption mid-argument.
• Claiming a rate from numerical curves rather than analysis.
• An algorithm with no guarantee presented as the central contribution.
• Simulation conclusions with no confidence intervals or variance control.

Output format

【Result → technique】each Thm/Prop mapped to its machinery
【Algorithm】guarantee (exact/approx/rate) + complexity
【Simulation】estimator, CI method, variance reduction (if used)
【Proof hygiene】assumptions invoked explicitly; e-companion plan
【Open gaps】[...]
【Next step】ors-data-analysis