the proceedings contain 33 papers. the special focus in this conference is on integerprogramming and combinatorialoptimization. the topics include: A Better-than-1.6-Approximation for Prize-Collecting TSP;on Ma...
ISBN:
(纸本)9783031598340
the proceedings contain 33 papers. the special focus in this conference is on integerprogramming and combinatorialoptimization. the topics include: A Better-than-1.6-Approximation for Prize-Collecting TSP;on Matrices over a Polynomial Ring with Restricted Subdeterminants;a First Order Method for Linear programming Parameterized by Circuit Imbalance;approximately Packing Dijoins via Nowhere-Zero Flows;capacitated Facility Location with Outliers and Uniform Facility Costs;integer Points in Arbitrary Convex Cones: the Case of the PSD and SOC Cones;the Extension Complexity of Polytopes with Bounded Integral Slack Matrices;assortment optimization with Visibility Constraints;adaptivity Gaps in Two-Sided Assortment optimization;two-Stage Stochastic Stable Matching;von Neumann-Morgenstern Stability and Internal Closedness in Matching theory;fully-Dynamic Load Balancing;pairwise-Independent Contention Resolution;An FPTAS for Connectivity Interdiction;tight Lower Bounds for Block-Structured integer Programs;A Lower Bound for the Max Entropy Algorithm for TSP;on the Number of Degenerate Simplex Pivots;on the Partial Convexification of the Low-Rank Spectral optimization: Rank Bounds and Algorithms;on the Congruency-Constrained Matroid Base;online combinatorial Assignment in Independence Systems;decomposing Probability Marginals Beyond Affine Requirements;polynomial Algorithms to Minimize 2/3-Submodular Functions;A 43-Approximation for the Maximum Leaf Spanning Arborescence Problem in DAGs;extending the Primal-Dual 2-Approximation Algorithm Beyond Uncrossable Set Families;network Flow Problems with Electric Vehicles;lower Bounds on the Complexity of Mixed-integer Programs for Stable Set and Knapsack;relaxation Strength for Multilinear optimization: McCormick Strikes Back;online Algorithms for Spectral Hypergraph Sparsification;fast combinatorial Algorithms for Efficient Sortation;a New Branching Rule for Range Minimization Problems;sensitivity Analysis for Mixed Binary Quadrat
the proceedings contain 33 papers. the special focus in this conference is on integerprogramming and combinatorialoptimization. the topics include: An Update-and-Stabilize Framework for the Minimum-Norm-Po...
ISBN:
(纸本)9783031327254
the proceedings contain 33 papers. the special focus in this conference is on integerprogramming and combinatorialoptimization. the topics include: An Update-and-Stabilize Framework for the Minimum-Norm-Point Problem;stabilization of Capacitated Matching Games;designing optimization Problems with Diverse Solutions;ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation;on the Correlation Gap of Matroids;A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP;the Polyhedral Geometry of Truthful Auctions;competitive Kill-and-Restart and Preemptive Strategies for Non-clairvoyant Scheduling;A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP;Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products;monoidal Strengthening of Simple V -Polyhedral Disjunctive Cuts;optimal General Factor Problem and Jump System Intersection;decomposition of Probability Marginals for Security Games in Abstract Networks;set Selection Under Explorable Stochastic Uncertainty via Covering Techniques;towards a Characterization of Maximal Quadratic-Free Sets;compressing Branch-and-Bound Trees;exploiting the Polyhedral Geometry of Stochastic Linear Bilevel programming;towards an Optimal Contention Resolution Scheme for Matchings;Advances on Strictly Δ -Modular IPs;cut-Sufficient Directed 2-Commodity Multiflow Topologies;a Nearly Optimal Randomized Algorithm for Explorable Heap Selection;constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid;a Fast combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints;multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching;a Linear Time Algorithm for Linearizing Quadratic and Higher-Order Shortest Path Problems;sparse Approximation over the Cube;recycling Inequalities for Robust combinatorialoptimization with Budget Uncertainty;inapproximability of Shortest Paths on Perfect Matching Polyt
Mixed-integer convex representable (MICP-R) sets are those sets that can be represented exactly through a mixed-integer convex programming formulation. Following up on recent work by Lubin et al. (in: Eisenbrand (ed) ...
详细信息
Mixed-integer convex representable (MICP-R) sets are those sets that can be represented exactly through a mixed-integer convex programming formulation. Following up on recent work by Lubin et al. (in: Eisenbrand (ed) integerprogramming and combinatorialoptimization - 19thinternationalconference, Springer, Waterloo), (Math. Oper. Res. 47:720-749, 2022) we investigate structural geometric properties of MICP-R sets, which strongly differentiate them from the class of mixed-integer linear representable (MILP-R) sets. First, we provide an example of an MICP-R set which is the countably infinite union of convex sets with countably infinitely many different recession cones. this is in sharp contrast with MILP-R sets which are (countable) unions of polyhedra that share the same recession cone. Second, we provide an example of an MICP-R set which is the countably infinite union of polytopes all of which have different shapes (no pair is combinatorially equivalent, which implies they are not affine transformations of each other). Again, this is in sharp contrast with MILP-R sets which are (countable) unions of polyhedra that are all translations of a finite subset of themselves.
We consider the problem of single link failure in an elastic optical network, (also known as flex-grid WDM network). the task is to reroute optical connections that go through the broken link using free capacity of ot...
详细信息
ISBN:
(纸本)9798350351866;9798350351859
We consider the problem of single link failure in an elastic optical network, (also known as flex-grid WDM network). the task is to reroute optical connections that go through the broken link using free capacity of other links of the network. Nowadays, dynamic restoration gains popularity, in which the possiblity of rerouting is only inspected after a link failure is detected. Since the problem of recovery is NP-hard, heuristic algorithms are used to either find such routes, or suggest that the routes do not exist. In order to understand the quality of these heuristics, often mixed integer linear programming is used to obtain exact positive and negative answers. We present a detailed such model that checks whether restoration is possible without the use of additional regenerators. this means, that the new light paths need to satisfy a length constraint. As preprossing we apply a trimming procedure that takes advantage of this length constraint, and significantly speeds up the evaluation of these models. Our model is more general, and besides solving the problem of link restoration, also solves the full problem of wavelength and spectrum assignment.
Various algorithms can be used to optimize the operation of energy hubs, which differ in complexity and optimization quality. the heuristic Evolutionary Algorithm (EA) is able to approximate solutions to complex and n...
详细信息
ISBN:
(纸本)9798350377385;9798350377378
Various algorithms can be used to optimize the operation of energy hubs, which differ in complexity and optimization quality. the heuristic Evolutionary Algorithm (EA) is able to approximate solutions to complex and non-convex problems. In comparison, the Mixed-integer Linear programming (MILP) and the Mixed-integer Quadratic Program (MIQP) are able to compute the optimal solution of an approximated model. the present paper focuses on the comparison of energy hub schedule optimization using an EA, a MILP, and a MIQP. Furthermore, the source code for the MILP and MIQP models is publicly available. In our comparison, the analytical solver can optimize the schedule of an exemplary energy hub within seconds, and the EA takes multiple minutes to compute. the schedule generated withthe analytical models follows the target closely with a similar root-mean-square error as the schedule generated by the EA.
We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral con...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral cones can sometimes have a notion of finite generating set. We show this is true for the cone of positive semidefinite matrices (PSD) and the second-order cone (SOC). Both cones have a finite generating set of integer points, similar in spirit to Hilbert bases, under the action of a finitely generated group. We also extend notions of total dual integrality, Gomory-Chv ' atal closure, and Carath ' eodory rank to integer points in arbitrary cones.
We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick lineari...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146-152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, we complement Khajavirad's result by showing that the intersection of the relaxations of such linearizations and the extended flower relaxation are equally strong.
In recent years, the advantages of Graph Neural Networks (GNNs) in solving complex combinatorialoptimization problems have become more and more obvious. Under this background, this paper demonstrates a method based o...
详细信息
We obtain new transference bounds that connect two active areas of research: proximity and sparsity of solutions to integer programs. Specifically, we study the additive integrality gap of the integer linear programs ...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
We obtain new transference bounds that connect two active areas of research: proximity and sparsity of solutions to integer programs. Specifically, we study the additive integrality gap of the integer linear programs min{c.x : x is an element of P boolean AND Z(n)}, where P = {x is an element of R-n : Ax = b, x >= 0} is a polyhedron in the standard form determined by an integer m x n matrix A and an integer vector b. the main result of the paper gives an upper bound for the integrality gap that drops exponentially in the size of support of the optimal solutions corresponding to the vertices of the integer hull of P. Additionally, we obtain a new proximity bound that estimates the l(2)-distance from a vertex of P to its nearest integer point in the polyhedron P. the proofs make use of the results from the geometry of numbers and convex geometry.
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.
暂无评论