Combinatorial Optimization: 7th International Symposium, ISCO 2022, Virtual Event, May 18–20, 2022, Revised Selected Papers

Description

This book constitutes thoroughly refereed and revised selected papers from the 7th International Symposium on Combinatorial Optimization, ISCO 2022, which was held online during May 18–20, 2022. The 24 full papers included in this book were carefully reviewed and selected from 50 submissions. They were organized in topical sections as follows: Polyhedra and algorithms; polyhedra and combinatorics; non-linear optimization; game theory; graphs and trees; cutting and packing; applications; and approximation algorithms. Preface Organization Plenary Lectures Graphical Designs Advances in Approximation Algorithms for Tree Augmentation Algorithmic Data Science Recent Algorithmic Advances for Maximum-Entropy Sampling Contents Polyhedra and Algorithms New Classes of Facets for Complementarity Knapsack Problems 1 Introduction 2 Notations, Assumptions, and Previous Work 3 Separation Complexity of Lifted Cover Inequalities for CKP 4 New Families of Facet-Defining Inequalities 5 Future Direction References Branch-and-Cut for a 2-Commodity Flow Relocation Model with Time Constraints 1 Introduction 2 A TEN Model for the Item Relocation Problem 3 The Projected IRP Model 3.1 Extended Subtour Constraints and Projected Cost 3.2 Separating the Extended Subtour Constraints 4 Algorithmic Handling and Numerical Experiments 4.1 Separation Algorithm 4.2 Numerical Experiments 5 Conclusion: A Brief Discussion of the Lift Issue References The Constrained-Routing and Spectrum Assignment Problem: Valid Inequalities and Branch-and-Cut Algorithm 1 Introduction 2 The Constrained-Routing and Spectrum Assignment Problem 3 Integer Linear Programming Formulation 4 Valid Inequalities and Facets 4.1 Edge-Capacity-Cover Inequalities 4.2 Edge-Interval-Capacity-Cover Inequalities 4.3 Edge-Interval-Clique Inequalities 4.4 Edge-Slot-Assignment-Clique Inequalities 4.5 Slot-Assignment-Clique Inequalities 5 Branch-and-Cut Algorithm 6 Computational Study 7 Conclusion References Polyhedra and Combinatorics Top-k List Aggregation: Mathematical Formulations and Polyhedral Comparisons 1 Introduction 2 Preliminaries 3 Integer Programming Formulations 4 Polyhedral Comparison 5 Concluding Remarks References Bounded Variation in Binary Sequences 1 Introduction 2 Penalized Variation 3 Bounded Variation 4 Conclusion and Future Work References On Minimally Non-firm Binary Matrices 1 Introduction 2 Preliminaries 3 Simplicial 1s and Stretching 4 Superfirm Matrices and Odd Holes 5 Four Infinite Classes of Minimally Non-firm Matrices 6 Conclusion References Few Induced Disjoint Paths for H-Free Graphs 1 Introduction 1.1 Related Work 1.2 Our Results 2 Polynomial-Time Algorithms 3 Completing the Proof of Theorem 2 3.1 Omitting ``H''-Graphs and Six-Vertex Cycles 4 Conclusions References On Permuting Some Coordinates of Polytopes 1 Introduction and Motivation 2 (More) Background and Related Work 2.1 Relevant Polytopes 3 Results 3.1 Parity Constraints via Partial Permutations 3.2 Partial Permutation over Quad-Valued Coordinates 3.3 Partial Permutation over Three-Valued Coordinates 3.4 Sorting Polytopes 4 Concluding Remarks References Non-linear Optimization Piecewise Linearization of Bivariate Nonlinear Functions: Minimizing the Number of Pieces Under a Bounded Approximation Error 1 Problem Description and State of the Art 2 Definitions 3 A Framework for Solving the R2-Corridor Fitting Problem 3.1 Key Idea 1: Management of the Corridor Domain 3.2 Key Idea 2: The Maximal Piece in Direction d Problem 3.3 Key Idea 3: Computing a Feasible Solution of a Maximal Piece in Direction d Problem 4 Framework Key Points Instantiation 4.1 Scoring the Quality of Pieces 4.2 Choose a Progress Direction 4.3 Inner Approximation of a Corridor 5 Numerical Experiments 6 Conclusion References An Outer-Approximation Algorithm for Maximum-Entropy Sampling 1 Introduction 2 Outer Approximation 3 Convex Relaxations for [MESP]MESP 4 Disjunctive Cuts 5 Experiments 6 Next Steps References Mitigating Anomalies in Parallel Branch-and-Bound Based Algorithms for Mixed-Integer Nonlinear Optimization 1 Introduction 2 Anomalies in Parallel Algorithms 3 Opportunistic Parallel Branch-and-Bound in Minotaur 4 Reducing Detrimental Anomalies in Parallel NLP-BB 4.1 Unambiguous Branching Functions 4.2 Unambiguous Reliability Branching Scheme 4.3 A Hybrid Unambiguous Node Selection Strategy 4.4 Nondetrimental NLP-BB 5 Reducing Detrimental Anomalies in Parallel QG 6 Computational Results 7 Conclusions and Future Directions References Game Theory Exact Price of Anarchy for Weighted Congestion Games with Two Players 1 Introduction 2 Results 3 LP Based Proofs 4 Concluding Remarks References Nash Balanced Assignment Problem 1 Introduction 2 LP Formulation for BAP 3 Nash Fairness Solutions for the AP 3.1 Proportional Fairness 3.2 Characterization of NF Solutions for the AP 3.3 Existence of NF Solutions 4 Finding All NF Solutions for the AP 4.1 Upper Bound for the Number of NF Solutions 4.2 Algorithm for Finding All NF Solutions 4.3 Numerical Results 5 Conclusion References Graphs and Trees On the Thinness of Trees 1 Introduction 2 Definitions and Preliminaries 3 Characterization and Algorithm 3.1 The Algorithm: Rooted Trees, k-critical Vertices and Labels 3.2 Computing Thinness of Trees and Finding a Consistent Solution References Generating Spanning-Tree Sequences of a Fan Graph in Lexicographic Order and Ranking/Unranking Algorithms 1 Introduction 2 Preliminary 3 Generating Fan-Tree Sequences 4 Ranking and Unranking Algorithms 5 Concluding Remarks References Cutting and Packing High Multiplicity Strip Packing with Three Rectangle Types 1 Introduction 2 Solving 2DFSPP in Polynomial Time 3 Algorithm for 2DHMSPP with Three Rectangle Types 3.1 Partitioning the Packing 3.2 Grouping Vertical Sections 3.3 Ordering the Configurations 3.4 Rounding Fractional Rectangles 3.5 None of SCase1, SCase2, and SCase3 are Empty, count = 1, and f1(i) + f2(i) 1 for all Vertical Sections si SCase2 3.6 None of SCase1, SCase2, and SCase3 are Empty, count = 1, and f1(i) + f2(i) > 1 for at Least One Vertical Section si SCase2 4 Polynomial Time Implementation 5 Conclusion References Improved Bounds for Stochastic Extensible Bin Packing Under Distributional Assumptions 1 Introduction 2 Stochastic Extensible Bin Packing 3 Second-Order Stochastic Dominance 4 Restriction to a Family of Processing Time Distributions References Applications One Transfer per Patient Suffices: Structural Insights About Patient-to-Room Assignment 1 Introduction 2 Every Patient Has to Be Transferred at Most Once 3 No Need to Transfer Patients Arriving in the First Period 4 Upper Bounds on the Number of Patient Transfers 5 Conclusion References Tool Switching Problems in the Context of Overlay Printing with Multiple Colours 1 Introduction 2 CUF-ToSP 2.1 Two-Index Formulation for CUF-ToSP 3 GOF-ToSP 3.1 Five-Index Arc Flow Formulation for GOF-ToSP 3.2 Preprocessing 4 GOV-ToSP 4.1 Six-Index Arc Flow Formulation for GOV-ToSP 5 Computational Results 5.1 Test Instances 5.2 Results 6 Conclusions and Future Research References Optimal Vaccination Strategies for Multiple Dose Vaccinations 1 Introduction 2 Problem Description and Formulation 3 The Matching Approach 3.1 Without Capacities 3.2 Include Upper Bound on Vaccination Speed and Storage Capacity 3.3 Include Multiple Vaccines and Cross-Immunization 4 The Three-Dose Problem 5 Conclusion References Approximation Algorithms Pervasive Domination 1 Introduction 1.1 Our Model 1.2 Our Results 2 Related Work 3 Pervasive Partial Domination 3.1 Algorithm Analysis 4 Conclusion References Unified Greedy Approximability Beyond Submodular Maximization 1 Introduction 2 Weak Submodularity Ratio, -Augmentability, and Independence Systems 2.1 Separating Function Classes 3 –Augmentability 3.1 A Critical Function 3.2 –Augmentability on Independence Systems 4 Outlook References Neighborhood Persistency of the Linear Optimization Relaxation of Integer Linear Optimization 1 Introduction 2 Preliminaries 3 Main Results 4 Maximality of UTVPI Systems 5 Fixed-Parameter Tractability and Two-Approximability for Special Cases 6 Conclusion References Polynomial-Time Approximation Schemes for a Class of Integrated Network Design and Scheduling Problems with Parallel Identical Machines 1 Introduction and Results 1.1 Problem Definition 1.2 Our Results 1.3 Related Work 2 Proofs of Lemmas1 and 2 2.1 Proof of Lemma1 2.2 Proof of Lemma2 3 Proofs of Corollaries1 and 2 3.1 Case of {MST, SP}. References Author Index