FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Branch-and-Price for the Generalized Assignment Problem

Description
The model implements a branch-and-price algorithm that solves a disaggregated formulation of the Generalized Assignment Problem (GAP) where columns represent feasible assignments of batches to machines. Column generation is applied at every node of the branch-and-bound tree. The branching algorithm is completely implemented in Mosel, and the optimizer is used only to solve the LP relaxation at each node.

The model implementation shows the following features of Mosel:
  • user type definitions for data structures (records)
  • concurrent solving of a set of subproblems coordinated via events and exchanging data (including data with user type) via shared memory
Data instances for this problem are generated by executing the model genGapDataD.mos. The branch-and-price algorithm is started by running the master model GAPbp3.mos. The master model triggers the solving of the submodels (file GAPsubDP.mos). The present implementation of branch-and-price can be extended by the definition of a heuristic that will be called at every node of the branching tree (subroutine 'heuristic') and it can also be configured to use other branching variable choice strategies.


Source Files

Data Files





Dtestx5_30_1.dat

NM: 5
NP: 30
DUR: [(1 1) 42 80 5 32 68 6 49 26 41 28 22 84 2 38 65 12 63 28 33 82 42 90 50 17
 74 43 40 86 78 37 (2 1) 54 84 64 33 64 69 77 28 13 96 77 100 26 37 45 28 80
 95 87 2 31 23 96 38 100 26 73 40 28 74 (3 1) 26 2 48 92 7 89 38 88 40 5 33
 36 85 36 24 76 59 61 10 90 29 59 65 87 29 74 60 93 25 89 (4 1) 72 58 46 24
 34 64 28 7 56 50 79 91 4 65 94 42 68 62 55 49 55 59 59 86 10 40 58 6 17 48
 (5 1) 30 76 43 40 91 94 23 58 92 14 97 92 46 28 17 50 88 91 30 55 88 9 68
 96 5 5 31 70 86 64]
CAP: [(1) 218 270 249 238 268]
PROFIT: [(1 1) 56 87 23 40 80 12 57 33 54 47 29 102 1 47 74 24 72 37 40 83 50 90 62
 31 73 51 55 97 81 54 (2 1) 63 101 74 49 75 86 83 33 20 105 93 119 37 39 45
 34 92 102 96 6 43 26 98 41 101 43 86 41 28 81 (3 1) 45 14 64 94 21 106 47
 99 39 17 39 50 100 35 36 88 61 74 29 98 40 70 68 101 39 92 67 111 27 91 (4
 1) 77 58 49 23 34 64 32 26 62 68 93 108 6 79 99 52 72 69 68 66 60 75 61 99
 11 45 68 17 16 64 (5 1) 30 91 61 46 106 96 37 57 110 22 102 100 57 46 29 65
 87 96 34 66 102 22 73 96 20 16 45 80 94 67]

Back to examples browserPrevious exampleNext example