-
作者：Storm, Jaap; Berkelmans, Wouter; Bekker, Rene
作者单位：Eindhoven University of Technology; Vrije Universiteit Amsterdam
摘要：We consider a many-server queue in which each server can serve multiple customers in parallel. Such multitasking phenomena occur in various applications areas (e.g., in hospitals and contact centers), although the impact of the number of customers who are simultaneously served on system efficiency may vary. We establish diffusion limits of the queueing process under the quality-and-efficiency-driven scaling and for different policies of assigning customers to servers depending on the number of...
-
作者：Naegele, Martin; Santiago, Richard; Zenklusen, Rico
作者单位：University of Bonn
摘要：A long-standing open question in integer programming is whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable. An important special case thereof are congruency-constrained integer programs min{c(inverted perpendicular)x : Tx <= b, gamma(inverted perpendicular)x = r (mod m), x is an element of Z(n)} with a totally unimodular constraint matrix T. Such problems are shown to be polynomial-time solvable for m = 2, which led to an efficient algorithm...
-
作者：Aprile, Manuel; Conforti, Michele; Di Summa, Marco
作者单位：University of Padua
摘要：A binarization of a bounded variable x is obtained via a system of linear inequalities that involve x together with additional variables y(1), ... , y(t) in [0,1] so that the integrality of x is implied by the integrality of y(1), ... , y(t). A binary extended formulation of a mixedinteger linear set is obtained by adding to its original description binarizations of its integer variables. Binary extended formulations are useful in mixed-integer programming as imposing integrality on 0/1 variab...
-
作者：Haasler, Isabel; Ringh, Axel; Chen, Yongxin; Karlsson, Johan
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Chalmers University of Technology; University of Gothenburg; University System of Georgia; Georgia Institute of Technology; Royal Institute of Technology
摘要：In this work, we develop a new framework for dynamic network flow problems based on optimal transport theory. We show that the dynamic multicommodity minimum-cost network flow problem can be formulated as a multimarginal optimal transport problem, where the cost function and the constraints on the marginals are associated with a graph structure. By exploiting these structures and building on recent advances in optimal transport theory, we develop an efficient method for such entropyregularized...
-
作者：Tang, Tianyun; Toh, Kim-Chuan
作者单位：National University of Singapore; National University of Singapore
摘要：In this paper, we consider a semidefinite programming (SDP) relaxation of the quadratic knapsack problem. After applying low-rank factorization, we get a nonconvex problem, whose feasible region is an algebraic variety with certain good geometric properties, which we analyze. We derive a rank condition under which these two formulations are equivalent. This rank condition is much weaker than the classical rank condition if the coefficient matrix has certain special structures. We also prove th...
-
作者：Gnoatto, Alessandro; Lavagnini, Silvia; Picarelli, Athena
作者单位：University of Verona; BI Norwegian Business School
摘要：We propose a novel computational procedure for quadratic hedging in highdimensional incomplete markets, covering mean-variance hedging and local risk minimization. Starting from the observation that both quadratic approaches can be treated from the point of view of backward stochastic differential equations (BSDEs), we (recursively) apply a deep learning-based BSDE solver to compute the entire optimal hedging strategies paths. This allows us to overcome the curse of dimensionality, extending t...
-
作者：Celaya, Marcel; Kuhlmann, Stefan; Paat, Joseph; Weismantel, Robert
作者单位：Cardiff University; Technical University of Berlin; University of British Columbia
摘要：This paper deals with linear integer optimization. We develop a technique that can be applied to provide improved upper bounds for two important questions in linear integer optimization. Given an optimal vertex solution for the linear relaxation, how far away is the nearest optimal integer solution (if one exists; proximity bounds)? If a polyhedron contains no integer point, what is the smallest number of integer parallel hyperplanes defined by an integral, nonzero, normal vector that intersec...
-
作者：Chen, Xujin; Ding, Guoli; Zang, Wenan; Zhao, Qiulan
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Louisiana State University System; Louisiana State University; University of Hong Kong; Nanjing University
摘要：Let T = (V,A) be a tournament with a nonnegative integral weight w(e) on each arc e. A subset F of arcs is called a feedback arc set (FAS) if T\F contains no cycles (directed). A collection F of FASs (with repetition allowed) is called an FAS packing if each arc e is used at most w(e) times by the members of F. The purpose of this paper is to give a characterization of all tournaments T = (V,A) with the property that, for every nonnegative integral weight function w defined on A, the minimum t...
-
作者：Blauth, Jannis; Neuwohner, Meike; Puhlmann, Luise; Vygen, Jens
作者单位：University of Bonn; University of London; London School Economics & Political Science
摘要：We revisit the A PRIORI TSP (with independent activation) and prove stronger approximation guarantees than were previously known. In the A PRIORI TSP, we are given a metric space (V, c ) and an activation probability p ( v ) for each customer v is an element of V . We ask for a TSP tour T for V that minimizes the expected length after cutting T short by skipping the inactive customers. All known approximation algorithms select a nonempty subset S of the customers and construct a master route s...
-
作者：Bolte, Jerome; Combettes, Cyrille W.; Pauwelsb, Edouard
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Institut Universitaire de France
摘要：The Frank-Wolfe algorithm is a popular method for minimizing a smooth convex function f over a compact convex set C. Whereas many convergence results have been derived in terms of function values, almost nothing is known about the convergence behavior of the sequence of iterates (xt)t is an element of N. Under the usual assumptions, we design several counterexamples to the convergence of (xt)t is an element of N, where f is d-time continuously differentiable, dP 2, and f(xt) -> minC f. Our cou...
