Search

We study the quadratic cycle cover problem (QCCP), which aims to find a node-disjoint cycle cover in a directed graph with minimum interaction cost between successive arcs. We derive several semidefinite programming (SDP) relaxations and use facial reduction to make these strictly feasible. We investigate a nontrivial relationship between the transformation matrix used in the reduction and the structure of the graph, which is exploited in an efficient algorithm that constructs this matrix for any instance of the problem. To solve our relaxations, we propose an algorithm that incorporates an augmented Lagrangian method into a cutting-plane framework by utilizing Dykstra's projection algorithm. Our algorithm is suitable for solving SDP relaxations with a large number of cutting-planes. Computational results show that our SDP bounds and efficient cutting-plane algorithm outperform other QCCP bounding approaches from the literature. Finally, we provide several SDP-based upper bounding techniques, among which is a sequential Q-learning method that exploits a solution of our SDP relaxation within a reinforcement learning environment. Summary of Contribution: The quadratic cycle cover problem (QCCP) is the problem of finding a set of node-disjoint cycles covering all the nodes in a graph such that the total interaction cost between successive arcs is minimized. The QCCP has applications in many fields, among which are robotics, transportation, energy distribution networks, and automatic inspection. Besides this, the problem has a high theoretical relevance because of its close connection to the quadratic traveling salesman problem (QTSP). The QTSP has several applications, for example, in bioinformatics, and is considered to be among the most difficult combinatorial optimization problems nowadays. After removing the subtour elimination constraints, the QTSP boils down to the QCCP. Hence, an in-depth study of the QCCP also contributes to the construction of strong bounds for the QTSP. In this paper, we study the application of semidefinite programming (SDP) to obtain strong bounds for the QCCP. Our strongest SDP relaxation is very hard to solve by any SDP solver because of the large number of involved cutting-planes. Because of that, we propose a new approach in which an augmented Lagrangian method is incorporated into a cutting-plane framework by utilizing Dykstra's projection algorithm. We emphasize an efficient implementation of the method and perform an extensive computational study. This study shows that our method is able to handle a large number of cuts and that the resulting bounds are currently the best QCCP bounds in the literature. We also introduce several upper bounding techniques, among which is a distributed reinforcement learning algorithm that exploits our SDP relaxations. [ABSTRACT FROM AUTHOR]

The article presents a list of working papers related to management science. Some of the papers include "A Primal-Dual Surrogate Simplex Algorithm: Comparison with the Criss Cross Method," by R. S. Garfinkel and P. L. Yu, "Optimal Impulsive Trajectory Rendezvous Using Projection-Restoration," by W. A. Gruver, and "Asymptotic Normality of the Extremum of Certain Sample Functions," by P. K. Sen.

This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. MESP is widely applied to many areas, including healthcare, power systems, manufacturing, and data science. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to study efficient approximation algorithms and develop their approximation bounds for MESP, which improves the best known one in the literature. This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to develop a sampling algorithm and derive its approximation bound for MESP, which improves the best known bound in literature. We then provide an efficient deterministic implementation of the sampling algorithm with the same approximation bound. Besides, we investigate the widely used local search algorithm and prove its first known approximation bound for MESP. The proof techniques further inspire for us an efficient implementation of the local search algorithm. Our numerical experiments demonstrate that these approximation algorithms can efficiently solve medium-size and large-scale instances to near optimality. Finally, we extend the analyses to the A-optimal MESP, for which the objective is to minimize the trace of the inverse of the selected principal submatrix. Funding: This work was supported by the National Science Foundation Division of Information and Intelligent Systems [Grant 2246417] and Division of Civil, Mechanical and Manufacturing Innovation [Grant 2246414]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2023.2488. [ABSTRACT FROM AUTHOR]

Solving Rank Constrained Least Squares via Recursive Importance Sketching In statistics and machine learning, we sometimes run into the rank-constrained least squares problems, for which we need to find the best low-rank fit between sets of data, such as trying to figure out what factors are affecting the data, filling in missing information, or finding connections between different sets of data. This paper introduces a new method for solving this problem called the recursive importance sketching algorithm (RISRO), in which the central idea is to break the problem down into smaller, easier parts using a unique technique called "recursive importance sketching." This new method is not only easy to use, but it is also very efficient and gives accurate results. We prove that RISRO converges in a local quadratic-linear and quadratic rate under some mild conditions. Simulation studies also demonstrate the superior performance of RISRO. In this paper, we propose a recursive importance sketching algorithm for rank-constrained least squares optimization (RISRO). The key step of RISRO is recursive importance sketching, a new sketching framework based on deterministically designed recursive projections, and it significantly differs from the randomized sketching in the literature. Several existing algorithms in the literature can be reinterpreted under this new sketching framework, and RISRO offers clear advantages over them. RISRO is easy to implement and computationally efficient, and the core procedure in each iteration is to solve a dimension-reduced least squares problem. We establish the local quadratic-linear and quadratic rate of convergence for RISRO under some mild conditions. We also discover a deep connection of RISRO to the Riemannian Gauss–Newton algorithm on fixed rank matrices. The effectiveness of RISRO is demonstrated in two applications in machine learning and statistics: low-rank matrix trace regression and phase retrieval. Simulation studies demonstrate the superior numerical performance of RISRO. Funding: Y. Luo and A. Zhang were partially supported by the National Science Foundation [Grant CAREER-2203741]. W. Huang was partially supported by the Fundamental Research Funds for the Central Universities [Grant 20720190060] and the National Natural Science Foundation of China [Grant 12001455]. X. Li was partially supported by the National Natural Science Foundation of China [Grants 62141407 and 12271107], the Chenguang Program by the Shanghai Education Development Foundation and Shanghai Municipal Education Commission [Grant 19CG02], and the Shanghai Science and Technology Program [Grant 21JC1400600]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2445. [ABSTRACT FROM AUTHOR]

Discrete optimal transport problems give rise to very large linear programs (LPs) with a particular structure of the constraint matrix. In this paper, we present a hybrid algorithm that mixes an interior point method (IPM) and column generation, specialized for the LP originating from the Kantorovich optimal transport problem. Knowing that optimal solutions of such problems display a high degree of sparsity, we propose a column generation–like technique to force all intermediate iterates to be as sparse as possible. The algorithm is implemented nearly matrix-free. Indeed, most of the computations avoid forming the huge matrices involved and solve the Newton system using only a much smaller Schur complement of the normal equations. We prove theoretical results about the sparsity pattern of the optimal solution, exploiting the graph structure of the underlying problem. We use these results to mix iterative and direct linear solvers efficiently in a way that avoids producing preconditioners or factorizations with excessive fill-in and at the same time guaranteeing a low number of conjugate gradient iterations. We compare the proposed method with two state-of-the-art solvers and show that it can compete with the best network optimization tools in terms of computational time and memory use. We perform experiments with problems reaching more than four billion variables and demonstrate the robustness of the proposed method. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: F. Zanetti received funding from the University of Edinburgh, in the form of a PhD scholarship. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0184) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0184). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Optimal stopping is a fundamental class of stochastic dynamic optimization problems with numerous applications in finance and operations management. In "A nonparametric algorithm for optimal stopping based on robust optimization," the author introduces an approach based on robust optimization for computing near-optimal solutions for computationally demanding stochastic optimal stopping problems with known probability distributions. Through this new use of robust optimization, the paper develops new algorithms for solving stochastic optimal stopping problems that are practical and can outperform state-of-the-art simulation-based algorithms in the context of pricing high-dimensional financial options. Optimal stopping is a fundamental class of stochastic dynamic optimization problems with numerous applications in finance and operations management. We introduce a new approach for solving computationally-demanding stochastic optimal stopping problems with known probability distributions. The approach uses simulation to construct a robust optimization problem that approximates the stochastic optimal stopping problem to any arbitrary accuracy; we then solve the robust optimization problem to obtain near-optimal Markovian stopping rules for the stochastic optimal stopping problem. In this paper, we focus on designing algorithms for solving the robust optimization problems that approximate the stochastic optimal stopping problems. These robust optimization problems are challenging to solve because they require optimizing over the infinite-dimensional space of all Markovian stopping rules. We overcome this challenge by characterizing the structure of optimal Markovian stopping rules for the robust optimization problems. In particular, we show that optimal Markovian stopping rules for the robust optimization problems have a structure that is surprisingly simple and finite-dimensional. We leverage this structure to develop an exact reformulation of the robust optimization problem as a zero-one bilinear program over totally unimodular constraints. We show that the bilinear program can be solved in polynomial time in special cases, establish computational complexity results for general cases, and develop polynomial-time heuristics by relating the bilinear program to the maximal closure problem from graph theory. Numerical experiments demonstrate that our algorithms for solving the robust optimization problems are practical and can outperform state-of-the-art simulation-based algorithms in the context of widely-studied stochastic optimal stopping problems from high-dimensional option pricing. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2023.2461. [ABSTRACT FROM AUTHOR]

In this note we consider the validity of substituting a linear goal for a fractional goal in a mathematical program and provide a simple geometric interpretation that contrasts the essential differences between the two programs. [ABSTRACT FROM AUTHOR]

Ride-pooling, which accommodates multiple passenger requests in a single trip, has the potential to substantially enhance the throughput of mobility-on-demand (MoD) systems. This paper investigates MoD systems that operate mixed fleets composed of "basic supply" and "augmented supply" vehicles. When the basic supply is insufficient to satisfy demand, augmented supply vehicles can be repositioned to serve rides at a higher operational cost. We formulate the joint vehicle repositioning and ride-pooling assignment problem as a two-stage stochastic integer program, where repositioning augmented supply vehicles precedes the realization of ride requests. Sequential ride-pooling assignments aim to maximize total utility or profit on a shareability graph: a hypergraph representing the matching compatibility between available vehicles and pending requests. Two approximation algorithms for midcapacity and high-capacity vehicles are proposed in this paper; the respective approximation ratios are 1 / p 2 and (e − 1) / (2 e + o (1)) p ln p , where p is the maximum vehicle capacity plus one. Our study evaluates the performance of these approximation algorithms using an MoD simulator, demonstrating that these algorithms can parallelize computations and achieve solutions with small optimality gaps (typically within 1%). These efficient algorithms pave the way for various multimodal and multiclass MoD applications. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. Funding: This work was supported by the National Science Foundation [Grants CCF-2006778 and FW-HTF-P 2222806], the Ford Motor Company, and the Division of Civil, Mechanical, and Manufacturing Innovation [Grants CMMI-1854684, CMMI-1904575, and CMMI-1940766]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2021.0349. [ABSTRACT FROM AUTHOR]

We introduce a bundle method for the unconstrained minimization of nonsmooth difference-of-convex (DC) functions, and it is based on the calculation of a special type of descent direction called descent–ascent direction. The algorithm only requires evaluations of the minuend component function at each iterate, and it can be considered as a parsimonious bundle method as accumulation of information takes place only in case the descent–ascent direction does not provide a sufficient decrease. No line search is performed, and proximity control is pursued independent of whether the decrease in the objective function is achieved. Termination of the algorithm at a point satisfying a weak criticality condition is proved, and numerical results on a set of benchmark DC problems are reported. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms – Continuous. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0142) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2023.0142). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

This article presents comments by the author on a paper discussing heuristic and special case algorithms for dispersion problems. Problems discussed in this article are the subject of the paper in focus. The results presented in that paper include a simple heuristic for Max-Min Facility Dispersion (MMFD) which provides a performance guarantee of 1/2, and a similar heuristic for Max-Avg Facility Dispersion (MAFD) with a performance guarantee of 1/4. It is also proved there that obtaining a performance guarantee of more than 1/2 for MMFD is NP-hard. The paper also discussed the one- dimensional versions of MMFD and MAFD, where the vertex set V consists of a set of n points on the real line. Section 2 of the paper is devoted to the heuristic for MMPD. It should be noted that this heuristic was analyzed before. In fact, it is shown therein that the performance guarantee of 1/2, holds for a more general model where the selected set p is restricted to be in a compact subset of the network indiced by the edge distances.

The article presents comments on the management science paper "On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs," by William L. Maxwell. The paper focused on an integer programming formulation of a one-machine job shop problem. The author contends that Maxwell made in error in proving the validity of an optimal algorithm by applying cutting plane constraints to the problem. The author explains that the problem cannot be solved through traditional cutting plane procedures. The author provides a mathematical model in an attempt to correct the proof.

More than 40 years ago, Lions and Mercier introduced in a seminal paper the Douglas–Rachford algorithm. Today, this method is well-recognized as a classic and highly successful splitting method to find minimizers of the sum of two (not necessarily smooth) convex functions. Whereas the underlying theory has matured, one case remains a mystery: the behavior of the shadow sequence when the given functions have disjoint domains. Building on previous work, we establish for the first time weak and value convergence of the shadow sequence generated by the Douglas–Rachford algorithm in a setting of unprecedented generality. The weak limit point is shown to solve the associated normal problem, which is a minimal perturbation of the original optimization problem. We also present new results on the geometry of the minimal displacement vector. Funding: The research of H. H. Bauschke and W. M. Moursi was partially supported by Discovery Grants of the Natural Sciences and Engineering Research Council of Canada [Grants RGPIN-2018-03703 and RGPIN-2019-04803], respectively. [ABSTRACT FROM AUTHOR]

We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities when monetary transfers are not allowed. The competitive rule is known for its remarkable fairness and efficiency properties in the case of goods. This rule was extended to chores by Bogomolnaia, Moulin, Sandomirskiy, and Yanovskaya. For both goods and chores, the rule produces Pareto optimal and envy-free allocations. In the case of goods, the outcome of the competitive rule can be easily computed. Competitive allocations solve the Eisenberg-Gale convex program; hence the outcome is unique and can be approximately found by standard gradient methods. An exact algorithm that runs in polynomial time in the number of agents and goods was given by Orlin. In the case of chores, the competitive rule does not solve any convex optimization problem; instead, competitive allocations correspond to local minima, local maxima, and saddle points of the Nash social welfare on the Pareto frontier of the set of feasible utilities. The Pareto frontier may contain many such points and, consequently, the outcome of the competitive rule is no longer unique. In this paper, we show that all the outcomes of the competitive rule for chores can be computed in strongly polynomial time if either the number of agents or the number of chores is fixed. The approach is based on a combination of three ideas: all consumption graphs of Pareto optimal allocations can be listed in polynomial time; for a given consumption graph, a candidate for a competitive utility profile can be constructed via an explicit formula; each candidate can be checked for competitiveness and the allocation can be reconstructed using a maximum flow computation. Our algorithm immediately gives an approximately-fair allocation of indivisible chores by the rounding technique of Barman and Krishnamurthy. Funding: This work was supported by National Science Foundation (CNS 1518941); Lady Davis Fellowship Trust, Hebrew University of Jerusalem; H2020 European Research Council (740435); Linde Institute at Caltech. [ABSTRACT FROM AUTHOR]

The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of m linear inequalities in n variables (P):A⊤x≤u when its set of solutions has positive volume. However, when (P) is infeasible, the ellipsoid algorithm has no mechanism for proving that (P) is infeasible. This is in contrast to the other two fundamental algorithms for tackling (P) , namely, the simplex and interior-point methods, each of which can be easily implemented in a way that either produces a solution of (P) or proves that (P) is infeasible by producing a solution to the alternative system (Alt):Aλ=0, u⊤λ<0, λ≥0. This paper develops an oblivious ellipsoid algorithm (OEA) that either produces a solution of (P) or produces a solution of (Alt). Depending on the dimensions and other condition measures, the computational complexity of the basic OEA may be worse than, the same as, or better than that of the standard ellipsoid algorithm. We also present two modified versions of OEA, whose computational complexity is superior to that of OEA when n≪m. This is achieved in the first modified version by proving infeasibility without producing a solution of (Alt) , and in the second version by using more memory. Funding: J. Lamperski and R. M. Freund were supported by the Air Force Office of Scientific Research [Grant FA9550-19-1-0240]. [ABSTRACT FROM AUTHOR]

Model-based methods are popular in derivative-free optimization (DFO). In most of them, a single model function is built to approximate the objective function. This is generally based on the assumption that the objective function is one black box. However, some real-life and theoretical problems show that the objective function may consist of several black boxes. In those problems, the information provided by each black box may not be equal. In this situation, one can build multiple submodels that are then combined to become a final model. In this paper, we analyze the relation between the accuracy of those submodels and the model constructed through their operations. We develop a broad framework that can be used as a theoretical tool in model error analysis and future research in DFO algorithm design. Funding: Y. Chen's research is partially funded by the MITACS Globalink program. All authors research partially supported by NSERC of Canada Discovery [Grant 2018-03865]. [ABSTRACT FROM AUTHOR]

Traditional clustering algorithms such as k-means and vanilla spectral clustering are known to deteriorate significantly in the presence of outliers. Several previous works in literature have proposed robust variants of these algorithms; however, they do not provide any theoretical guarantees. Extending previous clustering literature on Gaussian mixture models, in their paper "A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers," Prateek R. Srivastava, Purnamrita Sarkar, and Grani A. Hanasusanto developed a new spectral clustering algorithm and provided error bounds for the algorithm under a general sub-Gaussian mixture model setting with outliers. Surprisingly, their derived error bound matches with the best-known bound for semidefinite programs under the same setting without outliers. Numerical experiments on a variety of simulated and real-world data sets further demonstrate that their algorithm is less sensitive to outliers compared with other state-of-the-art algorithms. We consider the problem of clustering data sets in the presence of arbitrary outliers. Traditional clustering algorithms such as k-means and spectral clustering are known to perform poorly for data sets contaminated with even a small number of outliers. In this paper, we develop a provably robust spectral clustering algorithm that applies a simple rounding scheme to denoise a Gaussian kernel matrix built from the data points and uses vanilla spectral clustering to recover the cluster labels of data points. We analyze the performance of our algorithm under the assumption that the "good" data points are generated from a mixture of sub-Gaussians (we term these "inliers"), whereas the outlier points can come from any arbitrary probability distribution. For this general class of models, we show that the misclassification error decays at an exponential rate in the signal-to-noise ratio, provided the number of outliers is a small fraction of the inlier points. Surprisingly, this derived error bound matches with the best-known bound for semidefinite programs (SDPs) under the same setting without outliers. We conduct extensive experiments on a variety of simulated and real-world data sets to demonstrate that our algorithm is less sensitive to outliers compared with other state-of-the-art algorithms proposed in the literature. Funding: G. A. Hanasusanto was supported by the National Science Foundation Grants NSF ECCS-1752125 and NSF CCF-2153606. P. Sarkar gratefully acknowledges support from the National Science Foundation Grants NSF DMS-1713082, NSF HDR-1934932 and NSF 2019844. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2317. [ABSTRACT FROM AUTHOR]

In this paper, an algorithm for maximizing a convex function over a convex feasible set is proposed. The algorithm, called CoMax, consists of two phases: in phase 1, a feasible starting point is obtained that is used in a gradient ascent algorithm in phase 2. The main contribution of the paper is connected to phase 1; five different methods are used to approximate the original NP-hard problem of maximizing a convex function (MCF) by a tractable convex optimization problem. All the methods use the minimizer of the convex objective function in their construction. In phase 2, the gradient ascent algorithm yields stationary points to the MCF problem. The performance of CoMax is tested on a wide variety of MCF problems, demonstrating its efficiency. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: This work was supported by the Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant 406.17.511]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplementary Information [https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1238] or is available from the IJOC GitHub software repository (https://github.com/INFORMSJoC) at [http://dx.doi.org/10.5281/zenodo.6884872]. [ABSTRACT FROM AUTHOR]

This paper considers the problem of minimizing a convex expectation function with a set of inequality convex expectation constraints. We propose a stochastic augmented Lagrangian-type algorithm—namely, the stochastic linearized proximal method of multipliers—to solve this convex stochastic optimization problem. This algorithm can be roughly viewed as a hybrid of stochastic approximation and the traditional proximal method of multipliers. Under mild conditions, we show that this algorithm exhibits O (K − 1 / 2) expected convergence rates for both objective reduction and constraint violation if parameters in the algorithm are properly chosen, where K denotes the number of iterations. Moreover, we show that, with high probability, the algorithm has a O (log (K) K − 1 / 2) constraint violation bound and O (log 3 / 2 (K) K − 1 / 2) objective bound. Numerical results demonstrate that the proposed algorithm is efficient. History: Accepted byAntonio Frangioni, Area Editor for Design & Analysis ofAlgorithms—Continuous. Funding: This work was supported by the National Natural Science Foundation of China [Grants 11971089, 11731013, 12071055, and 11871135]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplementary Information [https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1228] or is available from the IJOC GitHub software repository (https://github.com/INFORMSJoC) at http://dx.doi.org/10.5281/zenodo.6818229. [ABSTRACT FROM AUTHOR]

We explore the Projective Cutting-Planes algorithm proposed in Porumbel (2020) from new angles by applying it to two new problems, that is, to robust linear programming and to a cutting-stock problem with multiple lengths. Projective Cutting-Planes is a generalization of the widely used Cutting-Planes, and it aims at optimizing a linear function over a polytope P with prohibitively many constraints. The main new idea is to replace the well-known separation subproblem with the following projection subproblem: given an interior point x ∈ P and a direction d , find the maximum steplength t such that x + t d ∈ P. This enables one to generate a feasible solution at each iteration, a feature that does not exist built-in in a standard Cutting-Planes algorithm. The practical success of this new algorithm does not mainly come from the higher level ideas already presented in Porumbel (2020). Its success is significantly more dependent on the computation time needed to solve the projection subproblem in practice. Thus, the main challenge addressed by the current paper is the design of new techniques for solving this subproblem very efficiently for different polytopes P. We first address a well-known robust linear programming problem in which P is defined as a primal polytope. We then solve a multiple-length cutting stock problem in which P is a dual polytope defined in a column generation model. Numerical experiments on both these new problems confirm the potential of the proposed ideas. This enables us to draw conclusions supported by numerical results from both the current paper and Porumbel (2020) while also gaining more insight into the dynamics of the algorithm. Summary of Contribution: The well-known Cutting-Planes algorithm relies on the separation subproblem to cut off the current optimal solution. This paper belongs to a line of work whose goal is to "upgrade" the widely used separation subproblem to the following projection subproblem: given a feasible solution x inside some polytope P and a direction d, what is the maximum t value such that x + td ∈ P. In simple terms, one has to "shoot" from x along direction d up to the point where the boundary of the polytope is hit. The greatest challenge is to solve this projection subproblem rapidly enough to compete well in terms of computational speed with the separation subproblem algorithm. This paper shows how to achieve this on two new problems: robust linear programming and multiple length cutting stock. The numerical results confirm one important advantage offered by the projection logic: it enables one to generate a new feasible interior solution (i.e., x + td) at each iteration. The interior points thus generated actually guide the evolution of the overall algorithm, which is a feature that does not exist (built-in) in a traditional Cutting-Planes algorithm. [ABSTRACT FROM AUTHOR]

This paper develops a new algorithm for increasing the revenue in a dynamic product assortment problem. Then, it identifies the challenges faced by managers in practice and discusses the conditions under which workers follow the algorithm. To do so, I conducted a field experiment with a beverage vending machine business. The experiment shows that, on average, workers are reluctant to follow the algorithmic advice; however, the workers are more willing to conform once their forecasts are integrated into the algorithm. Analyses using nonexperimental variations highlight the importance of taking worker and context heterogeneity into account to maximize the benefit from adopting a new algorithm. Higher worker's regret, sales volatility, and fewer delegations increase the conformity, while they mitigate the effects of integration. Workers avoid high-traffic vending machines and focus on machines with high sales volatility when adopting the algorithm. The effects on the sales are largely similar to the effects on product assortments. The results emphasize the gap between nominal and actual performance of an algorithm and several practical issues to be resolved. This paper was accepted by Matthew Shum, marketing. [ABSTRACT FROM AUTHOR]

The article presents a zero-one linear program and a dynamic programming algorithm for finding the shortest route containing exactly q arcs from node 1 to node n in a network (N, A) with distances c(i, j). This note shows that the linear programming formulation and his extension based on it are defective, and that the dynamic programming algorithm can lead to suboptimal solutions, but a minor change in the dynamic programming formulation relieves the difficulty. A special feature of this linear program is that there can never be a loop in the basis, because the vectors corresponding to the variables of a loop are linearly dependent. The last comment is related to the dynamic programming algorithm. One is allowed to pass through a node more than once in the shortest route . The proposed method for solving this program consists of converting it into a shortest route problem containing exactly q arcs. But for some arbitrary reason, the dynamic program is formulated in such a way that one can never have starting node 1 more than once in the final solution.

This paper studies the two-echelon capacitated vehicle routing problem with time windows. The first echelon consists of transferring freight from depots to intermediate facilities (i.e., satellites), whereas the second echelon consists of transferring freight from these facilities to the final customers, within their time windows. We propose two path-based mathematical formulations for our problem: (1) in one formulation, paths are defined over both first- and second-echelon tours, and (2) in the other one, the first- and second-echelon paths are decomposed. Branch-and-price–based algorithms are developed for both formulations. We compare both formulations and solution methods on a comprehensive set of instances and are able to solve instances up to five satellites and 100 customers to optimality. This paper is the first paper in the literature that solves such large instance sizes. The online appendix is available at https://doi.org/10.1287/trsc.2018.0844. [ABSTRACT FROM AUTHOR]

This paper reviews the literature on vehicle routing problems and location routing problems with intermediate stops. We classify publications into different categories from both an application-based perspective and a methodological perspective. In addition, we analyze the papers with respect to the algorithms and benchmark instances they present. Furthermore, we provide an overview of trends in the literature and identify promising areas for further research. [ABSTRACT FROM AUTHOR]

We propose a new nonconvex regularization scheme to improve the performance of the stochastic dual dynamic programming (SDDP) algorithm for solving large-scale multistage stochastic programs. Specifically, we use a class of nonconvex regularization functions, namely folded concave penalty functions, to improve solution quality and the convergence rate of the SDDP procedure. We develop a strategy based on mixed-integer programming to guarantee global optimality of the nonconvex regularization problem. Moreover, we establish provable convergence guarantees for our customized SDDP algorithm. The benefits of our regularization scheme are demonstrated by solving large-scale instances of two multistage stochastic optimization problems. History: Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0255) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0255). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

The article "A Decomposition Algorithm with Fast Identification of Critical Contingencies for Large-Scale Security-Constrained AC-OPF" presents the decomposition algorithm used by Team GO-SNIP for the ARPA-E Grid Optimization (GO) Competition Challenge 1, held from November 2018 through October 2019. The algorithm involves unique contingency ranking and evaluation strategies for determining the important contingencies to include in a master problem that approximates the original large-scale security-constrained problem. It also involves efficient strategies for handling the complementarity constraints that appear in the model and for handling the arising degeneracies. Software implementation details are described, and the results of an extensive set of numerical experiments are provided to illustrate the effectiveness of each of the used techniques. Team GO-SNIP received a second-place finish in Challenge 1 of the Go Competition. A decomposition algorithm for solving large-scale security-constrained AC optimal power flow problems is presented. The formulation considered is the one used in the Advanced Research Projects Agency-Energy Grid Optimization Competition, Challenge 1, held from November 2018 through October 2019. Algorithmic strategies are proposed for contingency selection, fast contingency evaluation, handling complementarity constraints, avoiding issues related to degeneracy, and exploiting parallelism. The results of numerical experiments are provided to demonstrate the effectiveness of the proposed techniques as compared with alternative strategies. History: This paper has been accepted for the Operations Research Special Issue on Computational Advances in Short-Term Power System Operations. Funding: This work was supported by the Advanced Research Projects Agency-Energy [Grant DE-AR0001073]. [ABSTRACT FROM AUTHOR]

In an observational study there are two disjointed groups of samples, one of treatment samples and the other of control samples. Each of the samples is characterized by several observed covariates. Covariate balancing problems arise when estimating causal effects using observational data. It is desirable to replicate a randomized experiment by obtaining treatment and control groups with similar covariate distributions. Even though covariate balancing problems have been studied extensively, the complexity status of many variants has not been established. Some of our results demonstrate that 2-covariate balancing problems are polynomial time solvable, whereas almost all problems are hard for three or more covariates. These results have practical implications, such as justifying the use of implicit enumeration techniques or heuristics for the hard cases. A new approach suggested by our results is to use the 2-covariate polynomial cases and relax the problem by aggregating covariates into two sets to be solved efficiently. (accepted paper title: Algorithms and complexities of matching variants in covariate balancing) Here, we study several variants of matching problems that arise in covariate balancing. Covariate balancing problems can be viewed as variants of matching, or b-matching, with global side constraints. We present here a comprehensive complexity study of the covariate balancing problems providing polynomial time algorithms, or a proof of NP-hardness. The polynomial time algorithms described are mostly combinatorial and rely on network flow techniques. In addition, we present several fixed-parameter tractable results for problems where the number of covariates and the number of levels of each covariate are seen as a parameter. Funding: This work was supported by National Science Foundation [Grants CMMI-1760102 and NSF 2112533]; Israel Science Foundation (308/18). Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2022.2286. [ABSTRACT FROM AUTHOR]

Ensuring fairness in algorithmic decision making is a crucial policy issue. Current legislation ensures fairness by barring algorithm designers from using demographic information in their decision making. As a result, to be legally compliant, the algorithms need to ensure equal treatment. However, in many cases, ensuring equal treatment leads to disparate impact particularly when there are differences among groups based on demographic classes. In response, several "fair" machine learning (ML) algorithms that require impact parity (e.g., equal opportunity) at the cost of equal treatment have recently been proposed to adjust for the societal inequalities. Advocates of fair ML propose changing the law to allow the use of protected class-specific decision rules. We show that the proposed fair ML algorithms that require impact parity, while conceptually appealing, can make everyone worse off, including the very class they aim to protect. Compared with the current law, which requires treatment parity, the fair ML algorithms, which require impact parity, limit the benefits of a more accurate algorithm for a firm. As a result, profit maximizing firms could underinvest in learning, that is, improving the accuracy of their machine learning algorithms. We show that the investment in learning decreases when misclassification is costly, which is exactly the case when greater accuracy is otherwise desired. Our paper highlights the importance of considering strategic behavior of stake holders when developing and evaluating fair ML algorithms. Overall, our results indicate that fair ML algorithms that require impact parity, if turned into law, may not be able to deliver some of the anticipated benefits. This paper was accepted by Kartik Hosanagar, information systems. [ABSTRACT FROM AUTHOR]

In this paper, we use the penalty approach in order to study constrained minimization problems in infinite dimensional spaces. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper, we establish the exact penalty property for a large class of inequality-constrained minimization problems. [ABSTRACT FROM AUTHOR]

In designing ideal multiple recursive random number (RN) generators (MRGs), the best set of multipliers, in terms of the lattice structure of the RNs produced, is sought. As the order of the MRG increases, the number of possible sets of multipliers to be examined grows exponentially This paper proposes a genetic algorithm for designing good MRGs. The set of multipliers associated with the MRG is encoded as a binary string. Via the operations of reproduction, crossover, and mutation, new sets of multipliers are generated. The spectral values of the MRGs are calculated to guide the search process. As an illustration, the proposed algorithm is employed to find good sets of multipliers for MRGs of orders three and four. The results are better than those derived from other studies. To conclude, this paper not only finds better MRGs of orders three and four, but also develops an algorithm for designing MRGs of higher orders. [ABSTRACT FROM AUTHOR]

Fluence map optimization for intensity-modulated radiation therapy planning can be formulated as a large-scale inverse problem with competing objectives and constraints associated with the tumors and organs at risk. Unfortunately, clinically relevant dose–volume constraints are nonconvex, so standard algorithms for convex problems cannot be directly applied. Although prior work focuses on convex approximations for these constraints, we propose a novel relaxation approach to handle nonconvex dose–volume constraints. We develop efficient, provably convergent algorithms based on partial minimization, and show how to adapt them to handle maximum-dose constraints and infeasible problems. We demonstrate our approach using the CORT data set and show that it is easily adaptable to radiation treatment planning with dose–volume constraints for multiple tumors and organs at risk. Summary of Contribution: This paper proposes a novel approach to deal with dose–volume constraints in radiation treatment planning optimization, which is inherently nonconvex, mixed-integer programming. The authors tackle this NP-hard problem using auxiliary variables and continuous optimization while preserving the problem's nonconvexity. Algorithms to efficiently solve the nonconvex optimization problem presented in this paper yield computation speeds suitable for a busy clinical setting. [ABSTRACT FROM AUTHOR]

This study introduces a branch-and-bound algorithm to solve mixed-integer bilinear maximum multiplicative programs (MIBL-MMPs). This class of optimization problems arises in many applications, such as finding a Nash bargaining solution (Nash social welfare optimization), capacity allocation markets, reliability optimization, etc. The proposed algorithm applies multiobjective optimization principles to solve MIBL-MMPs exploiting a special characteristic in these problems. That is, taking each multiplicative term in the objective function as a dummy objective function, the projection of an optimal solution of MIBL-MMPs is a nondominated point in the space of dummy objectives. Moreover, several enhancements are applied and adjusted to tighten the bounds and improve the performance of the algorithm. The performance of the algorithm is investigated by 400 randomly generated sample instances of MIBL-MMPs. The obtained result is compared against the outputs of the mixed-integer second order cone programming (SOCP) solver in CPLEX and a state-of-the-art algorithm in the literature for this problem. Our analysis on this comparison shows that the proposed algorithm outperforms the fastest existing method, that is, the SOCP solver, by a factor of 6.54 on average. Summary of Contribution: The scope of this paper is defined over a class of mixed-integer programs, the so-called mixed-integer bilinear maximum multiplicative programs (MIBL-MMPs). The importance of MIBL-MMPs is highlighted by the fact that they are encountered in applications, such as Nash bargaining, capacity allocation markets, reliability optimization, etc. The mission of the paper is to introduce a novel and effective criterion space branch-and-cut algorithm to solve MIBL-MMPs by solving a finite number of single-objective mixed-integer linear programs. Starting with an initial set of primal and dual bounds, our proposed approach explores the efficient set of the multiobjective problem counterpart of the MIBL-MMP through a criterion space–based branch-and-cut paradigm and iteratively improves the bounds using a branch-and-bound scheme. The bounds are obtained using novel operations developed based on Chebyshev distance and piecewise McCormick envelopes. An extensive computational study demonstrates the efficacy of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Column generation (CG) algorithms are well known to suffer from convergence issues due, mainly, to the degenerate structure of their master problem and the instability associated with the dual variables involved in the process. In the literature, several strategies have been proposed to overcome this issue. These techniques rely either on the modification of the standard CG algorithm or on some prior information about the set of dual optimal solutions. In this paper, we propose a new stabilization framework, which relies on the dynamic generation of aggregated rows from the CG master problem. To evaluate the performance of our method and its flexibility, we consider instances of three different problems, namely, vehicle routing with time windows (VRPTW), bin packing with conflicts (BPPC), and multiperson pose estimation (MPPEP). When solving the VRPTW, the proposed stabilized CG method yields significant improvements in terms of CPU time and number of iterations with respect to a standard CG algorithm. Huge reductions in CPU time are also achieved when solving the BPPC and the MPPEP. For the latter, our method has shown to be competitive when compared with a tailored method. Summary of Contribution: Column generation (CG) algorithms are among the most important and studied solution methods in operations research. CG algorithms are suitable to cope with large-scale problems arising from several real-life applications. The present paper proposes a generic stabilization framework to address two of the main issues found in a CG method: degeneracy in the master problem and massive instability of the dual variables. The newly devised method, called dynamic separation of aggregated rows (dyn-SAR), relies on an extended master problem that contains redundant constraints obtained by aggregating constraints from the original master problem formulation. This new formulation is solved in a column/row generation fashion. The efficacy of the proposed method is tested through an extensive experimental campaign, where we solve three different problems that differ considerably in terms of their constraints and objective function. Despite being a generic framework, dyn-SAR requires the embedded CG algorithm to be tailored to the application at hand. [ABSTRACT FROM AUTHOR]

In many statistical learning problems, it is desired that the optimal solution conform to an a priori known sparsity structure represented by a directed acyclic graph. Inducing such structures by means of convex regularizers requires nonsmooth penalty functions that exploit group overlapping. Our study focuses on evaluating the proximal operator of the latent overlapping group lasso developed by Jacob et al. in 2009. We implemented an alternating direction method of multiplier with a sharing scheme to solve large-scale instances of the underlying optimization problem efficiently. In the absence of strong convexity, global linear convergence of the algorithm is established using the error bound theory. More specifically, the paper contributes to establishing primal and dual error bounds when the nonsmooth component in the objective function does not have a polyhedral epigraph. We also investigate the effect of the graph structure on the speed of convergence of the algorithm. Detailed numerical simulation studies over different graph structures supporting the proposed algorithm and two applications in learning are provided. Summary of Contribution: The paper proposes a computationally efficient optimization algorithm to evaluate the proximal operator of a nonsmooth hierarchical sparsity-inducing regularizer and establishes its convergence properties. The computationally intensive subproblem of the proposed algorithm can be fully parallelized, which allows solving large-scale instances of the underlying problem. Comprehensive numerical simulation studies benchmarking the proposed algorithm against five other methods on the speed of convergence to optimality are provided. Furthermore, performance of the algorithm is demonstrated on two statistical learning applications related to topic modeling and breast cancer classification. The code along with the simulation studies and benchmarks are available on the corresponding author's GitHub website for evaluation and future use. [ABSTRACT FROM AUTHOR]

In the era of big data, an important weapon in a machine learning researcher's arsenal is a scalable support vector machine (SVM) algorithm. Traditional algorithms for learning SVMs scale superlinearly with the training set size, which becomes infeasible quickly for large data sets. In recent years, scalable algorithms have been designed which study the primal or dual formulations of the problem. These often suggest a way to decompose the problem and facilitate development of distributed algorithms. In this paper, we present a distributed algorithm for learning linear SVMs in the primal form for binary classification called the gossip-based subgradient (GADGET) SVM. The algorithm is designed such that it can be executed locally on sites of a distributed system. Each site processes its local homogeneously partitioned data and learns a primal SVM model; it then gossips with random neighbors about the classifier learnt and uses this information to update the model. To learn the model, the SVM optimization problem is solved using several techniques, including a gradient estimation procedure, stochastic gradient descent method, and several variants including minibatches of varying sizes. Our theoretical results indicate that the rate at which the GADGET SVM algorithm converges to the global optimum at each site is dominated by an O (1 λ ) term, where λ measures the degree of convexity of the function at the site. Empirical results suggest that this anytime algorithm—where the quality of results improve gradually as computation time increases—has performance comparable to its centralized, pseudodistributed, and other state-of-the-art gossip-based SVM solvers. It is at least 1.5 times (often several orders of magnitude) faster than other gossip-based SVM solvers known in literature and has a message complexity of O(d) per iteration, where d represents the number of features of the data set. Finally, a large-scale case study is presented wherein the consensus-based SVM algorithm is used to predict failures of advanced mechanical components in a chocolate manufacturing process using more than one million data points. This paper was accepted by J. George Shanthikumar, big data analytics. [ABSTRACT FROM AUTHOR]

Stochastic programming involves large-scale optimization with exponentially many scenarios. This paper proposes an optimization-based scenario reduction approach to generate high-quality solutions and tight lower bounds by only solving small-scale instances, with a limited number of scenarios. First, we formulate a scenario subset selection model that optimizes the recourse approximation over a pool of solutions. We provide a theoretical justification of our formulation, and a tailored heuristic to solve it. Second, we propose a scenario assortment optimization approach to compute a lower bound—hence, an optimality gap—by relaxing nonanticipativity constraints across scenario "bundles." To solve it, we design a new column-evaluation-and-generation algorithm, which provides a generalizable method for optimization problems featuring many decision variables and hard-to-estimate objective parameters. We test our approach on stochastic programs with continuous and mixed-integer recourse. Results show that (i) our scenario reduction method dominates scenario reduction benchmarks, (ii) our scenario assortment optimization, combined with column-evaluation-and-generation, yields tight lower bounds, and (iii) our overall approach results in stronger solutions, tighter lower bounds, and faster computational times than state-of-the-art stochastic programming algorithms. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2023.1295. [ABSTRACT FROM AUTHOR]

This paper proposes an exact algorithm to solve the one-to-one multiobjective shortest path problem. The solution involves determining a set of nondominated paths between two given nodes in a graph that minimizes several objective functions. This study is motivated by the application of this solution method to determine cycling itineraries. The proposed algorithm improves upon a label-correcting algorithm to rapidly solve the problem on large graphs (i.e., up to millions of nodes and edges). To verify the performance of the proposed algorithm, we use computational experiments to compare it with the best-known methods in the literature. The numerical results confirm the efficiency of the proposed algorithm. Summary of Contribution: The paper deals with a classic operations research problem (the one-to-one multiobjective shortest path problem) and is motivated by a real application for cycling itineraries. An efficient method is proposed and is based on a label-correcting algorithm into which several additional improvement techniques are integrated. Computational experiments compare this algorithm with the best-known methods in the literature to validate the performance on large-size graphs (Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) instances from the ninth DIMACS challenge). New instances from the context of cycling itineraries are also proposed. [ABSTRACT FROM AUTHOR]

This paper studies the reliable uncapacitated facility location problem in which facilities are subject to uncertain disruptions. A two-stage distributionally robust model is formulated, which optimizes the facility location decisions so as to minimize the fixed facility location cost and the expected transportation cost of serving customers under the worst-case disruption distribution. The model is formulated in a general form, where the uncertain joint distribution of disruptions is partially characterized and is allowed to have any prespecified dependency structure. This model extends several related models in the literature, including the stochastic one with explicitly given disruption distribution and the robust one with moment information on disruptions. An efficient cutting plane algorithm is proposed to solve this model, where the separation problem is solved respectively by a polynomial-time algorithm in the stochastic case and by a column generation approach in the robust case. Extensive numerical study shows that the proposed cutting plane algorithm not only outperforms the best-known algorithm in the literature for the stochastic problem under independent disruptions but also efficiently solves the robust problem under correlated disruptions. The practical performance of the robust models is verified in a simulation based on historical typhoon data in China. The numerical results further indicate that the robust model with even a small amount of information on disruption correlation can mitigate the conservativeness and improve the location decision significantly. Summary of Contribution: In this paper, we study the reliable uncapacitated facility location problem under uncertain facility disruptions. The problem is formulated as a two-stage distributionally robust model, which generalizes several related models in the literature, including the stochastic one with explicitly given disruption distribution and the robust one with moment information on disruptions. To solve this generalized model, we propose a cutting plane algorithm, where the separation problem is solved respectively by a polynomial-time algorithm in the stochastic case and by a column generation approach in the robust case. The efficiency and effectiveness of the proposed algorithm are validated through extensive numerical experiments. We also conduct a data-driven simulation based on historical typhoon data in China to verify the practical performance of the proposed robust model. The numerical results further reveal insights into the value of information on disruption correlation in improving the robust location decisions. [ABSTRACT FROM AUTHOR]

This paper proposes a cluster-aware supervised learning (CluSL) framework, which integrates the clustering analysis with supervised learning. The objective of CluSL is to simultaneously find the best clusters of the data points and minimize the sum of loss functions within each cluster. This framework has many potential applications in healthcare, operations management, manufacturing, and so on. Because CluSL, in general, is nonconvex, we develop a regularized alternating minimization (RAM) algorithm to solve it, where at each iteration, we penalize the distance between the current clustering solution and the one from the previous iteration. By choosing a proper penalty function, we show that each iteration of the RAM algorithm can be computed efficiently. We further prove that the proposed RAM algorithm will always converge to a stationary point within a finite number of iterations. This is the first known convergence result in cluster-aware learning literature. Furthermore, we extend CluSL to the high-dimensional data sets, termed the F-CluSL framework. In F-CluSL, we cluster features and minimize loss function at the same time. Similarly, to solve F-CluSL, a variant of the RAM algorithm (i.e., F-RAM) is developed and proven to be convergent to an ∈ -stationary point. Our numerical studies demonstrate that the proposed CluSL and F-CluSL can outperform the existing ones such as random forests and support vector classification, both in the interpretability of learning results and in prediction accuracy. Summary of Contribution: Aligned with the mission and scope of the INFORMS Journal on Computing, this paper proposes a cluster-aware supervised learning (CluSL) framework, which integrates the clustering analysis with supervised learning. Because CluSL is, in general, nonconvex, a regularized alternating projection algorithm is developed to solve it and is proven to always find a stationary solution. We further generalize the framework to the high-dimensional data set, F-CluSL. Our numerical studies demonstrate that the proposed CluSL and F-CluSL can deliver more interpretable learning results and outperform the existing ones such as random forests and support vector classification in computational time and prediction accuracy. [ABSTRACT FROM AUTHOR]

Suppose a target is hidden in one of the vertices of an edge-weighted graph according to a known probability distribution. Starting from a fixed root node, an expanding search visits the vertices sequentially until it finds the target, where the next vertex can be reached from any of the previously visited vertices. That is, the time to reach the next vertex equals the shortest-path distance from the set of all previously visited vertices. The expanding search problem then asks for a sequence of the nodes, so as to minimize the expected time to finding the target. This problem has numerous applications, such as searching for hidden explosives, mining coal, and disaster relief. In this paper, we develop exact algorithms and heuristics, including a branch-and-cut procedure, a greedy algorithm with a constant-factor approximation guarantee, and a local search procedure based on a spanning-tree neighborhood. Computational experiments show that our branch-and-cut procedure outperforms existing methods for instances with nonuniform probability distributions and that both our heuristics compute near-optimal solutions with little computational effort. Summary of Contribution: This paper studies new algorithms for the expanding search problem, which asks to search a graph for a target hidden in one of the nodes according to a known probability distribution. This problem has applications such as searching for hidden explosives, mining coal, and disaster relief. We propose several new algorithms, including a branch-and-cut procedure, a greedy algorithm, and a local search procedure; and we analyze their performance both experimentally and theoretically. Our analysis shows that the algorithms improve on the performance of existing methods and establishes the first constant-factor approximation guarantee for this problem. [ABSTRACT FROM AUTHOR]

In this paper, we consider optimal stopping problems in their dual form. In this way, the optimal stopping problem can be reformulated as a problem of stochastic average approximation (SAA) that can be solved via linear programming. By randomizing the initial value of the underlying process, we enforce solutions with zero variance while preserving the linear programming structure of the problem. A careful analysis of the randomized SAA algorithm shows that it enjoys favorable properties such as faster convergence rates and reduced complexity compared with the nonrandomized procedure. We illustrate the performance of our algorithm on several benchmark examples. Funding: This work was supported by the Deutsche Forschungsgemeinschaft via the MATH+ Cluster of Excellence [Project AA4-2]. [ABSTRACT FROM AUTHOR]

Modern reinforcement learning (RL) is commonly applied to practical problems with an enormous number of states, where function approximation must be deployed to approximate either the value function or the policy. The introduction of function approximation raises a fundamental set of challenges involving computational and statistical efficiency, especially given the need to manage the exploration/exploitation trade-off. As a result, a core RL question remains open: how can we design provably efficient RL algorithms that incorporate function approximation? This question persists even in a basic setting with linear dynamics and linear rewards, for which only linear function approximation is needed. This paper presents the first provable RL algorithm with both polynomial run time and polynomial sample complexity in this linear setting, without requiring a "simulator" or additional assumptions. Concretely, we prove that an optimistic modification of least-squares value iteration—a classical algorithm frequently studied in the linear setting—achieves O ˜ ( d 3 H 3 T) regret, where d is the ambient dimension of feature space, H is the length of each episode, and T is the total number of steps. Importantly, such regret is independent of the number of states and actions. Funding: This work was supported by the Defense Advanced Research Projects Agency program on Lifelong Learning Machines. [ABSTRACT FROM AUTHOR]

Cold start describes a commonly recognized challenge for online advertising platforms: with limited data, the machine learning system cannot accurately estimate the click-through rates (CTR) of new ads and, in turn, cannot efficiently price these new ads or match them with platform users. Traditional cold start algorithms often focus on improving the learning rates of CTR for new ads to improve short-term revenue, but unsuccessful cold start can prompt advertisers to leave the platform, decreasing the thickness of the ad marketplace. To address these issues, we build a data-driven optimization model that captures the essential trade-off between short-term revenue and long-term market thickness on the platform. Based on duality theory and bandit algorithms, we develop the shadow bidding with learning (SBL) algorithms with a provable regret upper bound of O (T 2 / 3 K 1 / 3 (log T) 1 / 3 d 1 / 2) , where K is the number of ads and d captures the error magnitude of the underlying machine learning oracle for predicting CTR. Our proposed algorithms can be implemented in a real online advertising system with minimal adjustments. To demonstrate this practicality, we have collaborated with a large-scale video-sharing platform, conducting a novel, two-sided randomized field experiment to examine the effectiveness of our SBL algorithm. Our results show that the algorithm increased the cold start success rate by 61.62% while compromising short-term revenue by only 0.717%. Our algorithm has also boosted the platform's overall market thickness by 3.13% and its long-term advertising revenue by (at least) 5.35%. Our study bridges the gap between the theory of bandit algorithms and the practice of cold start in online advertising, highlighting the value of well-designed cold start algorithms for online advertising platforms. This paper was accepted by Gabriel Weintraub, revenue management and market analytics. Supplemental Material: Data and the online appendices are available at https://doi.org/10.1287/mnsc.2022.4550. [ABSTRACT FROM AUTHOR]

The problem of determining continuous flows of minimum cost in a network with convex cost functions is considered. The approach used is that of finding, for any given feasible flow, circuit flows of negative incremental costs. In the main theoretical result of this paper, it is proved that if at each stage, given a feasible nonoptimal flow X, the circuit flow with most negative incremental cost is added to X, linear convergence to the optimal solution will be obtained. In addition, this most negative incremental cost determines an upper bound on the difference in cost between the given feasible solution and the optimal. Based on these concepts, an algorithm, which preserves linear convergence, is presented to determine minimum cost flows in networks with convex costs in the arcs. Results of computer runs made for this algorithm are given. The special case of networks with linear costs is also considered. [ABSTRACT FROM AUTHOR]

This paper deals with undiscounted infinite stage two-person zero-sum stochastic games with finite state and action spaces. It was recently shown that such games possess a value. But in general there are no optimal strategies. We prove that for each player there exists a nonempty set of easy initial states, i.e. starting states for which the player possesses an optimal stationary strategy. This result is proved with the aid of facts derived by Bewley and Kohlberg for the limit discount equation for stochastic games. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to delineate an algorithm for fractional programming with nonlinear as well as linear terms in the numerator and denominator. The algorithm presented is based on a theorem by Jagannathan [7] concerning the relationship between fractional and parametric programming. This theorem is restated and proved in a somewhat simpler way. Finally, it is shown how the given algorithm can be related to the method of Isbell and Marlow [6] for linear fractional programming and to the quadratic parametric approach by Ritter [10]. The Appendix contains a numerical example. [ABSTRACT FROM AUTHOR]

Commentary is presented for an article published in the July 1960 issue of "Management Science," written by L. V. Kantorovich with an introductory note by T. C. Koopmans. According to the author, in his introduction Koopmans addresses in particular a linear programming problem and a matrix game presented by Kantorovich. Also presented is an interpretation of the article's treatment of decision variables and mathematical optimization. The author notes that the article presents algorithms that have been improved from their contemporary presentations.

The exact solution of the NP-hard (nondeterministic polynomial-time hard) maximum cut problem is important in many applications across, for example, physics, chemistry, neuroscience, and circuit layout—which is also due to its equivalence to the unconstrained binary quadratic optimization problem. Leading solution methods are based on linear or semidefinite programming and require the separation of the so-called odd-cycle inequalities. In their groundbreaking research, F. Barahona and A. R. Mahjoub have given an informal description of a polynomial-time algorithm for this problem. As pointed out recently, however, additional effort is necessary to guarantee that the inequalities obtained correspond to facets of the cut polytope. In this paper, we shed more light on a so enhanced separation procedure and investigate experimentally how it performs in comparison with an ideal setting where one could even employ the sparsest, most violated, or geometrically most promising facet-defining odd-cycle inequalities. Summary of Contribution: This paper aims at a better capability to solve binary quadratic optimization or maximum cut problems and their various applications using integer programming techniques. To this end, the paper describes enhancements to a well-known algorithm for the central separation problem arising in this context; it is demonstrated experimentally that these enhancements are worthwhile from a computational point of view. The linear relaxations of the aforementioned problems are typically solved using fewer iterations and cutting planes than with a nonenhanced approach. It is also shown that the enhanced procedure is only slightly inferior to an ideal, enumerative, and, in practice, intractable global cutting-plane selection. [ABSTRACT FROM AUTHOR]

Zero forcing is a graph coloring process based on the following color change rule: all vertices of a graph G are initially colored either blue or white; in each timestep, a white vertex turns blue if it is the only white neighbor of some blue vertex. A zero forcing set of G is a set of blue vertices such that all vertices eventually become blue after iteratively applying the color change rule. The zero forcing number Z (G) is the cardinality of a minimum zero forcing set. In this paper, we propose novel exact algorithms for computing Z (G) based on formulating the zero forcing problem as a two-stage Boolean satisfiability problem. We also propose several heuristics for zero forcing based on iteratively adding blue vertices which color a large part of the remaining white vertices. These heuristics are used to speed up the exact algorithms and can also be of independent interest in approximating Z (G) . Computational results on various types of graphs show that, in many cases, our algorithms offer a significant improvement on the state-of-the-art algorithms for zero forcing. Summary of Contribution: This paper proposes novel algorithms and heuristics for an NP-hard graph coloring problem that has numerous applications. Our exact methods combine Boolean satisfiability modeling with a constraint generation framework commonly used in operations research. The paper also includes an analysis of the facets of the polytope associated with this problem and decomposition techniques which can reduce the size of the problem. Our computational approaches are implemented and tested on a wide variety of graphs and are compared with the state-of-the-art algorithms from the literature. We show that our proposed algorithms based on Boolean satisfiability, in conjunction with the heuristics and order-reduction techniques, yield a significant speedup in some cases. [ABSTRACT FROM AUTHOR]

When generating multirow intersection cuts for mixed-integer linear optimization problems, an important practical question is deciding which intersection cuts to use. Even when restricted to cuts that are facet defining for the corner relaxation, the number of potential candidates is still very large, especially for instances of large size. In this paper, we introduce a subset of intersection cuts based on the infinity norm that is very small, works for relaxations having arbitrary number of rows and, unlike many subclasses studied in the literature, takes into account the entire data from the simplex tableau. We describe an algorithm for generating these inequalities and run extensive computational experiments in order to evaluate their practical effectiveness in real-world instances. We conclude that this subset of inequalities yields, in terms of gap closure, around 50% of the benefits of using all valid inequalities for the corner relaxation simultaneously, but at a small fraction of the computational cost, and with a very small number of cuts. Summary of Contribution: Cutting planes are one of the most important techniques used by modern mixed-integer linear programming solvers when solving a variety of challenging operations research problems. The paper advances the state of the art on general-purpose multirow intersection cuts by proposing a practical and computationally friendly method to generate them. [ABSTRACT FROM AUTHOR]

Summary of Contribution: Big data analytics has become essential for modern operations research and operations management applications. Statistics methods, such as nonparametric density and function estimation, play important roles in predictive and exploratory data analysis for economics and operations management problems. In this paper, we concentrate on efficiently computing local polynomial regression estimates. We significantly accelerate the computation of such local polynomial estimates by novel applications of multidimensional binary indexed trees (Fenwick 1994) and lazy memory allocation via hashing. Both time and space complexity of our proposed algorithm are nearly linear in the number of inputs. Simulation results confirm the efficiency and effectiveness of our proposed methods. Local polynomial regression is an important class of methods for nonparametric density estimation and regression problems. However, straightforward implementation of local polynomial regression has quadratic time complexity which hinders its applicability in large-scale data analysis. In this paper, we significantly accelerate the computation of local polynomial estimates by novel applications of multidimensional binary indexed trees. Both time and space complexity of our proposed algorithm is nearly linear in the number of input data points. Simulation results confirm the efficiency and effectiveness of our proposed approach. Summary of Contribution. Big data analytics has become essential for modern operations research and operations management applications. Statistics methods, such as nonparametric density and function estimation, play important roles in predictive and exploratory data analysis for economics and operations management problems. In this paper, we concentrate on efficiently computing local polynomial regression estimates. We significantly accelerate the computation of such local polynomial estimates by novel applications of multidimensional binary indexed trees and lazy memory allocation via hashing. Both time and space complexity of our proposed algorithm are nearly linear in the number of inputs. Simulation results confirm the efficiency and effectiveness of our proposed methods. [ABSTRACT FROM AUTHOR]