Paschos V.Th. (ed.) Applications of Combinatorial Optimization

London: Wiley-ISTE, 2014. - 449p.Combinatorial optimization is a multidisciplinary scientific area, lying in the interface of three major scientific domains: mathematics, theoretical computer science and management. The three volumes of the Combinatorial Optimization series aim to cover a wide range of topics in this area. These topics also deal with fundamental notions and approaches as with several classical applications of combinatorial optimization.
Concepts of Combinatorial Optimization, is divided into three parts:
- On the complexity of combinatorial optimization problems, presenting basics about worst-case and randomized complexity;
- Classical solution methods, presenting the two most-known methods for solving hard combinatorial optimization problems, that are Branch-and-Bound and Dynamic Programming;
- Elements from mathematical programming, presenting fundamentals from mathematical programming based methods that are in the heart of Operations Research since the origins of this fieldAirline Crew Pairing OptimizationDefinition of the problem
Constructing subnetworks
Pairing costs
Model
Case without resource constraints
Solution approaches
Decomposition principles
Column generation, master problem and subproblem
Branching methods for finding integer solutions
Solving the subproblem for column generation
Mathematical formulation
General principle of effective label generation Case of one single resource: the bucket method Case of many resources: reduction of the resource space
Reduction principle
Approach based on the Lagrangian relaxation
Approach based on the surrogate relaxationThe Task Allocation ProblemPresentation
Definitions and modeling
Definitions
The processors
Communications
Tasks
Allocation types
Static allocation
Dynamic allocation
With or without pre-emption Task duplication Allocation/scheduling
Modeling
Modeling costs
Constraints
Objectives of the allocation
Minimizing the execution duration
Minimizing the global execution and communication cost
Load balancing
Review of the main works
Polynomial cases
Two-processor cases
Tree case
Other structures
Restrictions on the processors or the tasks
Minmax objective
Approximability
Approximate solution
Heterogenous processors Homogenous processors Exact solution
Independent tasks case
A little-studied model
Model
A heuristic based on graphs
Transformation of the problem
Modeling
Description of the heuristicA Comparison of Some Valid Inequality Generation Methods for General - ProblemsPresentation of the various techniques tested
Exact separation with respect to a mixed relaxation
Approximate separation using a heuristic Restriction + separation + relaxed lifting (RSRL) Disjunctive programming and the lift and project procedure
Reformulation-linearization technique (RLT)
Computational results
Presentation of test problems
Presentation of the results
Discussion of the computational resultsProduction PlanningHierarchical planning
Strategic planning and productive system design
Group technology
Locating equipment
Tactical planning and inventory management