Resource-Capacity Formulations and Relax-and-Fix Heuristics

Definitions and mathematical statement

Research problem. Find tighter formulations for resource-capacity constraints in mixed-integer supply-chain optimization, and determine how relax-and-fix heuristics can be combined with RINS. The source specifies no particular supply-chain model, resource system, objective, or guarantee, so the request concerns model-dependent formulations and algorithms.

For a fixed model, let $F\subset{\mathbb{R}}^p\times{\mathbb{Z}}^q$ denote its feasible decisions. A formulation must preserve $F$, including the resource-capacity restrictions. To compare two formulations with continuous relaxation polyhedra $P_1,P_2$, project them to the same original decision space by $\pi_1,\pi_2$. One precise meaning of a tighter relaxation is $\operatorname{conv}(F)\subseteq\pi_2(P_2)\subseteq\pi_1(P_1)$, with strict improvement on relevant instances; strengthening a relaxation must not delete feasible integral decisions. This interpretation does not specify which valid inequalities or additional variables work for the omitted model.

Relax-and-fix partitions the integer variables, imposes integrality on selected blocks while temporarily relaxing others, and fixes decisions progressively. RINS (relaxation-induced neighborhood search) uses a feasible incumbent and a relaxation solution to define a restricted mixed-integer neighborhood, typically fixing integer variables on which the two solutions agree. The problem asks for effective combinations of these mechanisms, including how blocks, fixing decisions, and neighborhoods should interact. Performance criteria, feasibility recovery, computational budgets, and any approximation or optimality theorem remain to be specified; fixing variables heuristically by itself guarantees neither feasibility of all later subproblems nor global optimality.

The supplied assessment dated 2026-08-21 calls this partially solved: tighter capacity formulations and combinations of relax-and-fix, RINS, fix-and-optimize, and related matheuristics are widely developed for particular mixed-integer supply-chain models, but no universal best formulation or combination with a general optimality guarantee is supplied. This is dated curation, not an independently verified impossibility claim.

Short English statement

Strengthen the resource-capacity models used in supply-chain optimization and design effective combinations of relax-and-fix with RINS. The question leaves the underlying model and performance criterion open; a tighter relaxation must still preserve every feasible integral solution.

Sources

• Local UnsolvedMath registry, permanent ID 30000007, code catalogue entry; Resource-Capacity Formulations and Relax-and-Fix Heuristics, Oberwolfach Reports Open Problems.
• Mathematics in the Supply Chain (2005), Oberwolfach Reports, DOI 10.4171/owr/2004/19, pp. 963--1036. https://doi.org/10.4171/owr/2004/19. Proposed year and year tag: 2004; no proposer named.
• Supplied literature label worst-case analysis of relax-and-fix: https://www.sciencedirect.com/science/article/abs/pii/S0377221719304850.
• Supplied literature label relax-and-fix in lot sizing: https://arxiv.org/abs/2107.10738.
• Supplied literature label generalized relax-and-fix: https://www.sciencedirect.com/science/article/pii/S0305054822002684.
• Literature triage checked 2026-08-21, status partially_solved; record updated 2026-09-16. Verify time-sensitive status and cited claims independently.