Introduction .................................................... 1
1 A Branch-and-Cut Method for the Strip Packing Problem ........ 5
1.1 Introduction ............................................ 5
1.2 Strong valid inequalities and facets .................... 9
1.3 The branch-and-cut algorithm ........................... 28
1.4 Valid linear inequalities .............................. 31
1.5 Valid nonlinear inequalities and linearization ......... 34
1.6 Numerical study ........................................ 37
1.7 Conclusions ............................................ 37
1.8 Acknowledgments ........................................ 38
2 Branch-and-Price Methods for the ID Contiguous Bin Packing
Problem ..................................................... 41
2.1 Introduction ........................................... 41
2.2 The branch-and-price algorithms ........................ 46
2.3 Subcolumns breaking the C1P ............................ 50
2.4 Subcolumns potentially breaking the C1P ................ 57
2.5 Numerical study ........................................ 61
2.6 Conclusions ............................................ 62
2.7 Acknowledgments ........................................ 62
3 Constraint Programming Approaches for Orthogonal Packing .... 65
3.1 Introduction ........................................... 65
3.2 An overview of the algorithm of Clautiaux et al ........ 68
3.3 Minor modifications .................................... 70
3.4 New branching strategies ............................... 72
3.5 Advanced constraint propagation ........................ 83
3.6 Numerical study ........................................ 97
3.7 Conclusions ........................................... 103
3.8 Acknowledgments ....................................... 103
4 Constraint Programming Approaches for 3D Orthogonal
Packing .................................................... 107
4.1 Introduction .......................................... 107
4.2 Modification of the basic algorithm ................... 110
4.3 Minor modifications ................................... 110
4.4 New branching strategies .............................. 112
4.5 Advanced constraint propagation ....................... 116
4.6 Numerical study ....................................... 123
4.7 Conclusions ........................................... 124
4.8 Acknowledgments ....................................... 125
Summary and Outlook ........................................... 131
Bibliography .................................................. 133
List of Tables ................................................ 139
List of Figures ............................................... 141
| 
