B
Ộ GIÁO DỤC
& ĐÀO T
ẠO
VI
ỆN KH
& CN VI
ỆT NAM
VI
ỆN CÔNG NGHỆ THÔNG TIN
PHAN TH
Ị HOÀI PHƯƠNG
M
ỘT
GI
ẢI THUẬT DI TRUYỀN
GI
ẢI BÀI TOÁN CẮT VẬT TƯ MỘT CHIỀU
V
ỚI NHIỀU KÍCH CỠ VẬT LIỆU THÔ
LUẬN ÁN TIẾN SĨ TOÁN HỌC
Hà N
ội
– 2011
B
Ộ GIÁO DỤC
& ĐÀO T
ẠO
VI
ỆN KH & CN VIỆT NAM
VI

Tôi xin cam đoan đây là công tr
ình nghiên c
ứu của riêng tôi. Các kết quả được viết
chung v
ới các tác giả khác đã được sự nhất trí của đồng tác giả khi đưa vào luận
án.
Các k
ết quả nêu trong luận án là trung thực và ch
ưa từng được ai công bố trong
b
ất kỳ
công trình nào.
Tác gi
ả
Phan Th
ị Hoài Phương
L
ỜI CẢM
ƠN
Lu
ận án
được thực hiện và hoàn thành dưới sự hướng dẫn của PGS.TS Lương Chi
Mai và TS. Nguy
ễn Văn Hùng. Tr
ước hết, tôi xin bày tỏ lòng biết ơn sâu s
ắc đến cô
Lương Chi Mai và th
ầy Nguyễn V
ăn Hùng, những ng
ười thầy

ối cùng tôi xin
dành t
ặng
lu
ận án này cho những ng
ười thân yêu: bố mẹ, chồng,
con gái và con trai c
ủa tôi như muốn nói một lời cảm
ơn chân thành nh
ất vì sự giúp
đ
ỡ,
s
ự
động vi
ên không gi
ới hạn
đ
ối với tôi.
H
ọ chính là n
ơi khơi nguồn và cũng là
đích hư
ớng tới trong học tập và nghiên cứu của tôi.
i
M
ỤC LỤC
M
Ở
ĐẦU

2.4. K
ết quả tính toán
40
2.5. K
ết luận
50
Chương 3. H
Ệ THỐNG
ĐA TÁC TỬ GMAS
-OneDCSP_M GI
ẢI BÀI TOÁN
OneDCSP_M 52
3.1. Yêu c
ầu của hệ thống GMAS
-OneDCSP_M 54
3.2. Thiết kế hệ thống GMAS-OneDCSP_M 55
3.2.1. Ki
ến trúc hệ thống GMAS
-OneDCSP_M 55
3.2.2. Thi
ết kế chi tiết hệ thống GMAS
-OneDCSP_M 58
3.3. Đánh giá tính hi
ệu quả của hệ thống GMAS
-OneDCSP_M 65
3.4. K
ết luận
67
K
ẾT LUẬN VÀ H

Subproblem – pricing problem
Đi
ểm cực
Extreme point
Gi
ải thuật di truyền
Genetic Algorithm – GA
Giá suy gi
ảm
Reduced cost
L
ập
trình ti
ến hóa
Evolutionary Programming-EP
N
ới lỏng tuyến tính liên tục
Linear continuous relaxation
N
ới lỏng tuyến tính liên tục mạnh
Strong linear continuous relaxation
N
ới lỏng tuyến tính liên tục yếu
Weak linear continuous relaxation
Phương pháp nhánh c
ận
Branch and Bound – B&B
Phương pháp phân nhánh và đ
ịnh giá
Branch and Price – B&P

ật ngữ
AF
Thu
ật toán dựa trên mô hình luồng cung (Arc
-Flow model) c
ủa
Carvalho gi
ải bài toán
OneDCSP_S
A-Team
Asynchronous Team- Ki
ến trúc không đồng bộ sử dụng trong hệ
đa tác tử
C&P
Cutting and Packing – C
ắt vật tư và đóng hàng
CSP
Cutting Stock Problem -Bài toán c
ắt vật tư
FIPA
Foundation for Intelligent Physical Agents
GA-AF
Genetic Algorithm- Arc-Flow Model – Thu
ật toán lai ghép giải
thu
ật di truyền và thuật toán AF
GMAS-
OneDCSP_M
Genetic Multi Agent System- H
ệ thống gen đa tác tử giải bài toán

ới lỏng tuyến tính của bài toán
OneDCSP_S
OneDCSP_S-
Solver
Tác t
ử giải bài toán
OneDCSP_S
iv
DANH M
ỤC CÁC BẢNG BIỂU
B
ảng 2.1 Tổng kết chất l
ượng nghiệm so với kết quả của Belov
-Scheithauer 44
B
ảng 2.2 Kết quả tính toán của Silvio A. Araujo và đồng sự
45
B
ảng 2.3 Phân bố
độ chênh lệch nghiệm so với kết quả của Belov
-Scheithauer 46
B
ảng 2.4 Thống kê thời gian tính toán
48
B
ảng 2.5 Thống kê phân bố thời gian tính toán
49
v
DANH M
ỤC CÁC HÌNH VẼ

ểu đồ tương tác giữa người dùng và hệ thống GMAS
-OneDCSP_M 55
Hình 3-3 Ki
ến trúc hệ thống GMAS
-OneDCSP_M 56
Hình 3-4 C
ấu trúc bộ nhớ chung tương ứng với mỗi bài toán
OneDCSP_M 59
Hình 3-5 Bi
ểu đồ Use Case của hệ thống GMAS
-OneDCSP_M 63
1
MỞ
Đ
ẦU
Dân s
ố thế gi
ới t
ăng nhanh và
đ
ời sống vật chất của con người không ngừng
nâng cao. Đi
ều
đó dẫn tới nhu cầu về tài nguyên thiên nhiên ngày càng lớn. Chúng
ta đã và đang chứng kiến sự cạn kiệt của tài nguyên thiên nhiên, nhất là những
ngu
ồn tài nguyên không tái tạo
được
như khoáng s
ản.

ển hình cho chủ đề này: Cắt vật tư và bài toán phế thải,
x
ếp
thùng (bin packing), bài toán s
ắp
ba lô (knapsack), cân bằng luồng (line balancing),
bài toán phân ph
ối bộ nhớ và lập lịch cho bộ
đa xử lý (
memory allocation and
multiprocessor scheduling problem)… Các bài toán c
ắt vật tư và đóng hàng được
phát bi
ểu và xử lý trong nhiều ngành khoa học khác nhau nh
ư khoa học quản
lý,
khoa h
ọc kỹ thuật, khoa học máy tính và công nghệ thông tin, toán học và vận trù
h
ọc. Chúng là các bài toán thực tế
đặt ra cho các ngành công nghiệp như công
nghiệp kính, thép, giấy, da, may mặc, vận tải và hậu cần.
T
ừ giữa thế kỷ tr
ước đã có nhiều cá
ch ti
ếp cận giải các bài toán cắt vật t
ư và
đóng hàng đư
ợc đề xuất. Công trình khởi nguồn cho chủ đề này do

ỷ trư
ớc. Trong kỹ thuật này, các tác giả sử dụng công cụ quy
ho
ạch tuyến tính để giải bài toán
n
ới lỏng
liên t
ục dẫn xuất từ bài toán quy hoạch
nguyên. Nghi
ệm của bài toán quy hoạch nguyên ban đầu sẽ nhận được bằng các kỹ
thu
ật làm tròn nghiệm của bài toán
n
ới lỏng
liên t
ục khi bài toán đảm bảo tính chất
làm tròn nguyên (Integer Round-Up Property-IRUP). Đ
ề xuất
c
ủa Gilmore và
Gomory đ
ặc biệt hiệu quả khi giải các bài toán cắt vật tư nhờ kỹ thuật tạo sinh cột
v
ới việc giải Bài t
oán x
ếp ba lô
như m
ột bài toán con
. Sau này k
ỹ thuật tạo sin

ắt vật t
ư và đóng hàng dựa trên điều t
ra
các đ
ặc tính của cấu trúc hình học, cấu trúc logic và ngữ cảnh xuất hiện của chúng
trong th
ực tế. S
ự phân lo
ại này
được G.
Waescher và các đ
ồng nghiệp tiếp tục hoàn
thi
ện vào năm 2007.
Vi
ệc phân loại được thực hiện dựa trên
b
ốn
tiêu chí:
3
1. Số chiều của bài toán: có thể là 1, 2, 3 hoặc lớn hơn
2. Ki
ểu gán (Kind of assignment)
: Có hai ki
ểu gán
là cực đ
ại hóa
đầu ra
(Output Maximization) ho
ặc c

ối tượng được cố định hay có thể biến đổi
)
- M
ột số đối tượng lớn với các chiều cố định. Trường hợp này có thể được
chia thành các bài toán v
ới các
đ
ối tượng lớn đồng nhất
, tương đ
ối đồng
nh
ất và hoàn toàn không đồng nhất.
Trong các kiểu bài toán cắt vật tư thì Bài toán cắt vật tư một chiều (One
Dimensional Cutting Stock Problem – OneDCSP) gi
ữ một vị trí quan trọng và
chi
ếm gần một nửa tổng số công trình
đã được công bố về chủ đề này. Có nhiều lý
do gi
ải thích về mối qua
n tâm c
ủa cộng đồng nghiên cứu dành ch
o bài toán này
trong đó có th
ể dẫn ra nhận xét của Gilmore và Gomory khi nói rằng
, nhi
ều bài toán
c
ắt vật tư nhiều chiều có thể được xử lý bằng một quy trình nhiều công
đo

s
ố lượng của từng loại vật tư đầu vào và lớp có
ràng bu
ộc này.
4
Có thể thấy hầu hết các công trình liên quan đến bài toán OneDCSP_M đều
hư
ớng tới giải các bài toán thuộc lớp thứ hai
. Chúng ta có th
ể khái quát các cách
ti
ếp cận được đề xuấ
t đ
ể giải bài toán này như sau.
Bài toán c
ắt vật t
ư
OneDCSP_M là bài toán quy ho
ạch nguyên và thuộc lớp NP
-
khó vì v
ậy không tồn tại thuật toán bảo đảm cho nghiệm tối ưu trong thời gian đa
th
ức. Cho
đến nay các phương pháp giải chính xác bài toán quy hoạch
nguyên này
và các bi
ến thể của nó đều được xây dựng theo
lư
ợc đồ phân nhánh và định giá

các gi
ải thuật heuristic khác nhau nhằm tìm kiếm nghiệm có chất
lư
ợng tốt trong
kho
ảng
th
ời gian chấp nhận
đư
ợc. Các giải thuật heuristic
không s
ử
d
ụng nới lỏng tuyến tính liên tục của bài toán mà dựa vào cấu trúc của bài toán
để
điều khiển quá trình tìm kiếm.
Các gi
ải thuật heuristic
đầu tiên được đề xuất để giải các bài toán cắt vật tư
thư
ờng dựa trên các phương pháp tìm kiếm cục bộ như First
-Fit, Next-Fit, Best-Fit
và Worst-Fit Decreasing đ
ể xây dựng các ph
ương án cắt
[52]. Ý t
ư
ởng chính của
nh
ững

ớn nhất tìm
được nhằm để lại
nguyên li
ệu nhiều nhất cho các bước lặp tiếp theo.
M
ột vấn
đề nảy sinh là các phương pháp dựa trên tìm kiếm cục bộ như vậy
thư
ờng rất nhanh chóng rơi vào các cực trị địa phương. Để hạn chế khả năng không
mong mu
ốn này, mộ
t s
ố tác giả
đề xuất áp dụng các Metaheuristic vào việc giải bài
toán. Yang dùng gi
ải thuật tham lam trong đó s
ử d
ụng một hàm mục tiêu phụ thuộc
vào m
ột số lượng nhỏ các điều ki
ện c
ắt để hỗ tr
ợ phát hi
ện nghiệm tốt nhất trong
quá trình tìm ki
ếm cục bộ tại
t
ừng b
ư
ớ

Trong cách ti
ếp cận
đơn hàng, các thành ph
ẩm
được sử dụng một cách độc lập
khi t
ạo ra các phương án cắt
. Cách ti
ếp cận này khá gần gũi với định nghĩa của bài
toán nhưng ít đư
ợc áp dụng trong thực tiễn vì các gen mã hóa ng
hi
ệm của bài toán
thường bị phá vỡ dưới tác động của các toán tử lai ghép. Toyoda và đồng nghiệp
[51,53] đ
ề xuất các toán tử lai ghép khác nhau trong giải thuật di truyền của mình
đ
ể giải bài toán cắt vật tư.
Falkenauer đ
ã đề xuất mô hình dựa trên nhóm
[21], trong
đó các phương án c
ắt
được xây dựng dựa trên các nhóm thành phẩm đã được phân
chia nh
ằm khắc phục sự ảnh hưởng của các toán tử di truyền đến cấu trúc nghiệm.
Yakawa và đ
ồng nghiệp cũng
đưa ra
toán t

ồng nghiệp
[43] đ
ã tiến hành so sánh hai
cách ti
ếp cận EP và GA và kết hợp tính
ưu việt của cả hai cách tiếp cận để xây dựng
m
ột giải thuật di truyền cho bài toán cắt vật tư. Trong [
48], Araujo và đ
ồng nghiệp
s
ử dụng giải thuật heuistic First
-Fit decreasing đ
ể
xây d
ựng
các phương án c
ắt tạo ra
các cá th
ể (nghiệm chấp nhận được) ở mức thấp.
Ở mức cao, các tác gi
ả đề xuất
thu
ật toán tiến hóa (Evolutionary Algorithm
-EA) v
ới toán tử lựa chọn tham lam
ng
ẫu nhiên
. Vi
ệc tạo ra các cá thể mới được thực hiện

ếp cận chính
xác
D
ựa trên mô hình nới
l
ỏng liên tục
K
ỹ thuật B&P
Cách ti
ếp cận heuristic
Cách ti
ếp cận lai ghép
D
ựa trên
Metaheuristic
và ti
ếp cận chính xác
Pure-heuristic
D
ựa trên tìm
ki
ếm cục b
ộ
Metaheuristic
S
ử dụng công cụ
toán h
ọc
để hạn chế
cực trị địa phương

- Tabu Search
Thu
ật toán
GA-AF
7
Theo hiểu biết của tác giả, cho đến nay chưa có một công trình nào liên quan đến
gi
ải bài toán
OneDCSP_M thu
ộc lớ
p th
ứ nhất (không có hạn chế về số l
ượng vật
li
ệu thô) được công bố. Bài toán này cũng chính là đối tượng nghiên cứu đặt ra cho
b
ản
lu
ận án
này.
Lu
ận án này
nh
ằm đóng g
óp m
ột phương pháp
hi
ệu quả để giải
bài toán
OneDCSP_M xu

ững mối liên quan
ng
ữ nghĩa với bài toán
OneDCSP_S, đ
ề xuất lai ghép
gi
ải thuật di truyền
v
ới
k
ỹ thuật
phân nhánh và đ
ịnh giá
theo mô hình Arc-Flow t
ạo nên
thu
ật
toán GA-AF gi
ải hiệu quả bài toán
OneDCSP_M. Tính đúng đ
ắn của thuật
toán đư
ợc chứng minh bằng lý thuyết.
Tính hi
ệu quả được kiểm chứng trên
m
ột số l
ượng tương đối lớn các bài toán
m
ẫu

ấu
trúc c
ủa Luận án như sau:
8
Ngoài phần Mở đầu và Kết luận chung, luận án được chia làm 3 chương.
Chương 1 trình bày các công c
ụ toán học
cơ s
ở nhằm giải quyết bài toán
đặt ra ở
chương sau. Ph
ần thứ nhất của chương trình bày
các mô hình và thu
ật giải
chính
xác cho bài toán c
ắt vật t
ư với một loại vật liệu thô. Phần thứ hai
trình bày tóm t
ắt
m
ột số vấn đề cơ bản của
gi
ải thuật di truyền.
Trong chương 2, tác gi
ả
phân tích m
ối liên quan ngữ nghĩa giữa bài toán
OneDCSP_M và bài toán OneDCSP_S. K
ết quả cho thấy việc cắt vật tư với nhiều

ắn của thuật toán GA
-AF
được chứng minh chặt chẽ. Tính hiệu quả của thuật toán cũng được kiểm chứng trên
t
ập
các bài toán m
ẫu do Belov
[11] đưa ra.
Phát bi
ểu mới
c
ủa bài toán
OneDCSP_M trong chương 2 đ
ã phân rã bài toán
thành nhi
ều bài toán con có thể giải quyết một cách độc lập bằng
thu
ật toán phân
nhánh và đ
ịnh giá
theo mô hình AF. T
ừ
đó
, trong chương 3, tác gi
ả
đã cài đặt thuật
toán dư
ới dạng một hệ thống đa tác tử
GMAS-OneDCSP_M nh
ằm n

tiếp theo. Phần thứ nhất giới thiệu bài toán cắt vật tư một chiều với một loại vật liệu
thô OneDCSP_S v
ới hai mô hình giải bài toán: mô hình của Gilmore
-Gomory và
mô hình Arc-Flow c
ủa Carvalho.
Ph
ần tiếp theo của chương đề cập những nội dung
cơ b
ản của
thu
ật toán di truyền.
1.1. Bài toán c
ắt vật tư một chiều với một loại vật liệu thô và thuật giải
Bài toán c
ắt vật tư một chiều kinh điển (bài toán cắt vật tư
m
ột
chi
ều với một loại
v
ật liệu thô
– One Dimensional Cutting Stock Problem with Single Stock Length
OneDCSP_S) đư
ợc xác định b
ởi các dữ liệu sau:
(m,L,l=(l
1
,…,l
m

hi
ểu với nghĩa tương đương.
Tương t
ự, hai thuật ngữ
thành ph
ẩm và sản phẩm cũng
mang ý ngh
ĩa t
ương
đương.
10
Hình 1-1 Các phương án c
ắt trong bài toán
OneDCSP_S
Bài toán OneDCSP l
ầ
n đ
ầu tiên được
Kantorovich [35] phát bi
ểu dưới dạng bài
toán quy ho
ạch nguyên và
được chứng minh thuộc lớp bài toán NP
-Hard. Sau đó
nhi
ều tác giả đã xây dựng các mô hình khác như mô hình của Gilmore
-Gomory
[26], mô hình Arc-flow c
ủa Valerio de Carvalho [
55], mô hình Node-flow c

ij
là s
ố lần thành phẩm thứ
i đư
ợc cắt theo phương án cắt
j t
ừ tấm vật
li
ệu thô. Ph
ương án cắt gọi là chấp nhận
đư
ợc
n
ếu nó thỏa mãn
đi
ều ki
ện:



m
i
iji
Lal
1
(1.1)
Gi
ả sử
njx
j

ij
L
l
i
a
i1
. . .
. . .
Phương án cắt 1
11
trên miền ràng buộc:
1
n
ij j i
j
a x b



i=1,…,m (1.3)
j
x


, j=1,…,n (1.4)
Mô hình (1.1)-(1.4) là bài toán quy ho
ạch nguyên với số l
ượng biến
n tăng theo
hàm mũ của m. Mô hình này khắc phục được tính đối xứng của mô hình

ơn 1 chiếm đa số. Những bài toán như vậy
đư
ợc gọi là các bài toán có tính chất làm tròn nguyên (
Integer Round-Up Property –
IRUP). Nh
ững bài toán có
sai khác l
ớn h
ơn hoặc bằng 1 được gọi là những bài toán
non-IRUP.
Trên cơ s
ở dự
đoán đó, Gilmore và Gomory đề xuất cách tiếp cận giải bài toán
(1.1)-(1.4) g
ồm 2 bước: 1/ giải bài toán nới lỏng liên tục của
(1.1)-(1.4); 2/ Làm
tròn s
ố nghiệm tối
ưu của bài
toán n
ới lỏng liên tục
để nhận được nghiệm của bài
toán (1.1)-(1.4).
Đ
ể giải bài toán nới lỏng liên tục của
(1.1)-(1.4) v
ới số l
ượng biến
n r
ất lớn,

ẽ có dạng:
 
_ ( , , , ) min : ,
LP n
OneDCSP S m L l b x Ax b x

   
(1.6)
Xu
ất phát, kỹ thuật tạo sinh cột sẽ làm việc với một tập con các cột
c
ủa
A đư
ợc
g
ọi là bài toán chủ hạn chế (
Restricted Master Problem - RMP). RMP có th
ể được
kh
ởi tạo dễ dàng, ví dụ bởi cơ sở
ki
ến thiết
ban đ
ầu của phương pháp đơn hình. Giả
s
ử
A’ là các c
ột trong
A đư
ợc lựa chọn. Khi đó RMP có dạng:

toán x
ếp ba lô
):
 
max : ,
m
ua al L a

 
(1.8)
Nghi
ệm tối ưu của (1.8) sẽ lần lượt được thêm vào RMP nếu giá trị tối ưu tương
ứng của (1.8) lớn h
ơn 1. N
ếu (1.8) không có nghiệm tối ưu như vậy thì nghiệm tối
ưu của bài toán RMP (1.7) chính là nghiệm tối ưu của bài toán MP (1.6).
Trên cơ s
ở ý t
ưởn
g v
ừa trình bày, ph
ương pháp tạo sinh cột giải bài toán quy
ho
ạch tuyến tính cỡ lớn được Gilmore
-Gomory nhúng vào lư
ợc đồ nhánh cận
(Brand and Bound) đ
ể tạo nên
lư
ợc

- N={0,1,…,L} là t
ập các nút
;
-
    
LNuvumiluvNNvuA
i
\/),(, ,1,/),( 
là t
ập các cung
.
Các cung n
ối mỗi cặp nút liên tiếp từ 0 tới
L không ph
ủ bất cứ một thành phẩm
nào. M
ột sản phẩm thứ
i đư
ợc biểu diễn một số lần trên mạng lưới bởi các cung có
đ
ộ dài
v-u=l
i
, i=1,…,m.
Ta ký hi
ệu các biến quyết định
x
uv
là s
ố lượng

2
3
4
5
6
7
8
9
4
2
2
14
Với cách xác định mạng lưới như vậy , bài toán OneDCSP_S sẽ có độ phức tạp
tính toán gi
ả
đa thức (Pseudo
-polynomial) O(mL) và tr
ở thành bài toán tìm luồng
c
ực tiểu sau:
Min z (1.9)
trên mi
ền ràn
g bu
ộc:
i
Aluu
luu
bx
i

uL


),(
(1.13)
uv
x


(u,v)A (1.14)
N
ếu ta áp dụng phân rã Dantzig
-Wolfe (bi
ểu diễn một
điểm trong đa diện bằng tổ
h
ợp lồi của các điểm cực cộng với một tổ hợp tuyến tính không âm của các tia cực)
vào bài toán (1.9)-(1.14) và gi
ữ ràng buộc (1.10) trong bài toán chủ thì bài toán con
xác đ
ịnh
b
ởi (1.11)
-(1.14) là bài toán lu
ồng với không gian nghiệm tương ứng với
các lu
ồng chấp nhận được giữa nút khởi đầu 0 và nút kết thúc
L. Bài toán con này
th
ể hiện ràng buộc bảo toàn luồng (flow conservation con

-(1.14)
Th
ực chất, biến
z có th
ể được coi như cung phản hồi từ nút kết thúc
L t
ới nút
kh
ởi đầu 0 (cũng có thể ký hiệu là
x
w0
) và các nghi
ệm của bài toán con như là luồng
15
chu trình được tạo nên bởi đường đi từ nút khởi đầu 0 tới nút kết thúc L và cung x
w0
.
Như v
ậy có một t
ương ứng 1
-1 gi
ữa các chu trình và các
đường đi. Nếu chúng ta coi
các nghi
ệm của bài toán con như các chu trình, các ràng buộc của bài toán con xác
đ
ịnh một hệ thuần nhất và không giới nội.
Do đó, đa di
ện t
ương ứng có một điểm

Ưu đi
ểm của mô hình
này là hoàn toàn không làm thay đ
ổi cấu trúc của bài toán
ch
ủ và các bài toán con khi tạo nới lỏng tuyến tính liên tục cũng nh
ư trong qu
á trình
th
ực hiện chiến lược phân nhánh và định giá.
Ta nh
ận
th
ấy
r
ằng, mô hình trên có nh
ược điểm là tính đối xứng. Để loại bỏ điều
đó, Valerio de Carvalho đề xuất các thành phẩm được cắt theo chiều giảm của kích
thư
ớc, tức là các cung t
ương ứng với các t
hành ph
ẩm có kích th
ước lớn hơn sẽ được
x
ếp ở gần nút 0 hơn và phế thải được dồn về phía nút
L.
T
ừ
đó, Valerio de Carvalho đã đề xuất thuật toán giải chính xác bài toán

độ dài
q-p t
ại
điểm có khoảng cách
p t
ừ biên trái của vật liệu và các
x
j
là các bi
ến quyết định của mô hình này, ta có thể xác định giá trị của biến luồng
x
pq
như sau:



),( qpAj
jpq
xx

(1.16)
N
ếu
 không nguyên, ta t
ạo 2 nhánh tương ứng với các bất đẳng thức
x
pq
≤ 
và x
pq

Jj
wl
ijj
l
j
Glxx ,

(1.19)
 



Jj
wl
ijj
l
j
Hlxx ,

(1.20)
x
j
≥0, jJ (1.21)
ở
đây
G
w
và H
w
là các t

ắt chấp nhận
được. Ta thấy (1.17)
-(1.18) chính là mô hình c
ủa Gilmore
-Gomory;
(1.19)-(1.20) là các ràng bu
ộc phân nhánh.
Như v
ậy
, m
ỗi nút của cây sẽ t
ương ứng với cùng một mô hình Gilmore
-Gomory
(phân rã Dantzig-Wolfe c
ủa mô hình Arc flow) (1.17)
-(1.18) v
ới việc bổ sung các
ràng bu
ộc phân nhánh dựa trên các biến luồng (1.19)
-(1.20).