Basis Selection for Lagrangian Decision-Rule Approximations

Definitions and mathematical statement

A multistage stochastic mixed-integer program (MSMIP) is a stochastic optimization model with decisions made at successive stages, some decision components constrained to be integer-valued, and information restrictions governing dependence on observed randomness. The supplied record does not specify the particular MSMIP, its probability model, its constraints, or the Lagrangian relaxation under consideration.

Here LDR denotes a linear decision rule: a function represented as a linear combination of prescribed basis functions. In the Lagrangian-dual setting, these rules restrict the dependence of dual multipliers on stochastic information. Schematically, for a stage $t$, one may write \[ \lambda_t=\sum_{j=1}^{m_t}\theta_{tj}\phi_{tj}, \] where $\phi_{tj}$ are selected basis functions of the information permitted for the multiplier at that stage, $m_t$ is the number of basis functions, and $\theta_{tj}$ are deterministic coefficients of compatible dimensions. This is explanatory notation for a finite-basis restriction, not a specification of the source's model. The multiplier information, dimensions, admissibility conditions, and meaning of equality of random functions remain unspecified.

Research question. For LDR restrictions in Lagrangian duals of the multistage stochastic mixed-integer program (MSMIP), which basis functions should be used in the LDR approximations, and how can the resulting restricted Lagrangian-dual problems be optimized efficiently?

More explicitly, the requested tasks are to select basis functions for the dual decision rules and to develop efficient methods for optimizing the corresponding restricted dual objective over admissible coefficients. The record supplies neither a particular dual objective nor a quantified criterion for basis quality or computational efficiency. Consequently, it does not determine a unique optimization problem, convergence assertion, or complexity claim. These qualifications must be resolved before this research question can be replaced by a fully quantified mathematical statement.

Short English statement

Choose basis functions for linear decision-rule restrictions of Lagrangian dual multipliers in multistage stochastic mixed-integer programming, and develop efficient methods for optimizing the restricted duals. The supplied record leaves the model class, admissibility requirements, approximation criteria, and meaning of efficiency unspecified.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30003932$, title: Basis Selection for Lagrangian Decision-Rule Approximations; source problem code: catalogue entry. Collection: Oberwolfach Reports Open Problems. No individual proposer is named; the proposed year is recorded as 2018.
• Supplied source citation: New Directions in Stochastic Optimisation (2019), Oberwolfach Reports, pp. 2303--2384, DOI 10.4171/owr/2018/38. https://doi.org/10.4171/owr/2018/38. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source: Lagrangian Dual Decision Rules for Multistage Stochastic Mixed-Integer Programming. https://doi.org/10.1287/opre.2022.2366.
• Supplied literature source: Oberwolfach Report 38/2018. https://doi.org/10.4171/owr/2018/38.
• Literature assessment dated 2026-08-21: the supplied curation labels the problem partially_solved and states that later Lagrangian dual decision-rule work supplies computable stagewise and nonanticipative bounds and primal policies, while general basis selection with convergence guarantees and uniformly efficient optimization remains unresolved. This is supplied dated curation derived from the OWR record, not an independently verified literature assessment. Its status and cited claims require independent verification.