-
作者：Bansal, Manish; Kianfar, Kiavash
作者单位：Texas A&M University System; Texas A&M University College Station
摘要：In this paper, we introduce a generalization of the continuous mixing set, which we refer to as the continuous multi-mixing set. This set is closely related to the feasible set of the multi-module capacitated lot-sizing (MML) problem with(out) backlogging. We present a family of valid inequalities for the continuous multi-mixing set and identify conditions under which they are facet-defining. The cycle inequalities, -step MIR inequalities, and mixed -step MIR inequalities are special cases of ...
-
作者：Bergner, Martin; Caprara, Alberto; Ceselli, Alberto; Furini, Fabio; Luebbecke, Marco E.; Malaguti, Enrico; Traversi, Emiliano
作者单位：RWTH Aachen University; University of Milan; Universite PSL; Universite Paris-Dauphine; University of Bologna; Universite Paris 13
摘要：Dantzig-Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the method is not implemented in any state-of-the-art MIP solver as it is considered to require structural problem knowledge and tailoring to this structure. We provide a computational proof-of-concept that the reformulation can be automated. That is, we perform a rigorous experimental study, which results in identifying a score to estimate...
-
作者：Bock, Adrian; Chandrasekaran, Karthekeyan; Koenemann, Jochen; Peis, Britta; Sanita, Laura
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Illinois System; University of Illinois Urbana-Champaign; University of Waterloo; RWTH Aachen University
摘要：An undirected graph is stable if the cardinality of a maximum matching equals the size of a minimum fractional vertex cover. We call a set of edges a stabilizer if its removal from yields a stable graph. In this paper we study the following natural edge-deletion question: given a graph , can we find a minimum-cardinality stabilizer? Stable graphs play an important role in cooperative game theory. In the classic matching game introduced by Shapley and Shubik (Int J Game Theory 1(1):111-130, 197...
-
作者：Conforti, Michele; Del Pia, Alberto; Di Summa, Marco; Faenza, Yuri
作者单位：University of Padua; University of Wisconsin System; University of Wisconsin Madison; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：The reverse split rank of an integral polyhedron is defined as the supremum of the split ranks of all rational polyhedra whose integer hull is . Already in there exist polyhedra with infinite reverse split rank. We give a geometric characterization of the integral polyhedra in with infinite reverse split rank.
-
作者：Arulselvan, Ashwin
作者单位：Technical University of Berlin
摘要：Padberg (Math Program 137:593-599, 2013) introduced a geometric notion of ranks for (mixed) integer rational polyhedrons and conjectured that the geometric rank of the matching polytope is one. In this work, we prove that this conjecture is true.
-
作者：Hanasusanto, Grani A.; Kuhn, Daniel; Wallace, Stein W.; Zymler, Steve
作者单位：Imperial College London; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Norwegian School of Economics (NHH)
摘要：We present a risk-averse multi-dimensional newsvendor model for a class of products whose demands are strongly correlated and subject to fashion trends that are not fully understood at the time when orders are placed. The demand distribution is known to be multimodal in the sense that there are spatially separated clusters of probability mass but otherwise lacks a complete description. We assume that the newsvendor hedges against distributional ambiguity by minimizing the worst-case risk of th...
-
作者：Correa, Jose; Marchetti-Spaccamela, Alberto; Matuschke, Jannik; Stougie, Leen; Svensson, Ola; Verdugo, Victor; Verschae, Jose
作者单位：Universidad de Chile; Sapienza University Rome; Technical University of Berlin; Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI); Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
摘要：A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different machines while incurring an arbitrary setup time. In this paper we present increasingly stronger LP-relaxations for this problem and their implications on the approximability of the problem. First we show that the straightforward LP, extending the approach for the original problem, has an integrality gap of 3 and yields an approximation algorithm of the same fa...
-
作者：Marchetti-Spaccamela, Alberto; Rutten, Cyriel; van der Ster, Suzanne; Wiese, Andreas
作者单位：Sapienza University Rome; Maastricht University; Vrije Universiteit Amsterdam; Max Planck Society
摘要：We study the problem of assigning sporadic tasks to unrelated machines such that the tasks on each machine can be feasibly scheduled. Despite its importance for modern real-time systems, this problem has not been studied before. We present a polynomial-time algorithm which approximates the problem with a constant speedup factor of and show that any polynomial-time algorithm needs a speedup factor of at least , unless P NP. In the case of a constant number of machines we give a polynomial-time ...
-
作者：Waldspurger, Irene; d'Aspremont, Alexandre; Mallat, Stephane
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
摘要：Phase retrieval seeks to recover a signal from the amplitude of linear measurements . We cast the phase retrieval problem as a non-convex quadratic program over a complex phase vector and formulate a tractable relaxation (called PhaseCut) similar to the classical MaxCut semidefinite program. We solve this problem using a provably convergent block coordinate descent algorithm whose structure is similar to that of the original greedy algorithm in Gerchberg and Saxton (Optik 35:237-246, 1972), wh...
-
作者：Pang, C. H. Jeffrey
作者单位：National University of Singapore
摘要：We study how the supporting hyperplanes produced by the projection process can complement the method of alternating projections and its variants for the convex set intersection problem. For the problem of finding the closest point in the intersection of closed convex sets, we propose an algorithm that, like Dykstra's algorithm, converges strongly in a Hilbert space. Moreover, this algorithm converges in finitely many iterations when the closed convex sets are cones in satisfying an alignment c...
