More Like this

1. A Parallel Approximation Algorithm for Maximizing Submodular b-Matching

   https://doi.org/10.1137/1.9781611976830.5  

   Ferdous, S; Pothen, A; Khan, A.; Panyala, A.; Halappanavar, M. (August 2021, Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21))

   Bender, M.; Gilbert, J.; Hendrickson, B.; Sullivan, B. (Ed.)

   We design new serial and parallel approximation algorithms for computing a maximum weight b-matching in an edge-weighted graph with a submodular objective function. This problem is NP-hard; the new algorithms have approximation ratio 1/3, and are relaxations of the Greedy algorithm that rely only on local information in the graph, making them parallelizable. We have designed and implemented Local Lazy Greedy algorithms for both serial and parallel computers. We have applied the approximate submodular b-matching algorithm to assign tasks to processors in the computation of Fock matrices in quantum chemistry on parallel computers. The assignment seeks to reduce the run time by balancing the computational load on the processors and bounding the number of messages that each processor sends. We show that the new assignment of tasks to processors provides a four fold speedup over the currently used assignment in the NWChemEx software on 8000 processors on the Summit supercomputer at Oak Ridge National Lab. 

   more » « less
2. Multi-Objective Optimization of Space Exploration Campaign Schedules with Stochastic Launch Delay

   https://doi.org/10.2514/1.A36412  

   Gollins, Nicholas; Grieser, Zachary; Ho, Koki (January 2026, Journal of Spacecraft and Rockets)

   Complex, multimission space exploration campaigns are particularly vulnerable to payload development and launch delays due to program-level schedule constraints and interactions between the payloads. While deterministic space logistics problems seek strongly performing (e.g., minimized cost) solutions, stochastic models must balance performance with robustness. The introduction of stochastic delays to the otherwise deterministic problem produces large and computationally intractable optimization problems. This paper presents and compares two multi-objective (minimized cost vs robustness) formulations for the stochastic campaign scheduling problem. First, a multi-objective mixed-integer quadratically constrained program (MOMIQCP) formulation is presented. Secondly, due to the computational intractability of the MOMIQCP for large problems, a method for constructing restricted, deterministic scheduling subproblems is defined. These subproblems are input to a noisy multi-objective evolutionary algorithm (NMOEA), which is used for the purpose of stochastically applying delays to the deterministic subproblem and building approximations of the objectives of the stochastic problems. Both methods are demonstrated through case studies, and the results demonstrate that the NMOEA can successfully find strongly performing solutions to larger stochastic scheduling problems. 

   more » « less
3. A single-loop stochastic feasible interior-point algorithm for nonlinear inequality-constrained optimization

   https://doi.org/10.1007/s10107-025-02320-2  

   Curtis, Frank_E; Jiang, Xin; Wang, Qi (January 2026, Mathematical Programming)

   Abstract An interior-point algorithm framework is proposed, analyzed, and tested for solving nonlinearly constrained continuous optimization problems. The main setting of interest is when the objective and inequality constraint functions may be nonlinear and/or nonconvex, and when constraint values and derivatives are tractable to compute, but objective function values and derivatives can only be estimated. The algorithm is intended primarily for a setting that is similar for stochastic-gradient methods for unconstrained optimization, i.e., the setting when stochastic-gradient estimates are available and employed in place of gradients, and when no objective function values (nor estimates of them) are employed. This is achieved by the interior-point framework having a single-loop structure rather than the nested-loop structure that is typical of contemporary interior-point methods. Convergence guarantees for the framework are provided both for deterministic and stochastic settings. Numerical experiments show that the algorithm yields good performance on a large set of test problems. 

   more » « less
4. Optimization landscape of Tucker decomposition

   https://doi.org/10.1007/s10107-020-01531-z  

   Frandsen, Abraham; Ge, Rong (January 2020, Mathematical Programming)

   Tucker decomposition is a popular technique for many data analysis and machine learning applications. Finding a Tucker decomposition is a nonconvex optimization problem. As the scale of the problems increases, local search algorithms such as stochastic gradient descent have become popular in practice. In this paper, we characterize the optimization landscape of the Tucker decomposition problem. In particular, we show that if the tensor has an exact Tucker decomposition, for a standard nonconvex objective of Tucker decomposition, all local minima are also globally optimal. We also give a local search algorithm that can nd an approximate local (and global) optimal solution in polynomial time. 

   more » « less
5. A Simple and Fast Bi-Objective Search Algorithm

   Hernandez, C.; Yeoh, W.; Baier, J.; Zhang, H.; Suazo, L.; Koenig, S. (June 2020, Proceedings of the International Conference on Automated Planning and Scheduling)

   Many interesting search problems can be formulated as bi-objective search problems, that is, search problems where two kinds of costs have to be minimized, for example, travel distance and time for transportation problems. Bi-objective search algorithms have to maintain the set of undominated paths from the start state to each state to compute the set of paths from the start state to the goal state that are not dominated by some other path from the start state to the goal state (called the Pareto-optimal solution set). Each time they find a new path to a state s, they perform a dominance check to determine whether this path dominates any of the previously found paths to s or whether any of the previously found paths to s dominates this path. Existing algorithms do not perform these checks efficiently. On the other hand, our Bi-Objective A* (BOA*) algorithm requires only constant time per check. In our experimental evaluation, we show that BOA* can run an order of magnitude (or more) faster than state-of-the-art bi-objective search algorithms, such as NAMOA*, NAMOA*dr, Bi-Objective Dijkstra, and Bidirectional Bi-Objective Dijkstra. 

   more » « less