Integer Programming and Combinatorial Optimization : 24th International Conference, IPCO 2023, Madison, WI, USA, June 21–23, 2023, Proceedings / edited by Alberto Del Pia, Volker Kaibel.

Format:

Book

Author/Creator:

Del Pia, Alberto.

Contributor:

Kaibel, Volker.

Series:

Lecture Notes in Computer Science, 1611-3349 ; 13904

Language:

English

Subjects (All):

Computer science--Mathematics.

Computer science.

Mathematics--Data processing.

Mathematics.

Discrete mathematics.

Application software.

Mathematics of Computing.

Computational Mathematics and Numerical Analysis.

Discrete Mathematics in Computer Science.

Computer and Information Systems Applications.

Local Subjects:

Mathematics of Computing.

Computational Mathematics and Numerical Analysis.

Discrete Mathematics in Computer Science.

Computer and Information Systems Applications.

Physical Description:

1 online resource (494 pages)

Edition:

1st ed. 2023.

Place of Publication:

Cham : Springer International Publishing : Imprint: Springer, 2023.

Summary:

This book constitutes the refereed proceedings of the 24th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2023, held in Madison, WI, USA, during June 21–23, 2023. The 33 full papers presented were carefully reviewed and selected from 119 submissions. IPCO is under the auspices of the Mathematical Optimization Society, and it is an important forum for presenting present recent developments in theory, computation, and applications. The scope of IPCO is viewed in a broad sense, to include algorithmic and structural results in integer programming and combinatorial optimization as well as revealing computational studies and novel applications of discrete optimization to practical problems.

Contents:

Intro

Preface

Organization

Contents

Information Complexity of Mixed-Integer Convex Optimization

1 First-order Information Complexity

1.1 Our Results

1.2 Formal Definitions and Statement of Results

1.3 Discussion and Future Avenues

2 Proof Sketches

2.1 Proof Sketch of Theorem 1

2.2 Proof of Theorem 3

2.3 Proof Sketch of Theorem 5

2.4 Proof Sketch of Theorems 2 and 4

References

Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products

1 Introduction

2 RLT for Bilinear Products

3 Detection of Implicit Products

4 Separation Algorithm

4.1 Row Marking

4.2 Projection Filtering

5 Computational Results

5.1 Setup

5.2 Impact of RLT Cuts

5.3 Separation

5.4 Experiments with Gurobi

5.5 Summary

A Nearly Optimal Randomized Algorithm for Explorable Heap Selection

2 The Explorable Heap Selection Problem

3 A New Algorithm

3.1 The Algorithm

3.2 Proof of Correctness

3.3 Running Time Analysis

3.4 Space Complexity Analysis

4 Lower Bound

Sparse Approximation over the Cube

1 Introduction and Literature Review

2 Preliminaries

3 The l1-Relaxation for Random Targets b

4 Proximity Between Optimal Solutions of ([P0]P0) and ([P1]P1)

5 A Deterministic Algorithm

6 Extension

Recycling Inequalities for Robust Combinatorial Optimization with Budget Uncertainty

2 Recycling Valid Inequalities

3 Facet-Defining Recycled Inequalities

4 Computational Study

4.1 Robust Independent Set

4.2 Robust Bipartite Matching

5 Conclusion

Inapproximability of Shortest Paths on Perfect Matching Polytopes

1.1 Our Result

1.2 Pivot Rules for Circuit-Augmentation Algorithms

1.3 Related Works

2 Proof of Theorem 1.

2.1 Preliminaries

2.2 Reduction

2.3 Proof of Lemma 3

Monoidal Strengthening and Unique Lifting in MIQCPs

2 Monoidal Strengthening in the Homogeneous Case

3 Monoidal Strengthening in the Non-homogeneous Case

3.1 A Technical Consideration for Sg

3.2 Monoid Construction

4 Solving the Monoidal Strengthening Problem

5 Unique Lifting

6 Computational Results

From Approximate to Exact Integer Programming

1.1 Contributions of This Paper

1.2 Related Work

3 The Cut-Or-Average Algorithm

3.1 Bounding the Number of Iterations

3.2 Correctness and Efficiency of Subroutines

3.3 Conclusion on the Cut-Or-Average Algorithm

4 An Asymmetric Approximate Carathéodory Theorem

5 IPs with Polynomial Variable Range

Optimizing Low Dimensional Functions over the Integers

1.1 Applications

1.2 Overview of Techniques

2 Non-negative Variables

3 Bounded Variables

4 Overview of Hunkenschröder Et Al. ch9hunkenschroder2022optimizing and Related Improvements

5 Conclusion and Open Questions

Configuration Balancing for Stochastic Requests

1.2 Technical Overview

1.3 Related Work

2 Configuration Balancing with Stochastic Requests

2.1 Structural Theorem

2.2 Offline Setting

2.3 Online Setting

3 Load Balancing on Related Machines

An Update-and-Stabilize Framework for the Minimum-Norm-Point Problem

2.1 Optimal Solutions and Proximity

2.2 The Centroid Mapping

3 The Update-and-Stabilize Framework

4 Analysis

5 Computational Experiments

Stabilization of Capacitated Matching Games

2 Preliminaries and Notation

3 M-vertex-stabilizer.

4 Vertex-Stabilizer

5 Capacitated Cooperative Matching Games

Designing Optimization Problems with Diverse Solutions

2 Statement of Main Results

2.1 The Cyclic Polytope

2.2 Results and Techniques

3 Preliminaries

4 Upper Bound (Proof of Theorem 1)

5 General Lower Bound (Proof of Theorem 2)

5.1 Construction Based on Moment Curve

5.2 Dual Certificate for Loadouts

5.3 Counting the Number of k-Loadouts

6 Conclusion

ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation

1.1 Our Main Results

1.2 Discussion of the Results

1.3 Further Related Work

2 Algorithms and Proof Overview

On the Correlation Gap of Matroids

1.1 Our Techniques

3 Locating the Correlation Gap

4 Lower Bounding the Correlation Gap

4.1 Lower Bounding G(x*)

4.2 Lower Bounding H(x*)

4.3 Putting Everything Together

A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP

3 Proof of Theorem 1

4 Conclusion and Open Questions

The Polyhedral Geometry of Truthful Auctions

3 Characterization of One-Player Mechanisms

4 Sensitivity of Mechanisms

Competitive Kill-and-Restart and Preemptive Strategies for Non-clairvoyant Scheduling

3 Lower Bound

4 The b-scaling Strategy

4.1 The Deterministic b-scaling Strategy

4.2 The Randomized b-scaling Strategy

5 Weighted Shortest Elapsed Time First

6 Upper Bounds for More General Settings

7 Conclusion

A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP

1.1 High Level Proof Overview.

2 Preliminaries

2.1 Notation

2.2 Randomized Algorithm of ch19KKO21a

2.3 Polyhedral Background

3 Computing Probabilities

3.1 Notation

3.2 Matrix Tree Theorem

3.3 Computing Parities in a Simple Case

4 A Deterministic Algorithm in the Degree Cut Case

5 General Case

Monoidal Strengthening of Simple V-Polyhedral Disjunctive Cuts

2 Notation and Background

3 Correspondence Between PRLP and CGLP Solutions

3.1 Simple VPCs

3.2 Relaxations Without Primal Degeneracy

3.3 Relaxations with Primal Degeneracy

4 Computational Experiments

5 Choosing a Relaxation Amenable to Strengthening

Optimal General Factor Problem and Jump System Intersection

1.1 General Factor Problem

1.2 Jump System Intersection

1.3 Our Contribution: Jump System with SBO Property

1.4 Organization

3 Algorithm and Correctness

4 Outline of the Proof of Lemma 1

4.1 Minimal Counterexample

4.2 Part of Case Analysis: |U|=3

5 Extension to Valuated Problem

6 Weighted Optimal General Factor Problem

7 Concluding Remarks

Decomposition of Probability Marginals for Security Games in Abstract Networks

1.1 Motivation

1.2 Abstract Networks

1.3 Previous Results

1.4 Our Results

1.5 Notation

2 Feasible Decompositions in Abstract Networks

3 Computing Feasible Decompositions

4 Computing Shortest Paths in Abstract Networks

5 Dahan et al.'s Network Security Game

6 The Conservation Law for Partially Ordered Sets

7 Other Set Systems

Set Selection Under Explorable Stochastic Uncertainty via Covering Techniques

2 Algorithmic Framework

2.1 Offline Problems and Hardness of Approximation

2.2 Algorithmic Framework.

3 MinSet with Deterministic Right-Hand Sides

4 MinSet Under Uncertainty

5 Disjoint MinSet

Towards a Characterization of Maximal Quadratic-Free Sets

1.1 Contributions

2 Examples of Maximal Homogeneous Quadratic-Free Sets

3 A Proof of Theorem 5

4 A Proof of Theorem 1

5 A Proof of Theorem 2

6 Preliminary Results on Non-expansive Functions

7 A Proof of Theorem 3

8 A Proof of Theorem 4

Compressing Branch-and-Bound Trees

2 The Tree Compression Problem (TCP)

3 Complexity Results and Lower Bounds

4 Compression Algorithms

4.1 An Exact Method

4.2 A Heuristic Method

5.1 Methodology

5.2 Full Strong Branching Results

5.3 Reliability Branching with Plunging

6 Future Work

Exploiting the Polyhedral Geometry of Stochastic Linear Bilevel Programming

1.1 Problem Formulation and Contributions

3 Vertex-Supported Beliefs and Bayesian Formulation

3.1 Sample Average Formulation

4 Geometrical Structure of Vertex-Supported Beliefs

5 Algorithms

5.1 Enumeration Algorithm

5.2 Monte-Carlo Approximation Scheme

6 Numerical Experiments

Towards an Optimal Contention Resolution Scheme for Matchings

1.2 Our Techniques

2 An Optimal CRS When "026B30D x"026B30D 0

2.1 The Karp-Sipser Algorithm

2.2 Random Trees

2.3 The Karp-Sipser Algorithm on Trees

2.4 Putting It Together

3 Improved CRSs for Bipartite Matchings

3.1 A 0.480-Balanced Scheme for Bipartite Matchings

3.2 A 0.509-Balanced Scheme for Bipartite Matchings

Advances on Strictly -Modular IPs

1.1 Group-Constrained Problems and Proof Strategy for Theorem 1

1.2 Further Related Work.

1.3 Structure of the Paper.

Notes:

Description based on publisher supplied metadata and other sources.

Other Format:

Print version: Del Pia, Alberto Integer Programming and Combinatorial Optimization

ISBN:

9783031327261

OCLC:

1379802598