Other Topics

Pareto Frontier of LLM Test-time Compute: Adaptive Rollouts and Voting Under Token Budgets

Categories Applications - OR and Management Sciences, Optimization in Data Science, Other Topics Tags , ,

Large language models improve test-time accuracy by generating multiple rollouts and aggregating these answers. As generating additional rollouts consumes more tokens, test-time compute faces a fundamental cost accuracy trade-off, naturally raising the question: given a fixed token budget, how to allocate the budget to maximize accuracy? Existing approaches typically adapt the number of rollouts for … Read more

SDDP has polynomial iteration complexity in the horizon

Categories Dynamic Programming, Stochastic Programming Tags , , , ,

Stochastic dual dynamic programming (SDDP) and its variants are run in practice with forward passes that sample the noise at random. Recent iteration-complexity results favour another choice: when the trial points are selected deterministically, for instance along the scenario with the largest gap, the number of iterations is polynomial in the horizon $T$, whereas every … Read more

Bundle Pricing via Learning the Market from Customer Preferences

Categories Finance and Economics, Optimization in Data Science, Other Topics

We study the problem of learning revenue-maximizing bundle prices when customer valuations and market composition are unknown and the firm observes only customer choices. This problem is challenging because the number of bundle-price decisions grows exponentially with the number of items offered. We develop BLMP (Bundle Pricing via Learning the Market from Customer Preferences), a … Read more

A tight 1/3–approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem

Categories Approximation Algorithms, Combinatorial Optimization, Dynamic Programming Tags , , ,

The \(\textit{Colored Knapsack Problem}\) (ColKP) generalizes the classical Knapsack Problem by partitioning the items into color classes and requiring the selected items to admit an ordering in which consecutive items have different colors. The problem is weakly \(\mathcal{NP}\)-hard and admits two pseudo-polynomial dynamic programming (DP) algorithms proposed in the literature. These two DP algorithms have … Read more

Differentiating Through Moving Recourse: Feasible Policy Optimization and Finite-Sample Certification for Multistage Stochastic Programs

Categories Dynamic Programming, Energy, Stochastic Programming Tags , , , , , , ,

Multistage stochastic programs model decisions under uncertainty where earlier decisions change later feasible sets. We propose a feasible pathwise gradient method (FeasPG) that can update the policy as new sample paths arrive. The policy proposes a decision and projects it onto the current feasible set, so every decision is feasible. We derive the full trajectory … Read more

Redundant objectives in multiobjective optimization

Categories Global Optimization, Multi-Criteria Optimization, Nonlinear Optimization Tags , , , , ,

This work examines three different concepts of objective redundancy in multiobjective optimization. Multiobjective optimization is known to suffer from the curse of dimensionality and we aim at reducing the number of objective functions which need to be considered. In this context, a set of objectives is called redundant if the sets of weakly efficient, efficient, … Read more

The fixed-point bundle method over product-of-simplex domains arising from game equilibria

Categories Complementarity and Variational Inequalities, Game Theory Tags , , , ,

Developing general-purpose algorithms with global asymptotic convergence guarantees for Nash equilibria of general-sum games remains a longstanding challenge. This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from simplex domains to product-of-simplex domains, enabling its direct application to Nash equilibrium computation. The resulting fixed-point bundle exhibits a composite fiber bundle structure. The … Read more

Twist Without Tangle: Flutter Suppression of Thin-Walled Wing-Engine Systems via Curvilinear Fiber Path Tailoring and Cross-Section Optimization

Categories Applications - Science and Engineering, Optimization of Simulated Systems, Optimization of Systems modeled by PDEs Tags , , ,

Flutter is traditionally delayed by modifying either a structure’s geometry or its stiffness distribution. Here, we show that allowing both to evolve simultaneously can unlock a fundamentally different route to aeroelastic stability. We concurrently optimize the cross-sectional geometry and fiber paths of a composite thin-walled wing–engine system to maximize flutter onset. The wing structure is … Read more

Scenario Tradeoffs in Uncertain Multiobjective Optimization

Categories Multi-Criteria Optimization, Robust Optimization Tags , , ,

Realistic decision problems are inherently multiobjective and uncertain. To manage both of these complexities, robust multiobjective optimization strives to aid the decision maker in finding a decision which is Pareto efficient and is hedged against the worst-case scenario. In this paper, we present a robustness approach which is grounded in the decision maker’s preferences by … Read more

Nonlinear optimization over trees with binary coupling decisions

Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Optimization in Data Science

Mixed integer nonlinear programs with binary coupling decisions naturally model selective coordination tasks where a fixed penalty is incurred whenever adjacent continuous variables differ. A prominent example is the classical Potts model, which is widely used in statistical inference. However, exact solvability remains theoretically challenging since the problem is NP hard on general graphs, and … Read more