Discussion of the graph partitioning formulations

For more info about our services contact : help@bestpfe.com

Table of contents

1 Introduction 
1.1 Research context
1.1.1 Graph partitioning problem under knapsack constraints (GPKC)
1.1.2 Graph partitioning under capacity constraints (GPCC)
1.2 Graph partitioning problem under set constraints
1.3 Motivation and Contributions
2 Literature review 
2.1 Fundamental concepts
2.1.1 Graph theory
2.1.2 Graph partitioning and multicuts
2.1.3 Problems, algorithms and complexity
2.2 Overview of models and solution methods
2.2.1 Node-Node formulations
2.2.2 Node-Cluster formulation
2.2.3 Approaches of mixing Node-Node and Node-Cluster models .
2.2.4 Semi-denite formulation
2.2.5 Discussion of the graph partitioning formulations
3 Improved compact formulations for sparse graphs 
3.1 Basic 0/1 programming model for GPP-SC
3.2 Improved 0/1 programming model for GPP-SC
3.3 Extension
3.4 Computational experiments
3.4.1 Experimental results for GPKC
3.4.2 Experimental results for GPCC
3.5 Conclusions
4 Cutting plane approach for large size graph 
4.1 Preliminary: Node-Node formulation for GPKC
4.2 A m-variable formulation for GPKC and its solution via cutting-planes
4.2.1 A m-variables formulation for GPKC
4.2.2 Solving the separation subproblem via shortest path computations
4.2.3 Ecient implementation of the cutting plane algorithm .
4.3 Ecient computation of upper bounds: heuristic solutions
4.3.1 Building feasible partitions: upper rounding procedure (UR) .
4.3.2 Building feasible partitions: progressive aggregation procedure (PA)
4.4 Numerical experiments
4.4.1 Experiments for the cycle model using the cutting plane algorithms
4.4.2 Experiments for the cycle model using ecient implementation of the cutting plane algorithm
4.4.3 GPKC upper bound computation
4.4.4 Convergence prole of the cutting plane algorithm
4.5 Conclusion
5 Stochastic graph partitioning 
5.1 Stochastic programming
5.1.1 Optimization under uncertainty, an overview
5.1.2 Chance constrained programming
5.1.3 Convexity studies
5.1.4 Stochastic graph partitioning
5.1.5 Stochastic graph partitioning under knapsack constraint formulation
5.2 Partitioning process networks
5.3 Second order cone formulation
5.4 Quadratic 0-1 reformulation
5.4.1 Classical linearization technique
5.4.2 Sherali-Smith’s linearization technique
5.5 Computational results
5.6 Conclusion
6 Conclusions and perspectives 
6.1 Conclusions
6.2 Perspectives