Optimization
Approximate constrained stochastic optimal control via parameterized input inference
Syed, Shahbaz P Qadri, Bai, He
Approximate methods to solve stochastic optimal control (SOC) problems have received significant interest from researchers in the past decade. Probabilistic inference approaches to SOC have been developed to solve nonlinear quadratic Gaussian problems. In this work, we propose an Expectation-Maximization (EM) based inference procedure to generate state-feedback controls for constrained SOC problems. We consider the inequality constraints for the state and controls and also the structural constraints for the controls. We employ barrier functions to address state and control constraints. We show that the expectation step leads to smoothing of the state-control pair while the the maximization step on the non-zero subsets of the control parameters allows inference of structured stochastic optimal controllers. We demonstrate the effectiveness of the algorithm on unicycle obstacle avoidance, four-unicycle formation control, and quadcopter navigation in windy environment examples. In these examples, we perform an empirical study on the parametric effect of barrier functions on the state constraint satisfaction. We also present a comparative study of smoothing algorithms on the performance of the proposed approach.
Asynchronous and Stochastic Distributed Resource Allocation
Li, Qiang, Yemini, Michal, Wai, Hoi-To
This work proposes and studies the distributed resource allocation problem in asynchronous and stochastic settings. We consider a distributed system with multiple workers and a coordinating server with heterogeneous computation and communication times. We explore an approximate stochastic primal-dual approach with the aim of 1) adhering to the resource budget constraints, 2) allowing for the asynchronicity between the workers and the server, and 3) relying on the locally available stochastic gradients. We analyze our Asynchronous stochastic Primal-Dual (Asyn-PD) algorithm and prove its convergence in the second moment to the saddle point solution of the approximate problem at the rate of $O(1/t)$, where $t$ is the iteration number. Furthermore, we verify our algorithm numerically to validate the analytically derived convergence results, and demonstrate the advantages of utilizing our asynchronous algorithm rather than deploying a synchronous algorithm where the server must wait until it gets update from all workers.
Gaming and Cooperation in Federated Learning: What Can Happen and How to Monitor It
Kim, Dongseok, Jeong, Wonjun, Oh, Gisung
The success of Federated Learning depends on the actions that participants take out of sight. We model Federated Learning not as a mere optimization task but as a strategic system entangled with rules and incentives. From this perspective, we present an analytical framework that makes it possible to clearly identify where behaviors that genuinely improve performance diverge from those that merely target metrics. We introduce two indices that respectively quantify behavioral incentives and collective performance loss, and we use them as the basis for consistently interpreting the impact of operational choices such as rule design, the level of information disclosure, evaluation methods, and aggregator switching. We further summarize thresholds, auto-switch rules, and early warning signals into a checklist that can be applied directly in practice, and we provide both a practical algorithm for allocating limited audit resources and a performance guarantee. Simulations conducted across diverse environments consistently validate the patterns predicted by our framework, and we release all procedures for full reproducibility. While our approach operates most strongly under several assumptions, combining periodic recalibration, randomization, and connectivity-based alarms enables robust application under the variability of real-world operations. We present both design principles and operational guidelines that lower the incentives for metric gaming while sustaining and expanding stable cooperation.
A Rollout-Based Algorithm and Reward Function for Resource Allocation in Business Processes
Middelhuis, Jeroen, Bukhsh, Zaharah, Adan, Ivo, Dijkman, Remco
Resource allocation plays a critical role in minimizing cycle time and improving the efficiency of business processes. Recently, Deep Reinforcement Learning (DRL) has emerged as a powerful technique to optimize resource allocation policies in business processes. In the DRL framework, an agent learns a policy through interaction with the environment, guided solely by reward signals that indicate the quality of its decisions. However, existing algorithms are not suitable for dynamic environments such as business processes. Furthermore, existing DRL-based methods rely on engineered reward functions that approximate the desired objective, but a misalignment between reward and objective can lead to undesired decisions or suboptimal policies. To address these issues, we propose a rollout-based DRL algorithm and a reward function to optimize the objective directly. Our algorithm iteratively improves the policy by evaluating execution trajectories following different actions. Our reward function directly decomposes the objective function of minimizing the cycle time, such that trial-and-error reward engineering becomes unnecessary. We evaluated our method in six scenarios, for which the optimal policy can be computed, and on a set of increasingly complex, realistically sized process models. The results show that our algorithm can learn the optimal policy for the scenarios and outperform or match the best heuristics on the realistically sized business processes.
Surrogate Benchmarks for Model Merging Optimization
Akizuki, Rio, Kudo, Yuya, Yoshinari, Nozomu, Hirose, Yoichi, Nishimoto, Toshiyuki, Uchida, Kento, Shirakawa, Shinichi
Model merging techniques aim to integrate the abilities of multiple models into a single model. Most model merging techniques have hyperparameters, and their setting affects the performance of the merged model. Because several existing works show that tuning hyperparameters in model merging can enhance the merging outcome, developing hyperparameter optimization algorithms for model merging is a promising direction. However, its optimization process is computationally expensive, particularly in merging LLMs. In this work, we develop surrogate benchmarks for optimization of the merging hyperparameters to realize algorithm development and performance comparison at low cost. We define two search spaces and collect data samples to construct surrogate models to predict the performance of a merged model from a hyperparameter. We demonstrate that our benchmarks can predict the performance of merged models well and simulate optimization algorithm behaviors.
AdaSwitch: An Adaptive Switching Meta-Algorithm for Learning-Augmented Bounded-Influence Problems
Chen, Xi, Chen, Yuze, Zhou, Yuan
We study a class of multi-period online decision-making problems with sequence-based predictions, which may be generated by machine learning models but whose accuracy is not guaranteed. In each period, the decision-maker observes the realized request and must take an irrevocable action that yields a reward or incurs a cost, without knowledge of future arrivals. We introduce a bounded-influence framework, in which past decisions and requests exert only limited impact on the future optimal reward. Within this framework, we propose the AdaSwitch meta-algorithm, which exploits predictions to attain performance close to the offline benchmark when predictions are accurate, while preserving classical competitive-ratio guarantees under highly inaccurate predictions. Our framework and meta-algorithm apply to diverse settings, including lead-time quotation in processing systems, the $k$-server problem, and online allocation of reusable resources. These applications illustrate the flexibility and broad applicability of our approach to learning-augmented online decision-making.
Systematic Evaluation of Trade-Offs in Motion Planning Algorithms for Optimal Industrial Robotic Work Cell Design
de Mathelin, G., Hartl-Nesic, C., Kugi, A.
The performance of industrial robotic work cells depends on optimizing various hyperparameters referring to the cell layout, such as robot base placement, tool placement, and kinematic design. Achieving this requires a bilevel optimization approach, where the high-level optimization adjusts these hyperparameters, and the low-level optimization computes robot motions. However, computing the optimal robot motion is computationally infeasible, introducing trade-offs in motion planning to make the problem tractable. These trade-offs significantly impact the overall performance of the bilevel optimization, but their effects still need to be systematically evaluated. In this paper, we introduce metrics to assess these trade-offs regarding optimality, time gain, robustness, and consistency. Through extensive simulation studies, we investigate how simplifications in motion-level optimization affect the high-level optimization outcomes, balancing computational complexity with solution quality. The proposed algorithms are applied to find the time-optimal kinematic design for a modular robot in two palletization scenarios.
Privacy-Utility Trade-off in Data Publication: A Bilevel Optimization Framework with Curvature-Guided Perturbation
Yin, Yi, Zhang, Guangquan, Zuo, Hua, Lu, Jie
Machine learning models require datasets for effective training, but directly sharing raw data poses significant privacy risk such as membership inference attacks (MIA). To mitigate the risk, privacy-preserving techniques such as data perturbation, generalization, and synthetic data generation are commonly utilized. However, these methods often degrade data accuracy, specificity, and diversity, limiting the performance of downstream tasks and thus reducing data utility. Therefore, striking an optimal balance between privacy preservation and data utility remains a critical challenge. To address this issue, we introduce a novel bilevel optimization framework for the publication of private datasets, where the upper-level task focuses on data utility and the lower-level task focuses on data privacy. In the upper-level task, a discriminator guides the generation process to ensure that perturbed latent variables are mapped to high-quality samples, maintaining fidelity for downstream tasks. In the lower-level task, our framework employs local extrinsic curvature on the data manifold as a quantitative measure of individual vulnerability to MIA, providing a geometric foundation for targeted privacy protection. By perturbing samples toward low-curvature regions, our method effectively suppresses distinctive feature combinations that are vulnerable to MIA. Through alternating optimization of both objectives, we achieve a synergistic balance between privacy and utility. Extensive experimental evaluations demonstrate that our method not only enhances resistance to MIA in downstream tasks but also surpasses existing methods in terms of sample quality and diversity.
Genetic Programming with Model Driven Dimension Repair for Learning Interpretable Appointment Scheduling Rules
Zhang, Huan, Wang, Yang, Jia, Ya-Hui, Mei, Yi
--Appointment scheduling is a great challenge in healthcare operations management. Appointment rules (AR) provide medical practitioners with a simple yet effective tool to determine patient appointment times. Genetic programming (GP) can be used to evolve ARs. However, directly applying GP to design ARs may lead to rules that are difficult for end-users to interpret and trust. A key reason is that GP is unaware of the dimensional consistency, which ensures that the evolved rules align with users' domain knowledge and intuitive understanding. In this paper, we develop a new dimensionally aware GP algorithm with dimension repair to evolve ARs with dimensional consistency and high performance. A key innovation of our method is the dimension repair procedure, which optimizes the dimensional consistency of an expression tree while minimizing structural changes and ensuring that its output dimension meets the problem's requirements. We formulate the task as a mixed-integer linear programming model that can be efficiently solved using common mathematical programming methods. With the support of the dimension repair procedure, our method can explore a wider range of AR structures by temporarily breaking the dimensional consistency of individuals, and then restoring it without altering their overall structure, thereby identifying individuals with greater potential advantages. We evaluated the proposed method in a comprehensive set of simulated clinics. The experimental results demonstrate that our approach managed to evolve high-quality ARs that significantly outperform not only the manually designed ARs but also existing state-of-the-art dimensionally aware GP methods in terms of both objective values and dimensional consistency. In addition, we analyzed the semantics of the evolved ARs, providing insight into the design of more effective and interpretable ARs. PPOINTMENT scheduling plays a crucial role in healthcare systems, impacting clinical, operational, and financial performance. A well-designed appointment system can improve the efficiency of medical providers and patient satisfaction by smoothing demand and mitigating uncertainty in patient arrivals [1]. Patients expect fast and timely service and find long wait times increasingly difficult to tolerate. Medical providers face pressure to efficiently utilize resources, including doctors' availability and expensive diagnostic machines.
QUBO-based training for VQAs on Quantum Annealers
Acosta, Ernesto, Botella, Guillermo, Cano, Carlos
Quantum annealers provide an effective framework for solving large-scale combinatorial optimization problems. This work presents a novel methodology for training Variational Quantum Algorithms (VQAs) by reformulating the parameter optimization task as a Quadratic Unconstrained Binary Optimization (QUBO) problem. Unlike traditional gradient-based methods, our approach directly leverages the Hamiltonian of the chosen VQA ansatz and employs an adaptive, metaheuristic optimization scheme. This optimization strategy provides a rich set of configurable parameters which enables the adaptation to specific problem characteristics and available computational resources. The proposed framework is generalizable to arbitrary Hamiltonians and integrates a recursive refinement strategy to progressively approximate high-quality solutions. Experimental evaluations demonstrate the feasibility of the method and its ability to significantly reduce computational overhead compared to classical and evolutionary optimizers, while achieving comparable or superior solution quality. These findings suggest that quantum annealers can serve as a scalable alternative to classical optimizers for VQA training, particularly in scenarios affected by barren plateaus and noisy gradient estimates, and open new possibilities for hybrid quantum gate - quantum annealing - classical optimization models in near-term quantum computing.