Search

Consider a two-person zero-sum search game between a hider and a searcher. The hider hides among $n$ discrete locations, and the searcher successively visits individual locations until finding the hider. Known to both players, a search at location $i$ takes $t_i$ time units and detects the hider -- if hidden there -- independently with probability $q_i$, for $i=1,\ldots,n$. The hider aims to maximize the expected time until detection, while the searcher aims to minimize it. We prove the existence of an optimal strategy for each player. In particular, the hider's optimal mixed strategy hides in each location with a nonzero probability, and the searcher's optimal mixed strategy can be constructed with up to $n$ simple search sequences. We develop an algorithm to compute an optimal strategy for each player, and compare the optimal hiding strategy with the simple hiding strategy which gives the searcher no location preference at the beginning of the search., Comment: 55 pages, 2 figures

This paper presents a general mean-field game (GMFG) framework for simultaneous learning and decision-making in stochastic games with a large population. It first establishes the existence of a unique Nash Equilibrium to this GMFG, and demonstrates that naively combining reinforcement learning with the fixed-point approach in classical MFGs yields unstable algorithms. It then proposes value-based and policy-based reinforcement learning algorithms (GMF-V and GMF-P, respectively) with smoothed policies, with analysis of their convergence properties and computational complexities. Experiments on an equilibrium product pricing problem demonstrate that GMF-V-Q and GMF-P-TRPO, two specific instantiations of GMF-V and GMF-P, respectively, with Q-learning and TRPO, are both efficient and robust in the GMFG setting. Moreover, their performance is superior in convergence speed, accuracy, and stability when compared with existing algorithms for multi-agent reinforcement learning in the $N$-player setting., Published in Mathematics of Operations Research

The problem of community detection with two equal-sized communities is closely related to the minimum graph bisection problem over certain random graph models. In the stochastic block model distribution over networks with community structure, a well-known semidefinite programming (SDP) relaxation of the minimum bisection problem recovers the underlying communities whenever possible. Motivated by their superior scalability, we study the theoretical performance of linear programming (LP) relaxations of the minimum bisection problem for the same random models. We show that unlike the SDP relaxation that undergoes a phase transition in the logarithmic average-degree regime, the LP relaxation exhibits a transition from recovery to non-recovery in the linear average-degree regime. We show that in the logarithmic average-degree regime, the LP relaxation fails in recovering the planted bisection with high probability., 32 pages, 3 figures; includes revisions for print version

Distributionally robust chance-constrained programs (DR-CCPs) over Wasserstein ambiguity sets exhibit attractive out-of-sample performance and admit big-M–based mixed-integer programming reformulations with conic constraints. However, the resulting formulations often suffer from scalability issues as problem size increases. To address this shortcoming, we derive stronger formulations that scale well with respect to the problem size. Our focus is on ambiguity sets under the so-called left-hand side uncertainty, where the uncertain parameters affect the coefficients of the decision variables in the linear inequalities defining the safety sets. The interaction between the uncertain parameters and the variable coefficients in the safety set definition causes challenges in strengthening the original big-M formulations. By exploiting the connection between nominal chance-constrained programs and DR-CCP, we obtain strong formulations with significant enhancements. In particular, through this connection, we derive a linear number of valid inequalities, which can be immediately added to the formulations to obtain improved formulations in the original space of variables. In addition, we suggest a quantile-based strengthening procedure that allows us to reduce the big-M coefficients drastically. Furthermore, based on this procedure, we propose an exponential class of inequalities that can be separated efficiently within a branch-and-cut framework. The quantile-based strengthening procedure can be expensive. Therefore, for the special case of covering and packing type problems, we identify an efficient scheme to carry out this procedure. We demonstrate the computational efficacy of our proposed formulations on two classes of problems, namely stochastic portfolio optimization and resource planning. Funding: This work was supported by the DARPA Lagrange Program [Grant N660011824020], the National Science Foundation [Grant 1740707], the Office of Naval Research [Grant N00014-19-1-2321], and the Institute for Basic Science [Grants IBS-R029-C1 and IBS-R029-Y2].

We consider Assemble-to-Order (ATO) inventory systems with a general Bill of Materials and general deterministic lead times. Unsatisfied demands are always backlogged. We apply a four-step asymptotic framework to develop inventory policies for minimizing the long-run average expected total inventory cost. Our approach features a multi-stage Stochastic Program (SP) to establish a lower bound on the inventory cost and determine parameter values for inventory control. Our replenishment policy deviates from the conventional constant base stock policies to accommodate non-identical lead times. Our component allocation policy differentiates demands based on backlog costs, Bill of Materials, and component availabilities. We prove that our policy is asymptotically optimal on the diffusion scale, that is, as the longest lead time grows, the percentage difference between the average cost under our policy and its lower bound converges to zero. In developing these results, we formulate a broad Stochastic Tracking Model and prove general convergence results from which the asymptotic optimality of our policy follows as specialized corollaries., Comment: 63 pages

Neighborhood search is a cornerstone of state-of-the-art traveling salesman and vehicle routing metaheuristics. Whereas neighborhood exploration procedures are well-developed for problems with individual services, their counterparts for one-to-one pickup-and-delivery problems are more scarcely studied. A direct extension of classic neighborhoods is often inefficient or complex because of the necessity of jointly considering service pairs. To circumvent these issues, we introduce major improvements to existing neighborhood searches for the pickup-and-delivery traveling salesman problem and new large neighborhoods. We show that the classic Relocate Pair neighborhood can be fully explored in [Formula: see text] instead of [Formula: see text] time. We adapt the 4-Opt and Balas–Simonetti neighborhoods to consider precedence constraints. Moreover, we introduce an exponential-size neighborhood called 2k-Opt, which includes all solutions generated by multiple nested 2-Opts and can be searched in [Formula: see text] time using dynamic programming. We conduct extensive computational experiments, highlighting the significant contribution of these new neighborhoods and speedup strategies within two classical metaheuristics. Notably, our approach permits us to repeatedly solve small pickup-and-delivery problem instances to optimality or near-optimality within milliseconds, and therefore, it represents a valuable tool for time-critical applications, such as meal delivery or mobility on demand. Funding: This work was supported by Coordenação de Aperfeiçoamento de Pessoal de Nível Superior, Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 308528/2018-2, 315361/2020-4, 422470/2021-0], and Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro [Grants E-26/202.790/2019, E-26/201.417/2022, E-26/010.002232/2019]. Supplemental Material: The electronic companion is available at https://doi.org/10.1287/trsc.2022.1176 .

Markov decision processes (MDPs) are used to model stochastic systems in many applications. Several efficient algorithms to compute optimal policies have been studied in the literature, including value iteration (VI) and policy iteration. However, these do not scale well especially when the discount factor for the infinite horizon discounted reward, $\lambda$, gets close to $1$. In particular, the running time scales as $O \left( 1/(1-\lambda) \right)$ for these algorithms. In this paper, our goal is to design new algorithms that scale better than previous approaches when $\lambda$ approaches $1$. Our main contribution is to present a connection between VI and gradient descent and adapt the ideas of acceleration and momentum in convex optimization to design faster algorithms for MDPs. We prove theoretical guarantees of a faster convergence of our algorithms for the computation of the value function of a policy, where the running times of our algorithms scale as $O \left( 1/\sqrt{1-\lambda} \right)$ for reversible MDP instances. The improvement is quite analogous to Nesterov's acceleration and momentum in convex optimization. We also provide a lower bound on the convergence properties of any first-order algorithm for solving MDPs, presenting a family of MDPs instances for which no algorithm can converge faster than VI when the number of iterations is smaller than the number of states. We introduce a Safe Accelerated Value Iteration (S-AVI), which alternates between accelerated updates and value iteration updates. Our algorithm S-AVI is worst-case optimal and retains the theoretical convergence properties of VI while exhibiting strong empirical performances, providing significant speedups compared to classical approaches (up to one order of magnitude in many cases) for a large test bed of MDP instances.

We study a new variant of the well-studied vehicle routing problem with time windows (VRPTW), called the fragility-constrained VRPTW, which assumes that (1) the capacity of a vehicle is organized in multiple identical stacks; (2) all items picked up at a customer are either “fragile” or not; (3) no nonfragile items can be put on top of a fragile item (the fragility constraint); and (4) no en route load rearrangement is possible. We first characterize the feasibility of a route with respect to this fragility constraint. Then, to solve this new problem, we develop an exact branch-price-and-cut (BPC) algorithm that includes a labeling algorithm exploiting this feasibility characterization to efficiently generate feasible routes. This algorithm is benchmarked against another BPC algorithm that deals with the fragility constraint in the column generation master problem through infeasible path cuts. Our computational results show that the former BPC algorithm clearly outperforms the latter in terms of computational time and that the fragility constraint has a greater impact on the optimal solution cost (compared with that of the VRPTW) when vehicle capacity decreases, stack height increases, and for a more balanced mix of customers with fragile and nonfragile items. Funding: This work was supported by the Natural Sciences and Engineering Research Council of Canada [Grants RGPIN 2015-06289 and RGPIN 2022-03916]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2022.1168 .

Facet-defining inequalities of the symmetric traveling salesman problem (TSP) polytope play a prominent role in both polyhedral TSP research and state-of-the-art TSP solvers. In this paper, we introduce a new class of facet-defining inequalities, the circlet inequalities. These inequalities were first conjectured in Gutekunst and Williamson [Gutekunst SC, Williamson DP (2019) Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem. SIAM J. Discrete Math. 33(4):2452–2478] when studying the circulant TSP, and they provide a bridge between polyhedral TSP research and number-theoretic investigations of Hamiltonian cycles stemming from a conjecture from Marco Buratti in 2007. The circlet inequalities exhibit circulant symmetry by placing the same weight on all edges of a given length; our main proof exploits this symmetry to prove the validity of the circlet inequalities. We then show that the circlet inequalities are facet-defining and compute their strength following Goemans [Goemans MX (1995) Worst-case comparison of valid inequalities for the TSP. Math. Programming 69:335–349]; they achieve the same worst case strength as the similarly circulant crown inequalities of Naddef and Rinaldi [Naddef D, Rinaldi G (1992) The crown inequalities for the symmetric traveling salesman polytope. Math. Oper. Res. 17(2):308–326] but are generally stronger. Funding: This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program [Grant DGE-1650441] and by the National Science Foundation Division of Computing and Communications Foundations [Grant CCF-1908517].

We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games with simultaneous moves. To incorporate function approximation, we consider a family of Markov games where the reward function and transition kernel possess a linear structure. Both the offline and online settings of the problems are considered. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret. For both settings, we propose an optimistic variant of the least-squares minimax value iteration algorithm. We show that our algorithm is computationally efficient and provably achieves an $\tilde O(\sqrt{d^3 H^3 T} )$ upper bound on the duality gap and regret, where $d$ is the linear dimension, $H$ the horizon and $T$ the total number of timesteps. Our results do not require additional assumptions on the sampling model. Our setting requires overcoming several new challenges that are absent in Markov decision processes or turn-based Markov games. In particular, to achieve optimism with simultaneous moves, we construct both upper and lower confidence bounds of the value function, and then compute the optimistic policy by solving a general-sum matrix game with these bounds as the payoff matrices. As finding the Nash Equilibrium of a general-sum game is computationally hard, our algorithm instead solves for a Coarse Correlated Equilibrium (CCE), which can be obtained efficiently. To our best knowledge, such a CCE-based scheme for optimism has not appeared in the literature and might be of interest in its own right., Accepted for presentation at COLT 2020

We propose two distributionally robust optimization (DRO) models for a mobile facility (MF) fleet-sizing, routing, and scheduling problem (MFRSP) with time-dependent and random demand as well as methodologies for solving these models. Specifically, given a set of MFs, a planning horizon, and a service region, our models aim to find the number of MFs to use (i.e., fleet size) within the planning horizon and a route and time schedule for each MF in the fleet. The objective is to minimize the fixed cost of establishing the MF fleet plus a risk measure (expectation or mean conditional value at risk) of the operational cost over all demand distributions defined by an ambiguity set. In the first model, we use an ambiguity set based on the demand’s mean, support, and mean absolute deviation. In the second model, we use an ambiguity set that incorporates all distributions within a 1-Wasserstein distance from a reference distribution. To solve the proposed DRO models, we propose a decomposition-based algorithm. In addition, we derive valid lower bound inequalities that efficiently strengthen the master problem in the decomposition algorithm, thus improving convergence. We also derive two families of symmetry-breaking constraints that improve the solvability of the proposed models. Finally, we present extensive computational experiments comparing the operational and computational performance of the proposed models and a stochastic programming model, demonstrating when significant performance improvements could be gained, and derive insights into the MFRSP. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.1153 .

We study a seemingly unexpected and relatively less understood overfitting aspect of a fundamental tool in sparse linear modeling - best subset selection, which minimizes the residual sum of squares subject to a constraint on the number of nonzero coefficients. While the best subset selection procedure is often perceived as the "gold standard" in sparse learning when the signal to noise ratio (SNR) is high, its predictive performance deteriorates when the SNR is low. In particular, it is outperformed by continuous shrinkage methods, such as ridge regression and the Lasso. We investigate the behavior of best subset selection in the high-noise regimes and propose an alternative approach based on a regularized version of the least-squares criterion. Our proposed estimators (a) mitigate, to a large extent, the poor predictive performance of best subset selection in the high-noise regimes; and (b) perform favorably, while generally delivering substantially sparser models, relative to the best predictive models available via ridge regression and the Lasso. We conduct an extensive theoretical analysis of the predictive properties of the proposed approach and provide justification for its superior predictive performance relative to best subset selection when the noise-level is high. Our estimators can be expressed as solutions to mixed integer second order conic optimization problems and, hence, are amenable to modern computational tools from mathematical optimization.

We consider minimizing $f(x) = \mathbb{E}[f(x,\omega)]$ when $f(x,\omega)$ is possibly nonsmooth and either strongly convex or convex in $x$. (I) Strongly convex. When $f(x,\omega)$ is $\mu-$strongly convex in $x$, we propose a variable sample-size accelerated proximal scheme (VS-APM) and apply it on $f_{\eta}(x)$, the ($\eta$-)Moreau smoothed variant of $\mathbb{E}[f(x,\omega)]$; we term such a scheme as (m-VS-APM). We consider three settings. (a) Bounded domains. In this setting, VS-APM displays linear convergence in inexact gradient steps, each of which requires utilizing an inner (SSG) scheme. Specifically, mVS-APM achieves an optimal oracle complexity in SSG steps; (b) Unbounded domains. In this regime, under a weaker assumption of suitable state-dependent bounds on subgradients, an unaccelerated variant mVS-PM is linearly convergent; (c) Smooth ill-conditioned $f$. When $f$ is $L$-smooth and $\kappa = L/\mu \ggg 1$, we employ mVS-APM where increasingly accurate gradients $\nabla_x f_{\eta}(x)$ are obtained by VS-APM. Notably, mVS-APM displays linear convergence and near-optimal complexity in inner proximal evaluations (upto a log factor) compared to VS-APM. But, unlike a direct application of VS-APM, this scheme is characterized by larger steplengths and better empirical behavior; (II) Convex. When $f(x,\omega)$ is merely convex but smoothable, by suitable choices of the smoothing, steplength, and batch-size sequences, smoothed VS-APM (or sVS-APM) produces sequences for which expected sub-optimality diminishes at the rate of $\mathcal{O}(1/k)$ with an optimal oracle complexity of $\mathcal{O}(1/\epsilon^2)$. Finally, sVS-APM and VS-APM produce sequences that converge almost surely to a solution of the original problem., Comment: Stochastic Systems (2022)

Entropy regularization has been extensively adopted to improve the efficiency, the stability, and the convergence of algorithms in reinforcement learning. This paper analyzes both quantitatively and qualitatively the impact of entropy regularization for mean field games (MFGs) with learning in a finite time horizon. Our study provides a theoretical justification that entropy regularization yields time-dependent policies and, furthermore, helps stabilizing and accelerating convergence to the game equilibrium. In addition, this study leads to a policy-gradient algorithm with exploration in MFG. With this algorithm, agents are able to learn the optimal exploration scheduling, with stable and fast convergence to the game equilibrium.

The goal of a sequential decision making problem is to design an interactive policy that adaptively selects a group of items, each selection is based on the feedback from the past, in order to maximize the expected utility of selected items. It has been shown that the utility functions of many real-world applications are adaptive submodular. However, most of existing studies on adaptive submodular optimization focus on the average-case. Unfortunately, a policy that has a good average-case performance may have very poor performance under the worst-case realization. In this study, we propose to study two variants of adaptive submodular optimization problems, namely, worst-case adaptive submodular maximization and robust submodular maximization. The first problem aims to find a policy that maximizes the worst-case utility and the latter one aims to find a policy, if any, that achieves both near optimal average-case utility and worst-case utility simultaneously. We introduce a new class of stochastic functions, called \emph{worst-case submodular function}. For the worst-case adaptive submodular maximization problem subject to a $p$-system constraint, we develop an adaptive worst-case greedy policy that achieves a $\frac{1}{p+1}$ approximation ratio against the optimal worst-case utility if the utility function is worst-case submodular. For the robust adaptive submodular maximization problem subject to cardinality constraints (resp. partition matroid constraints), if the utility function is both worst-case submodular and adaptive submodular, we develop a hybrid adaptive policy that achieves an approximation close to $1-e^{-\frac{1}{2}}$ (resp. $1/3$) under both worst- and average-case settings simultaneously. We also describe several applications of our theoretical results, including pool-base active learning, stochastic submodular set cover and adaptive viral marketing., This paper has been accepted to INFORMS Journal on Computing

Route choice models in public transport have been discussed for a long time. The main factor why a passenger chooses a specific path is usually based on its length or travel time. However, also the ticket price that passengers have to pay may influence their decision since passengers prefer cheaper paths over more expensive ones. In this paper, we deal with the cheapest ticket problem which asks for a cheapest ticket to travel between a pair of stations. The complexity and the algorithmic approach to solve this problem depend crucially on the underlying fare structure, e.g., it is easy if the ticket prices are proportional to the distance traveled (as in distance tariff fare structures), but may become NP-complete in zone tariff fare structures. We hence discuss the cheapest ticket problem for different variations of distance- and zone-based fare structures. We start by modeling the respective fare structure mathematically, identify its main properties, and finally provide a polynomial algorithm, or prove NP-completeness of the cheapest ticket problem. We also provide general results on the combination of two fare structures, which is often observed in practice., Comment: 35 pages, revised version

The motion-and-time analysis has been a popular research topic in operations research, especially for analyzing work performances in manufacturing and service operations. It is regaining attention as continuous improvement tools for lean manufacturing and smart factory. This paper develops a framework for data-driven analysis of work motions and studies their correlations to work speeds or execution rates, using data collected from modern motion sensors. The past analyses largely relied on manual steps involving time-consuming stop-watching and video-taping, followed by manual data analysis. While modern sensing devices have automated the collection of motion data, the motion analytics that transform the new data into knowledge are largely underdeveloped. Unsolved technical questions include: How the motion and time information can be extracted from the motion sensor data, how work motions and execution rates are statistically modeled and compared, and what are the statistical correlations of motions to the rates? In this paper, we develop a novel mathematical framework for motion and time analysis with motion sensor data, by defining new mathematical representation spaces of human motions and execution rates and by developing statistical tools on these new spaces. This methodological research is demonstrated using five use cases applied to manufacturing motion data., Keywords: motion and time study, motion sensors, Riemannian manifold, probability distribution on manifold, temporal evolution of probability distributions

This paper revisits the parametric analysis of semidefinite optimization problems with respect to the perturbation of the objective function along a fixed direction. We review the notions of invariancy set, nonlinearity interval, and transition point of the optimal partition, and we investigate their characterizations. We show that the set of transition points is finite and the continuity of the optimal set mapping, on the basis of Painlevé–Kuratowski set convergence, might fail on a nonlinearity interval. Under a local nonsingularity condition, we then develop a methodology, stemming from numerical algebraic geometry, to efficiently compute nonlinearity intervals and transition points of the optimal partition. Finally, we support the theoretical results by applying our procedure to some numerical examples.

Bayesian optimization is a powerful tool for expensive stochastic black-box optimization problems such as simulation-based optimization or machine learning hyperparameter tuning. Many stochastic objective functions implicitly require a random number seed as input. By explicitly reusing a seed a user can exploit common random numbers, comparing two or more inputs under the same randomly generated scenario, such as a common customer stream in a job shop problem, or the same random partition of training data into training and validation set for a machine learning algorithm. With the aim of finding an input with the best average performance over infinitely many seeds, we propose a novel Gaussian process model that jointly models both the output for each seed and the average. We then introduce the Knowledge gradient for Common Random Numbers that iteratively determines a combination of input and random seed to evaluate the objective and automatically trades off reusing old seeds and querying new seeds, thus overcoming the need to evaluate inputs in batches or measuring differences of pairs as suggested in previous methods. We investigate the Knowledge Gradient for Common Random Numbers both theoretically and empirically, finding it achieves significant performance improvements with only moderate added computational cost., Comment: 21 pages + Appendix, under review

We propose a simple projection and rescaling algorithm that finds maximum support solutions to the pair of feasibility problems \[ \text{find} \; x\in L\cap\mathbb{R}^n_{+} \;\;\;\; \text{ and } \; \;\;\;\; \text{find} \; \hat x\in L^\perp\cap\mathbb{R}^n_{+}, \] where $L$ is a linear subspace of $\mathbb{R}^n$ and $L^\perp$ is its orthogonal complement. The algorithm complements a basic procedure that involves only projections onto $L$ and $L^\perp$ with a periodic rescaling step. The number of rescaling steps and thus overall computational work performed by the algorithm are bounded above in terms of a condition measure of the above pair of problems. Our algorithm is a natural but significant extension of a previous projection and rescaling algorithm that finds a solution to the problem \[ \text{find} \; x\in L\cap\mathbb{R}^n_{++} \] when this problem is feasible. As a byproduct of our new developments, we obtain a sharper analysis of the projection and rescaling algorithm in the latter special case., 18 pages

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 [Formula: see text] 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 [Formula: see text] constraint violation bound and [Formula: see text] 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 .

In many contemporary optimization problems such as those arising in machine learning, it can be computationally challenging or even infeasible to evaluate an entire function or its derivatives. This motivates the use of stochastic algorithms that sample problem data, which can jeopardize the guarantees obtained through classical globalization techniques in optimization such as a trust region or a line search. Using subsampled function values is particularly challenging for the latter strategy, which relies upon multiple evaluations. On top of that all, there has been an increasing interest for nonconvex formulations of data-related problems, such as training deep learning models. For such instances, one aims at developing methods that converge to second-order stationary points quickly, i.e., escape saddle points efficiently. This is particularly delicate to ensure when one only accesses subsampled approximations of the objective and its derivatives. In this paper, we describe a stochastic algorithm based on negative curvature and Newton-type directions that are computed for a subsampling model of the objective. A line-search technique is used to enforce suitable decrease for this model, and for a sufficiently large sample, a similar amount of reduction holds for the true objective. By using probabilistic reasoning, we can then obtain worst-case complexity guarantees for our framework, leading us to discuss appropriate notions of stationarity in a subsampling context. Our analysis encompasses the deterministic regime, and allows us to identify sampling requirements for second-order line-search paradigms. As we illustrate through real data experiments, these worst-case estimates need not be satisfied for our method to be competitive with first-order strategies in practice.

We present FrankWolfe.jl, an open-source implementation of several popular Frank–Wolfe and conditional gradients variants for first-order constrained optimization. The package is designed with flexibility and high performance in mind, allowing for easy extension and relying on few assumptions regarding the user-provided functions. It supports Julia’s unique multiple dispatch feature, and it interfaces smoothly with generic linear optimization formulations using MathOptInterface.jl.

Mixed-integer second-order cone programs (MISOCPs) form a novel class of mixed-integer convex programs, which can be solved very efficiently as a result of the recent advances in optimization solvers. This paper shows how various performance metrics of M/G/1 queues can be modeled by different MISOCPs. To motivate the reformulation method, it is first applied to a challenging stochastic location problem with congestion, which is broadly used to design socially optimal service systems. Three different MISOCPs are developed and compared on different sets of benchmark test problems. The new formulations efficiently solve very large-size test problems that cannot be solved by the two existing methods developed based on linear programming within reasonable time. The superiority of the conic reformulation method is next shown over a state-space decomposition method recently used to solve an assignment problem in queueing systems. Finally, the general applicability of the method is shown for similar optimization problems that use queue-theoretic performance measures to address customer satisfaction and service quality.

This work addresses inverse linear optimization where the goal is to infer the unknown cost vector of a linear program. Specifically, we consider the data-driven setting in which the available data are noisy observations of optimal solutions that correspond to different instances of the linear program. We introduce a new formulation of the problem that, compared to other existing methods, allows the recovery of a less restrictive and generally more appropriate admissible set of cost estimates. It can be shown that this inverse optimization problem yields a finite number of solutions, and we develop an exact two-phase algorithm to determine all such solutions. Moreover, we propose an efficient decomposition algorithm to solve large instances of the problem. The algorithm extends naturally to an online learning environment where it can be used to provide quick updates of the cost estimate as new data becomes available over time. For the online setting, we further develop an effective adaptive sampling strategy that guides the selection of the next samples. The efficacy of the proposed methods is demonstrated in computational experiments involving two applications, customer preference learning and cost estimation for production planning. The results show significant reductions in computation and sampling efforts., Comment: To be published in INFORMS Journal on Computing

Network design, a cornerstone of mathematical optimization, is about defining the main characteristics of a network satisfying requirements on connectivity, capacity, and level-of-service. It finds applications in logistics and transportation, telecommunications, data sharing, energy distribution, and distributed computing. In multi-commodity network design, one is required to design a network minimizing the installation cost of its arcs and the operational cost to serve a set of point-to-point connections. The definition of this prototypical problem was recently enriched by additional constraints imposing that each origin-destination of a connection is served by a single path satisfying one or more level-of-service requirements, thus defining the Network Design with Service Requirements [Balakrishnan, Li, and Mirchandani. Operations Research, 2017]. These constraints are crucial, e.g., in telecommunications and computer networks, in order to ensure reliable and low-latency communication. In this paper we provide a new formulation for the problem, where variables are associated with paths satisfying the end-to-end service requirements. We present a fast algorithm for enumerating all the exponentially-many feasible paths and, when this is not viable, we provide a column generation scheme that is embedded into a branch-and-cut-and-price algorithm. Extensive computational experiments on a large set of instances show that our approach is able to move a step further in the solution of the Network Design with Service Requirements, compared with the current state-of-the-art.

We consider a distributed server system consisting of a large number of servers, each with limited capacity on multiple resources (CPU, memory, disk, etc.). Jobs with different rewards arrive over time and require certain amounts of resources for the duration of their service. When a job arrives, the system must decide whether to admit it or reject it, and if admitted, in which server to schedule the job. The objective is to maximize the expected total reward received by the system. This problem is motivated by control of cloud computing clusters, in which, jobs are requests for Virtual Machines or Containers that reserve resources for various services, and rewards represent service priority of requests or price paid per time unit of service by clients. We study this problem in an asymptotic regime where the number of servers and jobs' arrival rates scale by a factor L, as L becomes large. We propose a resource reservation policy that asymptotically achieves at least 1/2, and under certain monotone property on jobs' rewards and resources, at least 11/4 of the optimal expected reward. The policy automatically scales the number of VM slots for each job type as the demand changes, and decides in which servers the slots should be created in advance, without the knowledge of traffic rates. It effectively tracks a low-complexity greedy packing of existing jobs in the system while maintaining only a small number, g(L) = w(logL), of reserved VM slots for high priority jobs that pack well.

This paper proposes a new formulation for the school bus scheduling problem (SBSP), which optimizes school start times and bus operation times to minimize transportation cost. The goal is to minimize the number of buses to serve all bus routes such that each route arrives in a time window before school starts. We show that introducing context-specific features, common in many school districts, can lead to a new time-indexed integer linear programming (ILP) formulation. Based on a strengthened version of the linear relaxation of the ILP, we develop a dependent randomized rounding algorithm that yields near-optimal solutions for large-scale problem instances. The efficient formulation and solution approach enable quick generation of multiple solutions to facilitate strategic planning, which we demonstrate with data from two public school districts in the United States. We also generalize our methodologies to solve a robust version of the SBSP.

Stochastic optimization (SO) is a classical approach for optimization under uncertainty that typically requires knowledge about the probability distribution of uncertain parameters. Because the latter is often unknown, distributionally robust optimization (DRO) provides a strong alternative that determines the best guaranteed solution over a set of distributions (ambiguity set). In this work, we present an approach for DRO over time that uses online learning and scenario observations arriving as a data stream to learn more about the uncertainty. Our robust solutions adapt over time and reduce the cost of protection with shrinking ambiguity. For various kinds of ambiguity sets, the robust solutions converge to the SO solution. Our algorithm achieves the optimization and learning goals without solving the DRO problem exactly at any step. We also provide a regret bound for the quality of the online strategy that converges at a rate of [Formula: see text], where T is the number of iterations. Furthermore, we illustrate the effectiveness of our procedure by numerical experiments on mixed-integer optimization instances from popular benchmark libraries and give practical examples stemming from telecommunications and routing. Our algorithm is able to solve the DRO over time problem significantly faster than standard reformulations. Funding: This work was supported by Deutsche Forschungsgemeinschaft (DFG): Projects B06 and B10 in CRC TRR 154 and Project-ID 416229255 - SFB 1411 and Federal Ministry for Economic Affairs and Energy, Germany [Grant 03EI1036A]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoo.2023.0091 .

We study a semismooth Newton-type method for the nearest doubly stochastic matrix problem where the nonsingularity of the Jacobian can fail. The optimality conditions for this problem are formulated as a system of strongly semismooth functions. We show that the nonsingularity of the Jacobian does not hold for this system. By exploiting the problem structure, we construct a modified two step semismooth Newton method that guarantees a nonsingular Jacobian matrix at each iteration, and that converges to the nearest doubly stochastic matrix quadratically. Funding: This work was supported by Canadian Network for Research and Innovation in Machining Technology. The research of H. Hu, H. Im, and H. Wolkowocz was supported by The Natural Sciences and Engineering Research Council of Canada. The research of X. Li was supported by the National Natural Science Foundation of China [No. 11601183] and Natural Science Foundation for Young Scientist of Jilin Province [No. 20180520212JH].

The use of machine learning techniques to improve the performance of branch-and-bound optimization algorithms is a very active area in the context of mixed integer linear problems, but little has been done for nonlinear optimization. To bridge this gap, we develop a learning framework for spatial branching and show its efficacy in the context of the Reformulation-Linearization Technique for polynomial optimization problems. The proposed learning is performed offline, based on instance-specific features and with no computational overhead when solving new instances. Novel graph-based features are introduced, which turn out to play an important role for the learning. Experiments on different benchmark instances from the literature show that the learning-based branching rule significantly outperforms the standard rules. History: Accepted by Andrea Lodi, Area Editor/Design & Analysis of Algorithms – Discrete. Funding: This work was supported by Ivey Business School (David G. Burgoyne Faculty Fellowship); FEDER [MTM2014-60191-JIN]; Spanish Ministry of Education [FPU Grant 17/02643, FPU Grant 20/01555]; Conselleria de Cultura, Educacion e Universidade [ED431C 2021/24]; Natural Sciences and Engineering Research Council of Canada [Discovery Grant 2017-04185]; Spanish Ministry of Science and Technology [MTM2017-87197-C3] and Spanish Ministry of Science and Innovation [PID2021-124030NB-C32].

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/ .

Peak/off-peak spreads on European electricity forward and spot markets are eroding due to the ongoing nuclear phaseout in Germany and the steady growth in photovoltaic capacity. The reduced profitability of peak/off-peak arbitrage forces hydropower producers to recover part of their original profitability on the reserve markets. We propose a bi-layer stochastic programming framework for the optimal operation of a fleet of interconnected hydropower plants that sells energy on both the spot and the reserve markets. The outer layer (the planner's problem) optimizes end-of-day reservoir filling levels over one year, whereas the inner layer (the trader's problem) selects optimal hourly market bids within each day. Using an information restriction whereby the planner prescribes the end-of-day reservoir targets one day in advance, we prove that the trader's problem simplifies from an infinite-dimensional stochastic program with 25 stages to a finite two-stage stochastic program with only two scenarios. Substituting this reformulation back into the outer layer and approximating the reservoir targets by affine decision rules allows us to simplify the planner's problem from an infinite-dimensional stochastic program with 365 stages to a two-stage stochastic program that can conveniently be solved via the sample average approximation. Numerical experiments based on a cascade in the Salzburg region of Austria demonstrate the effectiveness of the suggested framework.

We consider a class of integer linear programs (IPs) that arise as discretizations of trust-region subproblems of a trust-region algorithm for the solution of control problems, where the control input is an integer-valued function on a one-dimensional domain and is regularized with a total variation term in the objective, which may be interpreted as a penalization of switching costs between different control modes. We prove that solving an instance of the considered problem class is equivalent to solving a resource constrained shortest path problem (RCSPP) on a layered directed acyclic graph. This structural finding yields an algorithmic solution approach based on topological sorting and corresponding run time complexities that are quadratic in the number of discretization intervals of the underlying control problem, the main quantifier for the size of a problem instance. We also consider the solution of the RCSPP with an $A^*$ algorithm. Specifically, the analysis of a Lagrangian relaxation yields a consistent heuristic function for the $A^*$ algorithm and a preprocessing procedure, which can be employed to accelerate the $A^*$ algorithm for the RCSPP without losing optimality of the computed solution. We generate IP instances by executing the trust-region algorithm on several integer optimal control problems. The numerical results show that the accelerated $A^*$ algorithm and topological sorting outperform a general purpose IP solver significantly. Moreover, the accelerated $A^*$ algorithm is able to outperform topological sorting for larger problem instances., Comment: 25 pages, 6 figures

The rise of battery-powered vehicles has led to many new technical and methodological hurdles. Among these, the efficient planning of an electric fleet to fulfill passenger transportation requests still represents a major challenge. This is because of the specific constraints of electric vehicles, bound by their battery autonomy and necessity of recharge planning, and the large scale of the operations, which challenges existing optimization algorithms. The purpose of this paper is to introduce a scalable column generation approach for routing and scheduling in this context. Our algorithm relies on four main ingredients: (i) a multigraph reformulation of the problem based on a characterization of nondominated charging arcs, (ii) an efficient bidirectional pricing algorithm using tight backward bounds, (iii) sparsification approaches permitting to decrease the size of the subjacent graphs dramatically, and (iv) a diving heuristic, which locates near-optimal solutions in a fraction of the time needed for a complete branch-and-price. Through extensive computational experiments, we demonstrate that our approach significantly outperforms previous algorithms for this setting, leading to accurate solutions for problems counting several hundreds of requests. Funding: This work was supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 08528/2018-2 and 315361/2020-4], Coordenação de Aperfeiçoamento de Pessoal de Nível Superior [Finance Code 001], and Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro [Grants E-26/010.002232/2019 and E-26/202.790/2019]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.1199 .

Demand forecasting plays an important role in many inventory control problems. To mitigate the potential harms of model misspecification in this context, various forms of distributionally robust optimization have been applied. Although many of these methodologies suffer from the problem of time inconsistency, the work of Klabjan et al. established a general time-consistent framework for such problems by connecting to the literature on robust Markov decision processes. Motivated by the fact that many forecasting models exhibit very special structure as well as a desire to understand the impact of positing different dependency structures in distributionally robust multistage optimization, we formulate and solve a time-consistent distributionally robust multistage newsvendor model, which naturally robustifies some of the simplest inventory models with demand forecasting. In particular, in some of the simplest such models, demand evolves as a martingale (i.e., expected demand tomorrow equals realized demand today). We consider a robust variant of such models in which the sequence of future demands may be any martingale with given mean and support. Under such a model, past realizations of demand are naturally incorporated into the structure of the uncertainty set going forward. We explicitly compute the minimax optimal policy (and worst-case distribution) in closed form by combining ideas from convex analysis, probability, and dynamic programming. We prove that, at optimality, the worst-case demand distribution corresponds to the setting in which inventory may become obsolete at a random time. To gain further insight, we prove weak convergence (as the time horizon grows large) to a simple and intuitive process. We also compare with the analogous setting in which demand is independent across periods (analyzed previously by Shapiro) and identify several differences between these models in the spirit of the price of correlations studied by Agrawal et al. Finally, we complement our results by providing both numerical experiments that illustrate the potential benefits and limitations of our approach as well as additional theoretical analyses exploring what happens when our modeling assumptions do not hold.

The doubly nonnegative (DNN) cone, being the set of all positive semidefinite matrices whose elements are nonnegative, is a popular approximation of the computationally intractable completely positive cone. The major difficulty for implementing a Newton-type method to compute the projection of a given large scale matrix onto the DNN cone lies in the possible failure of the constraint nondegeneracy, a generalization of the linear independence constraint qualification for nonlinear programming. Such a failure results in the singularity of the Jacobian of the nonsmooth equation representing the Karush-Kuhn-Tucker optimality condition that prevents the semismooth Newton-CG method from solving it with a desirable convergence rate. In this paper, we overcome the aforementioned difficulty by solving a sequence of better conditioned nonsmooth equations generated by the augmented Lagrangian method (ALM) instead of solving one above mentioned singular equation. By leveraging on the metric subregularity of the normal cone associated with the positive semidefinite cone, we derive sufficient conditions to ensure the dual quadratic growth condition of the underlying problem, which further leads to the asymptotically superlinear convergence of the proposed ALM. Numerical results on difficult randomly generated instances and from the semidefinite programming library are presented to demonstrate the efficiency of the algorithm for computing the DNN projection to a very high accuracy., Comment: 28 pages, 0 figure

We study statistical estimators computed using iterative optimization methods that are not run until completion. Classical results on maximum likelihood estimators (MLEs) assert that a one-step estimator (OSE), in which a single Newton-Raphson iteration is performed from a starting point with certain properties, is asymptotically equivalent to the MLE. We further develop these early-stopping results by deriving properties of one-step estimators defined by a single iteration of scaled proximal methods. Our main results show the asymptotic equivalence of the likelihood-based estimator and various one-step estimators defined by scaled proximal methods. By interpreting OSEs as the last of a sequence of iterates, our results provide insight on scaling numerical tolerance with sample size. Our setting contains scaled proximal gradient descent applied to certain composite models as a special case, making our results applicable to many problems of practical interest. Additionally, our results provide support for the utility of the scaled Moreau envelope as a statistical smoother by interpreting scaled proximal descent as a quasi-Newton method applied to the scaled Moreau envelope.

In this paper, we consider a broad class of nonsmooth and nonconvex fractional programs, where the numerator can be written as the sum of a continuously differentiable convex function whose gradient is Lipschitz continuous and a proper lower semicontinuous (possibly nonconvex) function, and the denominator is weakly convex over the constraint set. This model problem includes the composite optimization problems studied extensively lately, and encompasses many important modern fractional optimization problems arising from diverse areas such as the recently proposed scale invariant sparse signal reconstruction problem in signal processing. We propose a proximal subgradient algorithm with extrapolations for solving this optimization model and show that the iterated sequence generated by the algorithm is bounded and any of its limit points is a stationary point of the model problem. The choice of our extrapolation parameter is flexible and includes the popular extrapolation parameter adopted in the restarted Fast Iterative Shrinking-Threshold Algorithm (FISTA). By providing a unified analysis framework of descent methods, we establish the convergence of the full sequence under the assumption that a suitable merit function satisfies the Kurdyka--{\L}ojasiewicz (KL) property. In particular, our algorithm exhibits linear convergence for the scale invariant sparse signal reconstruction problem and the Rayleigh quotient problem over spherical constraint. In the case where the denominator is the maximum of finitely many continuously differentiable weakly convex functions, we also propose an enhanced extrapolated proximal subgradient algorithm with guaranteed convergence to a stronger notion of stationary points of the model problem. Finally, we illustrate the proposed methods by both analytical and simulated numerical examples., Comment: Revised version: Oct. 16, 2020

We study parameterized versions of classical algorithms for computing shortest-path trees. This is most easily expressed in terms of tropical geometry. Applications include shortest paths in traffic networks with variable link travel times., 24 pages and 8 figures

Modern electric power systems have witnessed rapidly increasing penetration of renewable energy, storage, electrical vehicles, and various demand response resources. The electric infrastructure planning is thus facing more challenges as a result of the variability and uncertainties arising from the diverse new resources. This study aims to develop a multistage and multiscale stochastic mixed integer programming (MM-SMIP) model to capture both the coarse-temporal-scale uncertainties, such as investment cost and long-run demand stochasticity, and fine-temporal-scale uncertainties, such as hourly renewable energy output and electricity demand uncertainties, for the power system capacity expansion problem. To be applied to a real power system, the resulting model will lead to extremely large-scale mixed integer programming problems, which suffer not only the well-known curse of dimensionality but also computational difficulties with a vast number of integer variables at each stage. In addressing such challenges associated with the MM-SMIP model, we propose a nested cross decomposition algorithm that consists of two layers of decomposition—that is, the Dantzig–Wolfe decomposition and L-shaped decomposition. The algorithm exhibits promising computational performance under our numerical study and is especially amenable to parallel computing, which will also be demonstrated through the computational results.

Platooning of vehicles is a promising approach for reducing fuel consumption, increasing vehicle safety, and using road space more efficiently. We consider the important but difficult problem of assigning optimal routes and departure schedules to a collection of vehicles. We propose an iterative route-then-schedule heuristic for centralized planning that quickly converges to high-quality solutions. We also propose and analyze a collection of valid inequalities for the individual problems of assigning vehicles to routes and scheduling the times that vehicles traverse their routes. These inequalities are shown to reduce the computational time or optimality gap of solving the routing and scheduling problem instances. Our approach uses the valid inequalities in both the routing and scheduling portions of each iteration; numerical experiments highlight the speed of the approach for routing vehicles on a real-world road network., 61 pages, 7 figures

We consider a variant of the berth allocation problem-i.e., the multi-port berth allocation problem-aimed at assigning berthing times and positions to vessels in container terminals. This variant involves optimizing vessel travel speeds between multiple ports, thereby exploiting the potentials of a collaboration between carriers (shipping lines) and terminal operators. Using a graph representation of the problem, we reformulate an existing mixed-integer problem into a generalized set partitioning problem, in which each variable refers to a sequence of feasible berths in the ports that the vessel visits. By integrating column generation and cut separation in a branch-and-cut-and-price procedure, our proposed method is able to outperform commercial solvers in a set of benchmark instances and adapt better to larger instances. In addition, we apply cooperative game theory methods to efficiently distribute the savings resulting from a potential collaboration and show that both carriers and terminal operators would benefit from collaborating., Comment: 42 pages, 9 figures

Intensity-modulated radiation therapy (IMRT) allows for the design of customized, highly-conformal treatments for cancer patients. Creating IMRT treatment plans, however, is a mathematically complex process, which is often tackled in multiple, simpler stages. This sequential approach typically separates radiation dose requirements from mechanical deliverability considerations, which may result in suboptimal treatment quality. For patient health to be considered paramount, holistic models must address these plan elements concurrently, eliminating quality loss between stages. This combined direct aperture optimization (DAO) approach is rarely paired with uncertainty mitigation techniques, such as robust optimization, due to the inherent complexity of both parts. This paper outlines a robust DAO (RDAO) model and discusses novel methodologies for efficiently integrating salient constraints. Because the highly-complex RDAO model is difficult to solve, an original candidate plan generation (CPG) heuristic is proposed. The CPG produces rapid, high-quality, feasible plans, which are immediately clinically viable, and can also be used to generate a feasible incumbent solution for warm starting the RDAO model. Computational results obtained using clinical patient datasets with motion uncertainty show the benefit of incorporating the CPG, both in terms of first incumbent solution and final output plan quality., 27 pages, 14 figures

In the last decade, decision diagrams (DDs) have been the basis for a large array of novel approaches for modeling and solving optimization problems. Many techniques now use DDs as a key tool to achieve state-of-the-art performance within other optimization paradigms, such as integer programming and constraint programming. This paper provides a survey of the use of DDs in discrete optimization, particularly focusing on recent developments. We classify these works into two groups based on the type of diagram (i.e., exact or approximate) and present a thorough description of their use. We discuss the main advantages of DDs, point out major challenges, and provide directions for future work.

We present StochasticPrograms.jl, a user-friendly and powerful open-source framework for stochastic programming written in the Julia language. The framework includes both modeling tools and structure-exploiting optimization algorithms. Stochastic programming models can be efficiently formulated using an expressive syntax, and models can be instantiated, inspected, and analyzed interactively. The framework scales seamlessly to distributed environments. Small instances of a model can be run locally to ensure correctness, whereas larger instances are automatically distributed in a memory-efficient way onto supercomputers or clouds and solved using parallel optimization algorithms. These structure-exploiting solvers are based on variations of the classical L-shaped, progressive-hedging, and quasi-gradient algorithms. We provide a concise mathematical background for the various tools and constructs available in the framework along with code listings exemplifying their usage. Both software innovations related to the implementation of the framework and algorithmic innovations related to the structured solvers are highlighted. We conclude by demonstrating strong scaling properties of the distributed algorithms on numerical benchmarks in a multinode setup. Summary of Contribution: This paper presents StochasticPrograms.jl, an open-source framework for stochastic programming implemented in the Julia programming language. The framework includes an expressive syntax for formulating stochastic programming models as well as versatile analysis tools and parallel optimization algorithms. The framework will prove useful to researchers, educators, and industrial users alike. Researchers will benefit from the readily extensible open-source framework, in which they can formulate complex stochastic models or quickly typeset and test novel optimization algorithms. Educators of stochastic programming will benefit from the clean and expressive syntax. Moreover, the framework supports analysis tools and stochastic programming constructs from classical theory and leading textbooks. We strongly believe that the StochasticPrograms.jl framework can reduce the barrier to entry for incoming practitioners of stochastic programming. Industrial practitioners can make use of StochasticPrograms.jl to rapidly formulate complex models, analyze small instances locally, and then run large-scale instances in production. In doing so, they get distributed capabilities for free without changing the code and access to well-tested state-of-the-art implementations of parallel structure-exploiting solvers. As the framework is open-source, anyone from these target audiences can contribute with new functionality to the framework. In conclusion, by providing both an intuitive interface for new users and an extensive development environment for expert users, StochasticPrograms.jl has strong potential to further the field of stochastic programming.

This paper studies a setting in which multiple suppliers compete for a buyer's procurement business. The buyer faces uncertain demand and there is a requirement to reserve capacity in advance of knowing the demand. Each supplier has costs that are two dimensional, with some costs incurred before demand is realized in order to reserve capacity and some costs incurred after demand is realized at the time of delivery. A distinctive feature of our model is that the marginal costs may not be constants, and this naturally leads us to a supply function competition framework in which each supplier offers a schedule of prices and quantities. We treat this problem as an example of a general class of capacity games and show that, when the optimal supply chain profit is submodular, in equilibrium the buyer makes a reservation choice that maximizes the overall supply chain profit, each supplier makes a profit equal to their marginal contribution to the supply chain, and the buyer takes the remaining profit. We further prove that this submodularity property holds under two commonly studied settings: (1) there are only two suppliers; and (2) in the case of more than two suppliers, the marginal two-dimension costs of each supplier are non-decreasing and constant, respectively., Comment: 35 pages

The paper studies approximations and control of a processor sharing (PS) server where the service rate depends on the number of jobs occupying the server. The control of such a system is implemented by imposing a limit on the number of jobs that can share the server concurrently, with the rest of the jobs waiting in a first-in-first-out (FIFO) buffer. A desirable control scheme should strike the right balance between efficiency (operating at a high service rate) and parallelism (preventing small jobs from getting stuck behind large ones). We employ the framework of heavy-traffic diffusion analysis to devise near optimal control heuristics for such a queueing system. However, while the literature on diffusion control of state-dependent queueing systems begins with a sequence of systems and an exogenously defined drift function, we begin with a finite discrete PS server and propose an axiomatic recipe to explicitly construct a sequence of state-dependent PS servers which then yields a drift function. We establish diffusion approximations and use them to obtain insightful and closed-form approximations for the original system under a static concurrency limit control policy. We extend our study to control policies that dynamically adjust the concurrency limit. We provide two novel numerical algorithms to solve the associated diffusion control problem. Our algorithms can be viewed as "average cost" iteration: The first algorithm uses binary-search on the average cost and can find an $\epsilon$-optimal policy in time $O\left( \log^2 \frac{1}{\epsilon} \right)$; the second algorithm uses the Newton-Raphson method for root-finding and requires $O\left( \log \frac{1}{\epsilon} \log\log \frac{1}{\epsilon}\right)$ time. Numerical experiments demonstrate the accuracy of our approximation for choosing optimal or near-optimal static and dynamic concurrency control heuristics.

Aggregation of heating, ventilation, and air conditioning (HVAC) loads can provide reserves to absorb volatile renewable energy, especially solar photo-voltaic (PV) generation. In this paper, we decide HVAC control schedules under uncertain PV generation, using a distributionally robust chance-constrained (DRCC) building load control model under two typical ambiguity sets: the moment-based and Wasserstein ambiguity sets. We derive mixed integer linear programming (MILP) reformulations for DRCC problems under both sets. Especially, for the Wasserstein ambiguity set, we use the right-hand side (RHS) uncertainty to derive a more compact MILP reformulation than the commonly known MILP reformulations with big-M constants. All the results also apply to general individual chance constraints with RHS uncertainty. Furthermore, we propose an adjustable chance-constrained variant to achieve tradeoff between the operational risk and costs. We derive MILP reformulations under the Wasserstein ambiguity set and second-order conic programming (SOCP) reformulations under the moment-based set. Using real-world data, we conduct computational studies to demonstrate the efficiency of the solution approaches and the effectiveness of the solutions. Summary of Contribution: The problem studied in this paper is motivated by a building load control problem that uses the aggregation of heating, ventilation, and air conditioning (HVAC) loads as flexible reserves to absorb uncertain solar photovoltaic (PV) generation. The problem is formulated as distributionally robust chance-constrained (DRCC) programs with right-hand side (RHS) uncertainty. In addition, we propose a risk-adjustable variant of the DRCC programs, where the risk level, instead of being predetermined, is treated as a decision variable. The paper aims to provide tractable reformulations and solution algorithms for both the (general) DRCC and the (general) adjustable DRCC models with RHS uncertainty.

We propose subsampling as a unified algorithmic technique for submodular maximization in centralized and online settings. The idea is simple: independently sample elements from the ground set, and use simple combinatorial techniques (such as greedy or local search) on these sampled elements. We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. In the usual offline setting, we present SampleGreedy, which obtains a $(p + 2 + o(1))$-approximation for maximizing a submodular function subject to a $p$-extendible system using $O(n + nk/p)$ evaluation and feasibility queries, where $k$ is the size of the largest feasible set. The approximation ratio improves to $p+1$ and $p$ for monotone submodular and linear objectives, respectively. In the streaming setting, we present SampleStreaming, which obtains a $(4p +2 - o(1))$-approximation for maximizing a submodular function subject to a $p$-matchoid using $O(k)$ memory and $O(km/p)$ evaluation and feasibility queries per element, where $m$ is the number of matroids defining the $p$-matchoid. The approximation ratio improves to $4p$ for monotone submodular objectives. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks., Comment: arXiv admin note: text overlap with arXiv:1802.07098