top

  Info

  • Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.

  Info

  • Utilizzare questo link per rimuovere la selezione effettuata.

Biblioteca

MARC Lista (tabellare)
Applications of combinatorial optimization / / edited by Vangelis Th. Paschos
Applications of combinatorial optimization / / edited by Vangelis Th. Paschos
Edizione [Revised and updated second edition.]
Pubbl/distr/stampa London, [England] ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2014
Descrizione fisica 1 online resource (449 p.)
Disciplina 519.64
Collana Mathematics and Statistics Series
Soggetto topico Combinatorial optimization
ISBN 1-119-00538-8
1-119-01522-7
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Cover; Title Page; Copyright; Contents; Preface; Chapter 1: Airline Crew Pairing Optimization; 1.1. Introduction; 1.2. Definition of the problem; 1.2.1. Constructing subnetworks; 1.2.2. Pairing costs; 1.2.3. Model; 1.2.4. Case without resource constraints; 1.3. Solution approaches; 1.3.1. Decomposition principles; 1.3.2. Column generation, master problem and subproblem; 1.3.3. Branching methods for finding integer solutions; 1.4. Solving the subproblem for column generation; 1.4.1. Mathematical formulation; 1.4.2. General principle of effective label generation
1.4.3. Case of one single resource: the bucket method1.4.4. Case of many resources: reduction of the resource space; 1.4.4.1. Reduction principle; 1.4.4.2. Approach based on the Lagrangian relaxation; 1.4.4.3. Approach based on the surrogate relaxation; 1.5. Conclusion; 1.6. Bibliography; Chapter 2: The Task Allocation Problem; 2.1. Presentation; 2.2. Definitions and modeling; 2.2.1. Definitions; 2.2.2. The processors; 2.2.3. Communications; 2.2.4. Tasks; 2.2.5. Allocation types; 2.2.5.1. Static allocation; 2.2.5.2. Dynamic allocation; 2.2.5.3. With or without pre-emption
2.2.5.4. Task duplication2.2.6. Allocation/scheduling; 2.2.7. Modeling; 2.2.7.1. Modeling costs; 2.2.7.2. Constraints; 2.2.7.3. Objectives of the allocation; 2.2.7.3.1. Minimizing the execution duration; 2.2.7.3.2. Minimizing the global execution and communication cost; 2.2.7.3.3. Load balancing; 2.3. Review of the main works; 2.3.1. Polynomial cases; 2.3.1.1. Two-processor cases; 2.3.1.2. Tree case; 2.3.1.3. Other structures; 2.3.1.4. Restrictions on the processors or the tasks; 2.3.1.5. Minmax objective; 2.3.2. Approximability; 2.3.3. Approximate solution; 2.3.3.1. Heterogenous processors
2.3.3.2. Homogenous processors2.3.4. Exact solution; 2.3.5. Independent tasks case; 2.4. A little-studied model; 2.4.1. Model; 2.4.2. A heuristic based on graphs; 2.4.2.1. Transformation of the problem; 2.4.2.2. Modeling; 2.4.2.3. Description of the heuristic; 2.5. Conclusion; 2.6. Bibliography; Chapter 3: A Comparison of Some Valid Inequality Generation Methods for General 0-1 Problems; 3.1. Introduction; 3.2. Presentation of the various techniques tested; 3.2.1. Exact separation with respect to a mixed relaxation; 3.2.2. Approximate separation using a heuristic
3.2.3. Restriction + separation + relaxed lifting (RSRL)3.2.4. Disjunctive programming and the lift and project procedure; 3.2.5. Reformulation-linearization technique (RLT); 3.3. Computational results; 3.3.1. Presentation of test problems; 3.3.2. Presentation of the results; 3.3.3. Discussion of the computational results; 3.4. Bibliography; Chapter 4: Production Planning; 4.1. Introduction; 4.2. Hierarchical planning; 4.3. Strategic planning and productive system design; 4.3.1. Group technology; 4.3.2. Locating equipment; 4.4. Tactical planning and inventory management
4.4.1. A linear programming model for medium-term planning
Record Nr. UNINA-9910132155703321
London, [England] ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2014
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Applications of combinatorial optimization / / edited by Vangelis Th. Paschos
Applications of combinatorial optimization / / edited by Vangelis Th. Paschos
Edizione [Revised and updated second edition.]
Pubbl/distr/stampa London, [England] ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2014
Descrizione fisica 1 online resource (449 p.)
Disciplina 519.64
Collana Mathematics and Statistics Series
Soggetto topico Combinatorial optimization
ISBN 1-119-00538-8
1-119-01522-7
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Cover; Title Page; Copyright; Contents; Preface; Chapter 1: Airline Crew Pairing Optimization; 1.1. Introduction; 1.2. Definition of the problem; 1.2.1. Constructing subnetworks; 1.2.2. Pairing costs; 1.2.3. Model; 1.2.4. Case without resource constraints; 1.3. Solution approaches; 1.3.1. Decomposition principles; 1.3.2. Column generation, master problem and subproblem; 1.3.3. Branching methods for finding integer solutions; 1.4. Solving the subproblem for column generation; 1.4.1. Mathematical formulation; 1.4.2. General principle of effective label generation
1.4.3. Case of one single resource: the bucket method1.4.4. Case of many resources: reduction of the resource space; 1.4.4.1. Reduction principle; 1.4.4.2. Approach based on the Lagrangian relaxation; 1.4.4.3. Approach based on the surrogate relaxation; 1.5. Conclusion; 1.6. Bibliography; Chapter 2: The Task Allocation Problem; 2.1. Presentation; 2.2. Definitions and modeling; 2.2.1. Definitions; 2.2.2. The processors; 2.2.3. Communications; 2.2.4. Tasks; 2.2.5. Allocation types; 2.2.5.1. Static allocation; 2.2.5.2. Dynamic allocation; 2.2.5.3. With or without pre-emption
2.2.5.4. Task duplication2.2.6. Allocation/scheduling; 2.2.7. Modeling; 2.2.7.1. Modeling costs; 2.2.7.2. Constraints; 2.2.7.3. Objectives of the allocation; 2.2.7.3.1. Minimizing the execution duration; 2.2.7.3.2. Minimizing the global execution and communication cost; 2.2.7.3.3. Load balancing; 2.3. Review of the main works; 2.3.1. Polynomial cases; 2.3.1.1. Two-processor cases; 2.3.1.2. Tree case; 2.3.1.3. Other structures; 2.3.1.4. Restrictions on the processors or the tasks; 2.3.1.5. Minmax objective; 2.3.2. Approximability; 2.3.3. Approximate solution; 2.3.3.1. Heterogenous processors
2.3.3.2. Homogenous processors2.3.4. Exact solution; 2.3.5. Independent tasks case; 2.4. A little-studied model; 2.4.1. Model; 2.4.2. A heuristic based on graphs; 2.4.2.1. Transformation of the problem; 2.4.2.2. Modeling; 2.4.2.3. Description of the heuristic; 2.5. Conclusion; 2.6. Bibliography; Chapter 3: A Comparison of Some Valid Inequality Generation Methods for General 0-1 Problems; 3.1. Introduction; 3.2. Presentation of the various techniques tested; 3.2.1. Exact separation with respect to a mixed relaxation; 3.2.2. Approximate separation using a heuristic
3.2.3. Restriction + separation + relaxed lifting (RSRL)3.2.4. Disjunctive programming and the lift and project procedure; 3.2.5. Reformulation-linearization technique (RLT); 3.3. Computational results; 3.3.1. Presentation of test problems; 3.3.2. Presentation of the results; 3.3.3. Discussion of the computational results; 3.4. Bibliography; Chapter 4: Production Planning; 4.1. Introduction; 4.2. Hierarchical planning; 4.3. Strategic planning and productive system design; 4.3.1. Group technology; 4.3.2. Locating equipment; 4.4. Tactical planning and inventory management
4.4.1. A linear programming model for medium-term planning
Record Nr. UNINA-9910808645303321
London, [England] ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2014
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Applications of combinatorial optimization [[electronic resource] /] / edited by Vangelis Th. Paschos
Applications of combinatorial optimization [[electronic resource] /] / edited by Vangelis Th. Paschos
Pubbl/distr/stampa London, : ISTE
Descrizione fisica 1 online resource (409 p.)
Disciplina 519.64
Altri autori (Persone) PaschosVangelis Th
Collana Combinatorial optimization
Soggetto topico Combinatorial optimization
ISBN 1-118-60028-2
1-118-60034-7
1-118-60011-8
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Cover; Applications of Combinatorial Optimization; Title Page; Copyright Page; Table of Contents; Preface; Chapter 1. Airline Crew Pairing Optimization; 1.1. Introduction; 1.2. Definition of the problem; 1.2.1. Constructing subnetworks; 1.2.2. Pairing costs; 1.2.3. Model; 1.2.4. Case without resource constraints; 1.3. Solution approaches; 1.3.1. Decomposition principles; 1.3.2. Column generation, master problem and subproblem; 1.3.3. Branching methods for finding integer solutions; 1.4. Solving the subproblem for column generation; 1.4.1. Mathematical formulation
1.4.2. General principle of effective label generation1.4.3. Case of one single resource: the bucket method; 1.4.4. Case of many resources: reduction of the resource space; 1.5. Conclusion; 1.6. Bibliography; Chapter 2. The Task Allocation Problem; 2.1. Presentation; 2.2. Definitions and modeling; 2.2.1. Definitions; 2.2.2. The processors; 2.2.3. Communications; 2.2.4. Tasks; 2.2.5. Allocation types; 2.2.6. Allocation/scheduling; 2.2.7. Modeling; 2.3. Review of the main works; 2.3.1. Polynomial cases; 2.3.2. Approximability; 2.3.3. Approximate solution; 2.3.4. Exact solution
2.3.5. Independent tasks case2.4. A little-studied model; 2.4.1. Model; 2.4.2. A heuristic based on graphs; 2.5. Conclusion; 2.6. Bibliography; Chapter 3. A Comparison of Some Valid Inequality Generation Methods for General 0-1 Problems; 3.1. Introduction; 3.2. Presentation of the various techniques tested; 3.2.1. Exact separation with respect to a mixed relaxation; 3.2.2. Approximate separation using a heuristic; 3.2.3. Restriction + separation + relaxed lifting (RSRL); 3.2.4. Disjunctive programming and the lift and project procedure; 3.2.5. Reformulation-linearization technique (RLT)
3.3. Computational results3.3.1. Presentation of test problems; 3.3.2. Presentation of the results; 3.3.3. Discussion of the computational results; 3.4. Bibliography; Chapter 4. Production Planning; 4.1. Introduction; 4.2. Hierarchical planning; 4.3. Strategic planning and productive system design; 4.3.1. Group technology; 4.3.2. Locating equipment; 4.4. Tactical planning and inventory management; 4.4.1. A linear programming model for medium-term planning; 4.4.2. Inventory management; 4.4.3. Wagner and Whitin model; 4.4.4. The economic order quantity model (EOQ)
4.4.5. The EOQ model with joint replenishments4.5. Operations planning and scheduling; 4.5.1. Tooling; 4.5.2. Robotic cells; 4.6. Conclusion and perspectives; 4.7. Bibliography; Chapter 5. Operations Research and Goods Transportation; 5.1. Introduction; 5.2. Goods transport systems; 5.3. Systems design; 5.3.1. Location with balancing requirements; 5.3.2. Multiproduct production-distribution; 5.3.3. Hub location; 5.4. Long-distance transport; 5.4.1. Service network design; 5.4.2. Static formulations; 5.4.3. Dynamic formulations; 5.4.4. Fleet management; 5.5. Vehicle routing problems
5.5.1. Definitions and complexity
Record Nr. UNINA-9910141601303321
London, : ISTE
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Applications of combinatorial optimization [[electronic resource] /] / edited by Vangelis Th. Paschos
Applications of combinatorial optimization [[electronic resource] /] / edited by Vangelis Th. Paschos
Edizione [1st ed.]
Pubbl/distr/stampa London, : ISTE
Descrizione fisica 1 online resource (409 p.)
Disciplina 519.64
Altri autori (Persone) PaschosVangelis Th
Collana Combinatorial optimization
Soggetto topico Combinatorial optimization
ISBN 1-118-60028-2
1-118-60034-7
1-118-60011-8
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Cover; Applications of Combinatorial Optimization; Title Page; Copyright Page; Table of Contents; Preface; Chapter 1. Airline Crew Pairing Optimization; 1.1. Introduction; 1.2. Definition of the problem; 1.2.1. Constructing subnetworks; 1.2.2. Pairing costs; 1.2.3. Model; 1.2.4. Case without resource constraints; 1.3. Solution approaches; 1.3.1. Decomposition principles; 1.3.2. Column generation, master problem and subproblem; 1.3.3. Branching methods for finding integer solutions; 1.4. Solving the subproblem for column generation; 1.4.1. Mathematical formulation
1.4.2. General principle of effective label generation1.4.3. Case of one single resource: the bucket method; 1.4.4. Case of many resources: reduction of the resource space; 1.5. Conclusion; 1.6. Bibliography; Chapter 2. The Task Allocation Problem; 2.1. Presentation; 2.2. Definitions and modeling; 2.2.1. Definitions; 2.2.2. The processors; 2.2.3. Communications; 2.2.4. Tasks; 2.2.5. Allocation types; 2.2.6. Allocation/scheduling; 2.2.7. Modeling; 2.3. Review of the main works; 2.3.1. Polynomial cases; 2.3.2. Approximability; 2.3.3. Approximate solution; 2.3.4. Exact solution
2.3.5. Independent tasks case2.4. A little-studied model; 2.4.1. Model; 2.4.2. A heuristic based on graphs; 2.5. Conclusion; 2.6. Bibliography; Chapter 3. A Comparison of Some Valid Inequality Generation Methods for General 0-1 Problems; 3.1. Introduction; 3.2. Presentation of the various techniques tested; 3.2.1. Exact separation with respect to a mixed relaxation; 3.2.2. Approximate separation using a heuristic; 3.2.3. Restriction + separation + relaxed lifting (RSRL); 3.2.4. Disjunctive programming and the lift and project procedure; 3.2.5. Reformulation-linearization technique (RLT)
3.3. Computational results3.3.1. Presentation of test problems; 3.3.2. Presentation of the results; 3.3.3. Discussion of the computational results; 3.4. Bibliography; Chapter 4. Production Planning; 4.1. Introduction; 4.2. Hierarchical planning; 4.3. Strategic planning and productive system design; 4.3.1. Group technology; 4.3.2. Locating equipment; 4.4. Tactical planning and inventory management; 4.4.1. A linear programming model for medium-term planning; 4.4.2. Inventory management; 4.4.3. Wagner and Whitin model; 4.4.4. The economic order quantity model (EOQ)
4.4.5. The EOQ model with joint replenishments4.5. Operations planning and scheduling; 4.5.1. Tooling; 4.5.2. Robotic cells; 4.6. Conclusion and perspectives; 4.7. Bibliography; Chapter 5. Operations Research and Goods Transportation; 5.1. Introduction; 5.2. Goods transport systems; 5.3. Systems design; 5.3.1. Location with balancing requirements; 5.3.2. Multiproduct production-distribution; 5.3.3. Hub location; 5.4. Long-distance transport; 5.4.1. Service network design; 5.4.2. Static formulations; 5.4.3. Dynamic formulations; 5.4.4. Fleet management; 5.5. Vehicle routing problems
5.5.1. Definitions and complexity
Record Nr. UNINA-9910809344503321
London, : ISTE
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Combinatorial Optimization [[electronic resource] ] : Theory and Algorithms / / by Bernhard Korte, Jens Vygen
Combinatorial Optimization [[electronic resource] ] : Theory and Algorithms / / by Bernhard Korte, Jens Vygen
Autore Korte Bernhard
Edizione [6th ed. 2018.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2018
Descrizione fisica 1 online resource (XXI, 698 p. 78 illus.)
Disciplina 519.64
Collana Algorithms and Combinatorics
Soggetto topico Combinatorics
Calculus of variations
Computer science—Mathematics
Operations research
Decision making
Calculus of Variations and Optimal Control; Optimization
Mathematics of Computing
Operations Research/Decision Theory
ISBN 3-662-56039-9
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto 1 Introduction -- 2 Graphs -- 3 Linear Programming -- 4 Linear Programming Algorithms -- 5 Integer Programming -- 6 Spanning Trees and Arborescences -- 7 Shortest Paths -- 8 Network Flows -- 9 Minimum Cost Flows -- 10 Maximum Matchings -- 11 Weighted Matching -- 12 b-Matchings and T -Joins -- 13 Matroids -- 14 Generalizations of Matroids -- 15 NP-Completeness -- 16 Approximation Algorithms -- 17 The Knapsack Problem -- 18 Bin-Packing -- 19 Multicommodity Flows and Edge-Disjoint Paths -- 20 Network Design Problems -- 21 The Traveling Salesman Problem -- 22 Facility Location -- Indices.
Record Nr. UNINA-9910300110103321
Korte Bernhard  
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2018
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Combinatorial optimization : 7th International Symposium, ISCO 2022, virtual event, May 18-20, 2022, revised selected papers / / Ivana Ljubic [and three others] editors
Combinatorial optimization : 7th International Symposium, ISCO 2022, virtual event, May 18-20, 2022, revised selected papers / / Ivana Ljubic [and three others] editors
Pubbl/distr/stampa Cham, Switzerland : , : Springer, , [2022]
Descrizione fisica 1 online resource (340 pages)
Disciplina 519.64
Collana Lecture notes in computer science
Soggetto topico Combinatorial optimization
ISBN 3-031-18530-7
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Intro -- 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.
Record Nr. UNINA-9910631085503321
Cham, Switzerland : , : Springer, , [2022]
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Combinatorial optimization : 7th International Symposium, ISCO 2022, virtual event, May 18-20, 2022, revised selected papers / / Ivana Ljubic [and three others] editors
Combinatorial optimization : 7th International Symposium, ISCO 2022, virtual event, May 18-20, 2022, revised selected papers / / Ivana Ljubic [and three others] editors
Pubbl/distr/stampa Cham, Switzerland : , : Springer, , [2022]
Descrizione fisica 1 online resource (340 pages)
Disciplina 519.64
Collana Lecture notes in computer science
Soggetto topico Combinatorial optimization
ISBN 3-031-18530-7
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Intro -- 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.
Record Nr. UNISA-996500062603316
Cham, Switzerland : , : Springer, , [2022]
Materiale a stampa
Lo trovi qui: Univ. di Salerno
Opac: Controlla la disponibilità qui
Combinatorial optimization [[electronic resource] ] : methods and applications / / edited by Vašek Chvátal
Combinatorial optimization [[electronic resource] ] : methods and applications / / edited by Vašek Chvátal
Pubbl/distr/stampa Washington, D.C., : IOS Press, 2011
Descrizione fisica 1 online resource (240 p.)
Disciplina 519.64
658.5
Altri autori (Persone) ChvátalVašek
Collana NATO science for peace and security series. Sub-series D, Information and communication security
Soggetto topico Combinatorial optimization
Soggetto genere / forma Electronic books.
ISBN 6613289620
1-283-28962-8
9786613289629
1-60750-718-8
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Title; Preface; Acknowledgments; The NATO Advanced Study Institute; Contents; Mixed Integer Rounding Cuts and Master Group Polyhedra; Combinatorial Optimization in VLSI Design; Facility Location: Discrete Models and Local Search Methods; Discrete Convexity and Its Applications; Branching on Split Disjunctions; Convex Discrete Optimization
Record Nr. UNINA-9910457589203321
Washington, D.C., : IOS Press, 2011
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Combinatorial optimization [[electronic resource] ] : methods and applications / / edited by Vašek Chvátal
Combinatorial optimization [[electronic resource] ] : methods and applications / / edited by Vašek Chvátal
Pubbl/distr/stampa Washington, D.C., : IOS Press, 2011
Descrizione fisica 1 online resource (240 p.)
Disciplina 519.64
658.5
Altri autori (Persone) ChvátalVašek
Collana NATO science for peace and security series. Sub-series D, Information and communication security
Soggetto topico Combinatorial optimization
ISBN 6613289620
1-283-28962-8
9786613289629
1-60750-718-8
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Title; Preface; Acknowledgments; The NATO Advanced Study Institute; Contents; Mixed Integer Rounding Cuts and Master Group Polyhedra; Combinatorial Optimization in VLSI Design; Facility Location: Discrete Models and Local Search Methods; Discrete Convexity and Its Applications; Branching on Split Disjunctions; Convex Discrete Optimization
Record Nr. UNINA-9910781754503321
Washington, D.C., : IOS Press, 2011
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Combinatorial optimization [[electronic resource] ] : methods and applications / / edited by Vašek Chvátal
Combinatorial optimization [[electronic resource] ] : methods and applications / / edited by Vašek Chvátal
Pubbl/distr/stampa Washington, D.C., : IOS Press, 2011
Descrizione fisica 1 online resource (240 p.)
Disciplina 519.64
658.5
Altri autori (Persone) ChvátalVašek
Collana NATO science for peace and security series. Sub-series D, Information and communication security
Soggetto topico Combinatorial optimization
ISBN 6613289620
1-283-28962-8
9786613289629
1-60750-718-8
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Title; Preface; Acknowledgments; The NATO Advanced Study Institute; Contents; Mixed Integer Rounding Cuts and Master Group Polyhedra; Combinatorial Optimization in VLSI Design; Facility Location: Discrete Models and Local Search Methods; Discrete Convexity and Its Applications; Branching on Split Disjunctions; Convex Discrete Optimization
Record Nr. UNINA-9910806201503321
Washington, D.C., : IOS Press, 2011
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui