Combinatorial Optimization : 8th International Symposium, ISCO 2024, la Laguna, Tenerife, Spain, May 22-24, 2024, Revised Selected Papers

• Autore: Basu Amitabh
• Pubblicazione: Cham : , : Springer, , 2024; ©2024
• Edizione: 1st ed.
• Descrizione fisica: 1 online resource (425 pages)
• Altri autori: MahjoubAli Ridha Salazar GonzálezJuan José
• Nota di contenuto: Intro -- Preface -- Organization -- Contents -- Integer Programming -- On Disjunction Convex Hulls by Lifting -- 1 Introduction -- 2 Definitions -- 2.1 Model and Notation -- 2.2 Convex Hull -- 2.3 Full Optimal Big-M Lifting -- 3 Results -- 4 Some Proofs, Proof Sketches, and Remarks -- References -- On a Geometric Graph-Covering Problem Related to Optimal Safety-Landing-Site Location -- 1 Introduction -- 2 Covering Edges with a Subset of a Finite Set of Balls -- 3 What Kind of Constraint Matrices Can We Get? -- 4 Efficiently Solvable Cases -- 4.1 When G Is a Unit-Grid Graph in Rd, d2, NV(G), and 1r(x)< -- [d]5/4, for All xN -- 4.2 When G Is a Path Intersecting Each Ball on a Subpath -- 4.3 A Fork-Free Set of Subtrees -- 5 Strong Fixing -- 6 Computational Experiments -- 7 Outlook -- References -- Quadratically Constrained Reformulation, Strong Semidefinite Programming Bounds, and Algorithms for the Chordless Cycle Problem -- 1 Introduction -- 2 QC Reformulation and SDP Relaxation -- 3 SDP Lagrangian Relaxation Bounds -- 3.1 Subgradient Optimization -- 4 Lagrangian Relaxation as a Warm Starter to BC -- 4.1 An Improved BC Algorithm -- 5 Preliminary Computational Experiments -- 6 Conclusions -- References -- A Family of Spanning-Tree Formulations for the Maximum Cut Problem -- 1 Introduction -- 2 Preliminaries and Related Work -- 3 A Family of Spanning-Tree Formulations for MaxCut -- 3.1 Basic Spanning-Tree Formulations -- 3.2 Improved Spanning-Tree Formulations -- 3.3 Separation of Odd-Cycle Inequalities for a Given Cycle -- 4 Computational Experiments -- 5 Conclusion -- References -- Optimal Cycle Selections: An Experimental Assessment of Integer Programming Formulations -- 1 Introduction -- 2 Formulations and Implementations -- 3 Experimental Results -- 3.1 Random Instances -- 3.2 Instances Associated with Steiner Triples. ; 4 MWCS with budget constraint -- 5 MWCS with maximum cycle length constraint -- 5.1 Formulation of 3-Cycle Selections -- 5.2 Polyhedral Study -- 5.3 Numerical Experiments -- 6 Conclusions -- References -- 1-Persistency of the Clique Relaxation of the Stable Set Polytope -- 1 Introduction -- 2 Definitions and Preliminary Results -- 3 1-Persistency on Relaxations of the Stable Set Polytope -- 3.1 Basic Results on the Family of Q-Persistent Graphs -- 3.2 Forbidden Structures for the Family of Q-Persistent Graphs -- 4 Final Remarks -- References -- Alternating Direction Method and Deep Learning for Discrete Control with Storage -- 1 Introduction -- 2 MINLP for Discrete Control with Storage -- 3 A Concrete Model: Pump Scheduling -- 4 ADM for Local Optimization by Decomposition -- 5 The Deep Learning Model -- 6 Experimental Evaluation -- 6.1 Benchmark, Dataset Generation, and Scaling -- 6.2 Hyperparameters of the Deep Learning Models -- 6.3 Parameters of the Optimization Algorithms -- 6.4 Performance of Deep Learning -- 6.5 Performance of the Hybrid Algorithm -- 7 Conclusions -- References -- Branch and Cut for Partitioning a Graph into a Cycle of Clusters -- 1 Introduction -- 2 Formulations -- 3 Valid Inequalities -- 3.1 Triangle Inequalities -- 3.2 Partition Inequalities -- 3.3 Subtour and Path Inequalitities -- 4 Primal Heuristics -- 5 Computational Experiments -- References -- Graph Theory -- Computing the Edge Expansion of a Graph Using Semidefinite Programming -- 1 Introduction -- 2 QP Formulation and a Semidefinite Relaxation -- 3 Fixing the Size k: Bisection Problem -- 3.1 SDP Lower Bounds for the Bisection Problem -- 3.2 A Heuristic for the Bisection Problem -- 3.3 A Branch-and-bound Algorithm for the Bisection Problem -- 3.4 Transformation to a Max-Cut Problem -- 4 Split and Bound -- 4.1 Pre-elimination -- 4.2 Computational Aspects. ; 5 Numerical Results -- 5.1 Benchmark Instances -- 5.2 Discussion of the Experiments -- 6 Summary and Future Research -- References -- Minimizing External Vertices in Hypergraph Orientations -- 1 Introduction -- 2 Notations, Definitions and Preliminaries -- 3 Computational Complexity of HOP -- 4 Polynomial Instances of HOP -- 5 An ILP Model for HOP -- 6 Computational Experiments -- 7 Conclusion -- References -- Open-Separating Dominating Codes in Graphs -- 1 Introduction -- 2 Existence, Bounds and Hardness -- 3 OSD-numbers of Some Graph Families -- 4 Polyhedra Associated with OSD-codes -- 5 Concluding Remarks -- References -- On the Complexity of the Minimum Chromatic Violation Problem -- 1 Introduction -- 1.1 Basic Definitions -- 2 Complexity of MCVP -- 3 A Polynomial Algorithm for MCVP on a Subclass of Unit Interval Graphs -- 4 Concluding Remarks -- References -- Crystal Trees -- 1 Introduction -- 2 Preliminary Concepts -- 3 Crystal Trees Are Distinct from Well Known Classes of Trees in Graphs -- 4 Algebraic Definition of Crystal Trees -- 4.1 A System of Crystal Trees -- 5 Conclusion -- References -- Parameterized Algorithms -- Reducing Treewidth for SAT-Related Problems Using Simple Liftings -- 1 Introduction -- 1.1 Related Work -- 2 Definitions and Formalization of the Question -- 2.1 Graphs and Tree Decompositions -- 2.2 Formulas and Satisfiability Problems -- 2.3 Graphs Associated with Formula -- 2.4 Simple Lifting and Problem Statement -- 3 A Solution Using the Incidence Graph -- 4 Near-Optimality of the Approach -- 5 Computation of a Lifting -- 6 Experiments -- 7 Conclusion -- References -- Total Matching and Subdeterminants -- 1 Introduction -- 2 General Graphs -- 2.1 Maximum Subdeterminants and Graph Structure -- 2.2 Algorithmic Results -- 3 Forests -- 4 Conclusions and Future Work -- References. ; A New Structural Parameter on Single Machine Scheduling with Release Dates and Deadlines -- 1 Introduction -- 2 Preliminaries -- 3 The (wED) Rule -- 3.1 Definition and Dominance -- 3.2 A Summit-Based Decomposition -- 4 The Algorithm -- 4.1 Core Concept -- 4.2 State Bounding -- 4.3 Complexity -- 4.4 Minimizing Lmax -- 5 Conclusion -- References -- Fixed-Parameter Algorithms for Cardinality-Constrained Graph Partitioning Problems on Sparse Graphs -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Contribution -- 2 Preliminaries -- 2.1 Fixed-Parameter Tractability -- 2.2 (n, p, q)-Lopsided Universal Set -- 2.3 Vertex-Weighted Max (Min) Connected k-Subgraph -- 3 Fixed-Parameter Algorithms for Max (Min) -FCGP Parameterized by k+d -- 4 FPT Algorithms for Max (Min) Connected -FCGP -- 4.1 FPT Algorithms Parameterized by k+ -- 4.2 FPT Algorithms Parameterized by k+d -- 4.3 Subexponential-Time FPT Algorithm on Apex-Minor-Free Graphs -- 4.4 FPT-AS for Connected -FCGP -- References -- Approximation Algorithms -- Sequencing Stochastic Jobs with a Single Sample -- 1 Introduction, Motivation, and Model -- 2 Preliminaries: Single Machine Scheduling by Samples -- 3 Relative Optimality Gap and Better Than Random Schedules -- 4 On Uniform Randomization as Adversary -- 5 Well Behaved Input Distributions -- 5.1 Symmetric Processing Time Distributions -- 5.2 Identical Processing Time Distributions up to Scaling -- 5.3 Translations of Identical Processing Time Distributions -- 5.4 Exponential Distributions and -Separated Priorities -- 6 Conclusions -- References -- The Thief Orienteering Problem on Series-Parallel Graphs -- 1 Introduction -- 2 Thief Orienteering on Series-Parallel Graphs -- 2.1 Removing Vertices with Degree 1 -- 2.2 Cut Vertices -- 2.3 Transforming Gx into a DAG -- 2.4 Algorithm Analysis -- References. ; Approximation Algorithm for Job Scheduling with Reconfigurable Resources -- 1 Introduction -- 2 Problem Description and Notations -- 3 Identical-Machines Scheduling -- 4 Presentation of the Algorithm -- 5 Approximation Analysis -- 6 Generation of Packings with Small Volume -- 6.1 Dynamic Programming for the Single-Period Problems -- 6.2 Optimum Packing with Unlimited Scale -- 6.3 Consequences for Multi_Bot -- 7 Perspectives -- References -- Network Design on Undirected Series-Parallel Graphs -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Results -- 2 Preliminaries -- 3 Pseudopolynomial Algorithm -- 4 Fully Polynomial Time Approximation Scheme -- 5 Further Extensions -- 5.1 Capacities from a Lattice -- 5.2 Edge Upgrades -- References -- Online Graph Coloring with Predictions -- 1 Introduction -- 1.1 Preliminaries -- 1.2 Our Contribution -- 2 A Structural Theorem About FirstFit -- 3 Algorithmic Results -- 3.1 FirstFitPredictions (FFP) -- 3.2 RobustFirstFitPredictions(RFFP) -- 3.3 Results for Specific Classes of Graphs -- 4 Discussion -- References -- Integer Programming for Machine Learning -- Neuron Pairs in Binarized Neural Networks Robustness Verification via Integer Linear Programming -- 1 Introduction -- 2 Robustness Verification Problem in BNNs -- 2.1 Description of BNNs -- 2.2 Robustness Verification Problem -- 2.3 Related Work -- 3 Disjunctive Programming Based View to Neuron Pairs in BNNs -- 3.1 Single Neuron Convexification -- 3.2 Disjunctive Programming Based Approach for Neuron Pairs -- 3.3 Separation Procedure w.r.t. conv(S2) -- 3.4 Facet Defining Inequalities -- 4 Computational Experiments -- 4.1 Evaluated Methods and Setup -- 4.2 Computational Results -- 5 Conclusion -- References -- Optimal Counterfactual Explanations for k-Nearest Neighbors Using Mathematical Optimization and Constraint Programming -- 1 Introduction. ; 2 Problem Definition.
• Titolo autorizzato: Combinatorial Optimization
• ISBN: 3-031-60924-7
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 996601562903316
• Lo trovi qui: Univ. di Salerno
• Serie: Lecture Notes in Computer Science Series