GoogleOR-Tools （六）装箱问题BinPacking
本⽂参考Google OR-Tools介绍OR-Tools的使⽤⽅法。
的描述是要将⼀组给定尺⼨的物品放置到具有固定容量的容器中，⼀般情况下由于容器有容量限制，不可能放⼊所有物品，那么装箱问题的⽬标是要找到限定约束下使得总价值最⼤或总花费最⼩的装箱⽅法。根据我们具体的⽬标情况，装箱问题⼜可分为两类：
背包问题(Knapsack problem)，容器数量是固定的，每个容器有⾃⼰的最⼤容量，⽽需要分配的物件有各⾃的价值，我们的⽬标是让装⼊容器的物体的总价值最⼤，并不要求所有物体都装⼊；
Bin-packing问题，容器容量是相同的，但是数量不固定，我们的⽬标是⽤最少的容器来存放所有的物件。
OR-Tools针对典型的单背包问题提供了专⽤的接⼝，对于更⼀般的多背包问题和-packing问题则需要使⽤通⽤的整数规划接⼝来计算。这篇⽂章⾥我就参考官⽅教程演⽰⽤OR-Tools对单背包问题、多背包问题和Bin-Packing问题进⾏建模。
1 单背包问题
如果背包问题中只有⼀个背包，那么就是单背包问题，⼀般也成为0-1背包问题，因为它可以⽤下⾯的⽅程式来描述问题：⽤0-1变量表⽰第个物件是否放⼊背包，表⽰物件的价值，则表⽰物件的重量，则是背包的最⼤承重，那么整个问题可表⽰为：maximize subject to i=1∑n vi x i i=1∑n wi x i ≤W xi ∈{0,1}
当然实际⽣活中可能限制背包存放物体数量的不仅是重量，还有体积等属性，因此上⾯的定义更严格的来说应该是单维单背包问题，如果有多维限定，那么在每⼀维存放物体的总量都不能超过背包的限定值。
我们新建⼀个 Core控制台应⽤，⾃定义⼀个单背包问题的数据:
holmes
OR-Tools提供了⼀个KnapsackSolver来专门处理单背包问题，我们定义这个KnapsackSolver对象，并且指定使⽤分⽀界定算法然后就可以初始化KnapsackSolver对象并求解了
Solve()⽅法的返回值就是算法的最终⽬标值，⽽如果要知道那些物件被放置，则需要调⽤BestSolutionContains()⽅法查看。
x i i v i i w i W //values[i], the value of item i long [] values = { 360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147, 78, 256, 63, 17, 120, 164, 432, 35,
92, 110, 22, 42, 50, 323, 514, 28, 87, 73, 78, 15, 26, 78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312 }; //weights[i,j], the weight of weights[i][j] long [,] weights = { { 7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42, 9, 0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71, 3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13 } }; long [] capacities = { 850 };
1
2
3
4
5
bcs6
7
8
until you9
10
克格勃特工11
12
13
14
15
16
17KnapsackSolver solver = new KnapsackSolver ( KnapsackSolver .SolverType .KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER , "KnapsackExample");
1
2
3 solver .Init (values , weights , capacities ); long computedValue = solver .Solve ();
1
2
完整的程序 Console .WriteLine ("Optimal Value = " + computedValue ); string lectItems = $"Selected item indexs : "; for (int i = 0; i < values .Length ; i ++) { if (solver .BestSolutionContains (i )) { lectItems += $"{i}({values[i]}), "; } } Console .WriteLine (lectItems );
1
2prado
3
4
htl
5
6
7
8
9
10using System ;using Google .OrTools .Algorithms ;namespace SingleKnapsackProblem { class Program { static void Main (string [] args ) { //Create a knapsack solver, u Branch And Bound algorithm KnapsackSolver solver = new KnapsackSolver ( KnapsackSolver .SolverType .KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER , "KnapsackExample"); //values[i], the value of item i long [] values = { 360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147, 78, 256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28, 87, 73, 78, 15, 26, 78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312 }; //weights[i,j], the weight of weights[i][j] long [,] weights = { { 7, 0, 30, 22, 80, 94, 11, 81, 70, 64,
59, 18, 0, 36, 3, 8, 15, 42, 9, 0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71, 3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13 } }; long [] capacities = { 850 }; solver .Init (values , weights , capacities ); long computedValue = solver .Solve (); Console .WriteLine ("Optimal Value = " + computedValue ); string lectItems = $"Selected item indexs : "; for (int i = 0; i < values .Length ; i ++) { if (solver .BestSolutionContains (i )) { lectItems += $"{i}({values[i]}), "; } } Console .WriteLine (lectItems ); } }}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
brilliant22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43孤儿院英文
44
45
46
47
2 多背包问题
把单个背包扩展到多个背包，就是多背包问题，对于多背包问题，我们可以采⽤下⾯的定义⽅式：
给出个物件和个背包()，并且按如下定义(仍然只是单维):
vj ：物件j的价值wj ：物件j的重量ci ：第i个背包的容量
要让每个背包不超过容量限制的情况下最⼤化放置的物件的价值总量，即:
其中是0-1变量，表⽰物件是否分配到背包中。
对于多背包问题，OR-Tools没有提供直接的接⼝，不过从它的建模⽅程来看，这是⼀很典型的整数规划问题，因此我们可以例⽤OR-Tools 的整数规划接⼝来建模和计算。
我们先⾃定义⼀个问题的数据源，假设有15个物件和5个背包，每个背包的最⼤承重都是100
新建⼀个整数规划求解对象，这⾥指定内部连接CBC求解器
n m m ≤n maximize
subject to v x i =1∑j =1∑j ij w x ≤c ,i ∈M ={1,...m }j =1∑
n j ij i x ≤1,j ∈N ={1,...n }
i =1∑m ij x ∈{0,1}
ij x ij j i class DataModel { public double [] Weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36}; public double [] Values = {10, 30, 25, 50, 35, 30, 1
5, 40, 30, 35, 45, 10, 20, 30, 25}; public double [] BinCapacities = { 100, 100, 100, 100, 100 }; private int numItems ; public int NumItems { get { numItems = Weights .Length ; return numItems ; } t { numItems = value ; } } public int NumBins = 5; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 // Create the linear solver with the CBC backend. Solver solver = Solver .CreateSolver ("SimpleMipProgram", "CBC_MIXED_INTEGER_PROGRAMMING");
1
2
然后定义求解变量，即个0-1变量
接着是两个，约束⼀是对⼀个物件，最多只会被分配在⼀个背包；约束⼆是每个背包内的物件的重量和不会超过限制
最后就可以定义⽬标并求解了
完整的代码
i ×j // Create variables, x[i][j]=1 means item i is packed in bin j Variable [,] x = new Vari
able [data .NumItems ,data .NumBins ]; for (int i = 0; i < data .NumItems ; i ++) { for (int j = 0; j < data .NumBins ; j ++) { x [i ,j ] = solver .MakeIntVar (0, 1, String .Format ("x_{0}_{1}", i , j )); } }
1
2
3
4
5
6
7
8
9 //Item i can't be packed in more than one bins for (int i = 0; i < data .NumItems ; ++i )
{ LinearExpr sum =new LinearExpr (); for (int j = 0; j < data .NumBins ; ++j ) { sum += x [i ,j ]; } solver .Add (sum <= 1.0); } //The amount packed in each bin cannot exceed its capacity for (int j = 0; j < data .NumBins ; ++j ) { LinearExpr Weight =new LinearExpr (); for (int i = 0; i < data .NumItems ; ++i ) { Weight += data .Weights [i ] * x [i ,j ]; } solver .Add (Weight <= data .BinCapacities [j ]); }
英语翻译软件下载
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 //Objective LinearExpr totalValue =new LinearExpr (); for (int i = 0; i < data .NumItems ; ++i ) { for (int j = 0; j < data .NumBins ; ++j ) { totalValue += data .Values [i ] * x [i ,j ]; } } solver .Maximize (totalValue ); //Solve it Solver .ResultStatus resultStatus = solver .Solve ();
1
2
3
4
5
6
7
8
9
10
11
12
13using System ;using Google .OrTools .LinearSolver ;namespace MultipleKnapsackProblem { class Program { class DataModelabbey
1
2
3
4
5
6
7
8
class DataModel { public double [] Weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36}; public double [] Values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25}; public double [] BinCapacities = { 100, 100, 100, 100, 100 }; private int numItems ; public int NumItems { get { numItems = Weights .Length ; return numItems ; } t { numItems = value ; } } public int NumBins = 5; } static void Main (string [] args ) { DataModel data = new DataModel (); // Create the linear solver with the CBC backend. Solver solver = Solver .CreateSolver ("SimpleMipProgram", "CBC_MIXED_INTEGER_PROGRAMMING"); // Create variables, x[i][j]=1 means item i is packed in bin j Variable [,] x = new Variable [data .NumItems ,data .NumBins ]; for (int i = 0; i < data .NumItems ; i ++) { for (int j = 0; j < data .NumBins ; j ++) { x [i ,j ] = solver .MakeIntVar (0, 1, String .Format ("x_{0}_{1}", i , j )); } }
//Item i can't be packed in more than one bins for (int i = 0; i < data .NumItems ; ++i ) { LinearExpr sum =new LinearExpr (); for (int j = 0; j < data .NumBins ; ++j ) { sum += x [i ,j ]; } solver .Add (sum <= 1.0); } //The amount packed in each bin cannot exceed its capacity for (int j = 0; j < data .NumBins ; ++j ) { LinearExpr Weight =new LinearExpr (); for (int i = 0; i < data .NumItems ; ++i ) { Weight += data .Weights [i ] * x [i ,j ]; } solver .Add (Weight <= data .BinCapacities [j ]); } //Objective LinearExpr totalValue =new LinearExpr (); for (int i = 0; i < data .NumItems ; ++i ) { for (int j = 0; j < data .NumBins ; ++j ) { totalValue += data .Values [i ] * x [i ,j ]; }8910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
