Separation algorithms for cutting planes based on mixed integer row relaxations : implementation and evaluation in the context of mixed integer programming solver software / Philipp M. Christophel. 2009
Inhalt
- Introduction
- MIP Theory
- Mixed Integer Programming Problems
- Formulations
- Relaxations and Bounds
- Valid Inequalities and Separation
- Mixed Integer Rounding Inequalities
- Mixing Inequalities
- Lifting Valid Inequalities
- The Branch-and-cut Algorithm
- MIP Solver Software
- Separation Algorithms
- The Flow Cover Cut Separation Algorithm
- The Aggregated cMIR Cut Separation Algorithm
- The Flow Path Cut Separation Algorithm
- Implementations, Algorithmic Improvements, and New Algorithms
- Objectives
- Framework
- Overview
- Data Structures
- Accuracy
- Variable Bounds and Row Types
- Aggregation and Path-finding
- Bound Substitution
- The Flow Cover Cut Generator
- The cMIR Cut Generator
- The Flow Path Cut Generator
- The Path Mixing Cut Generators
- Evaluation
- Evaluation Methods
- Empirical Analysis of Algorithms
- Problem Instances
- Computational Experiments and Performance Measures
- Presentation
- The Test Environment
- Accuracy Evaluation
- Evaluation of the Flow Cover Cut Generator
- Implementation Details
- Comparison to the Previous Flow Cover Cut Generator
- Comparison to Published Results
- Evaluation of the cMIR Cut Generator
- Implementation Details and Algorithmic Improvements
- Comparison to the Previous cMIR Cut Generator
- Comparison to Published Results
- Comparison between the Flow Cover and the cMIR Cut Generator
- Evaluation of the Path-based Cut Generators
- Implementation Details of the Flow Path Cut Generator
- Comparison of Path-based Cut Generators
- Evaluation of the Need for a Path-based Cut Generator
- Comparison of Cut Configurations
- Conclusions and Outlook
- Notation
- Example Configuration Files
- Test Sets
- Test Results