装箱问题(Bin Packing Problem)
装箱问题即搬家公司问题。一个搬家公司有无限多的箱子，每个箱子的承重上限为W，当搬家公司进入一个房间时，所有物品都必须被装入箱子，每个物品的重量为wi (i=1,...,m)，规划装箱方式，使得使用的箱子最少。此文及所有本博克中的博文均为原创,本博克不转发他人博文，特此声明。
实例
一个海运公司有若干货轮, 一个货轮的最大载重量4000吨, 客户货物的重量是 1020T, 1930T, 3575T, 2861T, 4221T, 1541T, 2348T, and 1170T, 问如何分配货物可以使总计需求的货轮数量(航次) 最小。
建模
假设搬家公司带来n个箱子，且n个箱子足够装入所有物品。设0-1变量x[i][j]表示第j个物品是否被安排装入第i个箱子，0表示不装入，1表示装入。根据题意，任何物品必须被装入某个箱子中，于是有约束：
sum{i=1,...,n} x[i][j] = 1 | j=1,...,m // (1)
如果箱子i有任何物品被装入，则说该箱子被打开，并设0-1变量y[i]表示箱子i是否被打开（0-表示不打开，1-表示打开）。显然目标是极小化打开箱子的数目，即：
min sum{i=1,...,n} y[i] //(2)
装入箱子的物品重量和不能超过该箱子的承重，即：
sum{j=1,...,m} x[i][j] <= W*y[i] | i=1,...,n //(3)
上式表示当聚焦第i个箱子时，如果y[i]=0则任何x[i][j]都必须为0，亦即如果第i个箱子没有被打开，则没有物品可以装入该箱子。反之，如果y[i]=1，则装入该箱子的物品的重量和必须小于箱子的最大承重W。
综合（1）-（3）, 装箱问题模型的核心部分如下：
//-------------------------------------------------------
min sum{i=1,...,n} y[i] //(2)
subject to
sum{i=1,...,n} x[i][j] = 1 | j=1,...,m // (1)
sum{j=1,...,m} x[i][j]w[i] <= W*y[i] | i=1,...,n //(3)
//-------------------------------------------------------
添加where段对模型中常量符号和变量符号的说明
//-------------------------------------------------------
where
m,n are integers
W is a number
w is a set
x[i][j] is a variable of binary|i=1,...,n;j=1,...,m
y[i] is a variable of binary|i=1,...,n
//-------------------------------------------------------
E、添加数据段
//-------------------------------------------------------
data
W=4000
w={1020， 1930，3575，2861，4221，1541，2348, 1170}
data_relation
m=_$(w) // <-- _$(w) 函数给出集合w中的元素数。
n=m/2 // <-- 预备箱子数取为物体数的一半。
//-------------------------------------------------------
上面模型中，物品个数由求w中的元素数给出。预备箱子数给为物体数的一半。预备箱子数必须大于实际最优箱子数，否则问题无解。
CPLEX求解
求解模型，在Leapms环境中, 首先使用load命令调入并解析模型, 而后使用"cplex" 命令调用IBMC PLEX求解器完成求解.
Leapms>load Current directory is "ROOT". ......... binpacking.leap ......... lease input the filename:binpacking =============================================================== : //------------------------------------------------------- : : min sum{i=1,...,n} y[i] //(2) : subject to : sum{i=1,...,n} x[i][j] = 1 | j=1,...,m // (1) : sum{j=1,...,m} x[i][j]w[i] <= W*y[i] | i=1,...,n //(3) : where : m,n are integers : W is a number 0: w is a set 1: x[i][j] is a variable of binary|i=1,...,n;j=1,...,m 2: y[i] is a variable of binary|i=1,...,n 3: data 4: W=4000 5: w={1020M, 1930M, 3575M, 2861M, 4221M, 1541M, 2348M, 1170} 6: //w={1020， 1930，3575，2861，4221，1541，2348, 1170} 7: data_relation 8: m=_$(w) 9: n=m 0: //------------------------------------------------------- =============================================================== >end of the file. arsing model: D R V O C S End. ................................. umber of variables=72 umber of constraints=16 ................................. Leapms>cplex You must have licience for Ilo Cplex, otherwise you will violate corresponding copyrights, continue(Y/N)？ 你必须有Ilo Cplex软件的授权才能使用此功能，否则会侵犯相应版权， 是否继续(Y/N)？y Tried aggregator 1 time. MIP Presolve eliminated 1 rows and 9 columns. MIP Presolve modified 61 coefficients. Reduced MIP has 15 rows, 63 columns, and 119 nonzeros. Reduced MIP has 63 binaries, 0 generals, 0 SOSs, and 0 indicators. Presolve time = 0.02 sec. (0.14 ticks) Found incumbent of value 7.000000 after 0.08 sec. (0.32 ticks) Probing time = 0.00 sec. (0.06 ticks) Tried aggregator 1 time. Reduced MIP has 15 rows, 63 columns, and 119 nonzeros. Reduced MIP has 63 binaries, 0 generals, 0 SOSs, and 0 indicators. Presolve time = 0.02 sec. (0.08 ticks) Probing time = 0.00 sec. (0.06 ticks) Clique table members: 43. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 4 threads. Root relaxation solution time = 0.00 sec. (0.05 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap * 0+ 0 7.0000 0.0000 100.00% * 0+ 0 4.0000 0.0000 100.00% 0 0 2.2824 5 4.0000 2.2824 8 42.94% * 0+ 0 3.0000 2.2824 23.92% 0 0 cutoff 3.0000 2.2824 8 23.92% Elapsed time = 0.20 sec. (0.72 ticks, tree = 0.00 MB, solutions = 3) Root node processing (before b&c): Real time = 0.22 sec. (0.72 ticks) Parallel b&c, 4 threads: Real time = 0.00 sec. (0.00 ticks) Sync time (average) = 0.00 sec. Wait time (average) = 0.00 sec. ------------ Total (root+branch&cut) = 0.22 sec. (0.72 ticks) Solution status = Optimal Solution value = 3 x1_1=1 x1_5=1 x1_8=1 x6_2=1 x6_7=1 x8_3=1 x8_4=1 x8_6=1 y1=1 y6=1 y8=1