Báo Cáo Những phương pháp dựa trên nhánh-và-cận cho những bài toán qui hoạch nguyên

BRANCH-AND-BOUND BASED METHODS FOR INTEGER PROGRAMS

BẢN TÓM TẮT
​

Bài báo giới thiệu một lãnh vực nghiên cứu trong tối ưu tổ hợp, gọi là quy hoạch nguyên. Không
giống những phương pháp tính toán mềm, hướng nghiên cứu này tập trung nghiên cứu những lý thuyết
và phương pháp hiệu quả trong việc tìm kiếm lời giải tối ưu toàn cục. Trong đó, branch-and-bound kết
hợp với việc tạo những mặt cắt là một phương pháp khung nổi tiếng. Nhiều khía cạnh từ ứng dụng, mô
hình đến phương pháp giải sẽ được khảo sát và trình bày tóm tắt. Lãnh vực này cũng là một hướng
ứng dụng của tính toán song song đang là một xu thế phát triển của tính toán khoa học hiệu năng cao.
Việc giải các bài toán tối ưu có khối lượng tính toán lớn trong thời gian hợp lý là rất khả thi.

ABSTRACT
​

In the paper, we present an interesting research area in combinatorial optimization, called integer
programming. Not as non-exact methods, this direction primarily focuses on finding optimal solutions
efficiently. Branch-and-bound with cutting plane generation is a well-known framework to solve
integer programs. All its aspects ranged from applications, models to solution methods will be briefly
surveyed. Moreover, the area is also considered under a view of parallel computing, which is an
increasingly popular trend in high performance scientific computing. It is promising to solve large
scale optimization problems to optimality within a reasonable computation time.