the proceedings contain 32 papers. the special focus in this conference is on Session 1 and Session 2. the topics include: Robust branch-and-cut-and-price for the capacitated vehicle routing problem;metric inequalitie...
ISBN:
(纸本)3540221131
the proceedings contain 32 papers. the special focus in this conference is on Session 1 and Session 2. the topics include: Robust branch-and-cut-and-price for the capacitated vehicle routing problem;metric inequalities and the network loading problem;valid inequalities based on simple mixed-integer sets;the price of anarchy when costs are non-separable and asymmetric;computational complexity, fairness, and the price of anarchy of the maximum latency problem;polynomial time algorithm for determining optimal strategies in cyclic games;a robust optimization approach to supply chain management;approximation algorithms for stochastic optimization problems;scheduling an industrial production facility;three min-max theorems concerning cyclic orders of strong digraphs;a TDI description of restricted 2-matching polytopes;enumerating minimal dicuts and strongly connected subgraphs and related geometric problems;semi-continuous cuts for mixed-integerprogramming;combinatorial benders’ cuts;a faster exact separation algorithm for blossom inequalities;LP-based approximation algorithms for capacitated facility location;a multiexchange local search algorithm for the capacitated facility location problem;separable concave optimization approximately equals piecewise linear optimization;three kinds of integerprogramming algorithms based on barvinok’s rational functions;the path-packing structure of graphs;more on a binary-encoded coloring formulation;single machine scheduling with precedence constraints;the constrained minimum weighted sum of job completion times problem;near-optimum global routing with coupling, delay bounds, and power consumption;a flow-based method for improving the expansion or conductance of graph cuts;all rational polytopes are transportation polytopes and all polytopal integer sets are contingency tables;a capacity scaling algorithm for M-convex submodular flow and integer concave cocirculations and honeycombs.
the perceptron algorithm for linear programming, arising from machine learning, has been around since the 1950s. While not a polynomial-time algorithm, it is useful in practice due to its simplicity and robustness. In...
详细信息
ISBN:
(纸本)9783319592503;9783319592497
the perceptron algorithm for linear programming, arising from machine learning, has been around since the 1950s. While not a polynomial-time algorithm, it is useful in practice due to its simplicity and robustness. In 2004, Dunagan and Vempala showed that a randomized rescaling turns the perceptron method into a polynomial time algorithm, and later Pena and Soheili gave a deterministic rescaling. In this paper, we give a deterministic rescaling for the perceptron algorithm that improves upon the previous rescaling methods by making it possible to rescale much earlier. this results in a faster running time for the rescaled perceptron algorithm. We will also demonstrate that the same rescaling methods yield a polynomial time algorithm based on the multiplicative weights update method. this draws a connection to an area that has received a lot of recent attention in theoretical computer science.
One of the most famous conjectures in combinatorialoptimization is the four-thirds conjecture, which states that the integrality gap of the subtour LP relaxation of the TSP is equal to 4/3. For 40 years, the best kno...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
One of the most famous conjectures in combinatorialoptimization is the four-thirds conjecture, which states that the integrality gap of the subtour LP relaxation of the TSP is equal to 4/3. For 40 years, the best known upper bound was 1.5, due to Wolsey [Wol80]. Recently, Karlin, Klein, and Oveis Gharan [KKO22] showed that the max entropy algorithm for the TSP gives an improved bound of 1.5 - 10(-36). In this paper, we show that the approximation ratio of the max entropy algorithm is at least 1.375, even for graphic TSP. thus the max entropy algorithm does not appear to be the algorithm that will ultimately resolve the four-thirds conjecture in the affirmative, should that be possible.
the volume contains the papers selected for presentation at ipco 2008, the 13thinternationalconference on integerprogramming and combinatorial - timization that was held in Bertinoro (Italy), May 26–28, 2008. the ...
详细信息
ISBN:
(数字)9783540688914
ISBN:
(纸本)9783540688860
the volume contains the papers selected for presentation at ipco 2008, the 13thinternationalconference on integerprogramming and combinatorial - timization that was held in Bertinoro (Italy), May 26–28, 2008. the ipco series of conferences, sponsored by the Mathematical Progr- ming Society, highlights recent developments in theory, computation, and app- cation of integerprogramming and combinatorialoptimization. the ?rst conf- ence took place in 1990; starting from ipco 1995, the proceedings are published in the Lecture Notes in Computer Science series. the 12 previous ipcoconferences were held in Waterloo (Canada) 1990, Pittsburgh (USA) 1992, Erice (Italy) 1993, Copenhagen (Denmark) 1995 [LNCS 920], Vancouver (Canada) 1996 [LNCS 1084], Houston (USA) 1998 [LNCS 1412], Graz (Austria) 1999 [LNCS 1610], Utrecht (the Netherlands) 2001 [LNCS 2081], Boston (USA) 2002 [LNCS 2337], New York (USA) 2004 [LNCS 2986], Berlin (Germany) 2005 [LNCS 3509], and Ithaca (USA) 2007 [LNCS 4168]. the c- ference is not held in the years when the international Symposium of the Ma- ematical programming Society takes place.
this paper presents three kinds of algebraic-analytic algorithms for solving integer and mixed integerprogramming problems. We report boththeoretical and experimental results. We use the generating function techniqu...
详细信息
ISBN:
(纸本)3540221131
this paper presents three kinds of algebraic-analytic algorithms for solving integer and mixed integerprogramming problems. We report boththeoretical and experimental results. We use the generating function techniques introduced by A. Barvinok.
We study the problem of optimizing over the set of all combinatorial embeddings of a given planar graph. Our objective function prefers certain cycles of G as face cycles in the embedding. the motivation for studying ...
详细信息
ISBN:
(纸本)3540660194
We study the problem of optimizing over the set of all combinatorial embeddings of a given planar graph. Our objective function prefers certain cycles of G as face cycles in the embedding. the motivation for studying this problem arises in graph drawing, where the chosen embedding has an important influence on the aesthetics of the drawing. We characterize the set of all possible embeddings of a given biconnected planar graph G by means of a system of linear inequalities with {0, 1}-variables corresponding to the set of those cycles in G which can appear in a combinatorial embedding. this system of linear inequalities can be constructed recursively using SPQR-trees and a new splitting operation. Our computational results on two benchmark sets of graphs are surprising: the number of variables and constraints seems to grow only linearly withthe size of the graphs although the number of embeddings grows exponentially. For all tested graphs (up to 500 vertices) and linear objective functions, the resulting integer linear programs could be generated within 10 minutes and solved within two seconds on a Sun Enterprise 10000 using CPLEX.
In this paper we use facets of the convex hull of mixed-integer sets with two and three variables to derive valid inequalities for integer sets defined by a single equation. these inequalities also define facets of th...
详细信息
ISBN:
(纸本)3540221131
In this paper we use facets of the convex hull of mixed-integer sets with two and three variables to derive valid inequalities for integer sets defined by a single equation. these inequalities also define facets of the master cyclic group polyhedron of Gomory. In particular, our inequalities generalize the 2slope facets of Araoz, Gomory, Johnson and Evans (2003). In addition, they dominate the strong fractional cuts of Letchford and Lodi (2002).
Motivated by applications in e-retail and online advertising, we study the problem of assortment optimization under visibility constraints, referred to as APV. We are given a universe of substitutable products and a s...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
Motivated by applications in e-retail and online advertising, we study the problem of assortment optimization under visibility constraints, referred to as APV. We are given a universe of substitutable products and a stream of T customers. the objective is to determine the optimal assortment of products to offer to each customer in order to maximize the total expected revenue, subject to the constraint that each product is required to be shown to a minimum number of customers. the minimum display requirement for each product is given exogenously and we refer to these constraints as visibility constraints. We assume that customer choices follow a Multinomial Logit model. We provide a characterization of the structure of the optimal assortments and present an efficient polynomial time algorithm for solving APV. To accomplish this, we introduce a novel function called the "expanded revenue" of an assortment and establish its supermodularity. Our algorithm takes advantage of this structural property. Additionally, we demonstrate that APV can be formulated as a compact linear program. Finally, we propose a novel, fair strategy for pricing the revenue loss due to the enforcement of visibility constraints.
Many hierarchies of lift-and-project relaxations for 0,1 integer programs have been proposed, two of the most recent and strongest being those by Lasserre in 2001, and Bienstock and Zuckerberg in 2004. We prove that, ...
详细信息
ISBN:
(纸本)9783642208072
Many hierarchies of lift-and-project relaxations for 0,1 integer programs have been proposed, two of the most recent and strongest being those by Lasserre in 2001, and Bienstock and Zuckerberg in 2004. We prove that, on the LP relaxation of the matching polytope of the complete graph on (2n+1) vertices defined by the nonnegativity and degree constraints, the Bienstock-Zuckerberg operator (even with positive semidefiniteness constraints) requires theta(root n) rounds to reach the integral polytope, while the Lasserre operator requires theta(n) rounds. We also prove that Bienstock-Zuckerberg operator, without the positive semidefiniteness constraint requires approximately n/2 rounds to reach the stable set polytope of the n-clique, if we start withthe fractional stable set polytope. As a by-product of our work, we consider a significantly strengthened version of Sherali-Adams operator and a strengthened version of Bienstock-Zuckerberg operator. Most of our results also apply to these stronger operators.
暂无评论