fdabrandao/vpsolver

Arc-flow Vector Packing Solver — Giải pháp tối ưu đóng gói đa chiều mạnh mẽ

VPSolver sinh ra các mô hình rất mạnh (tương đương Gilmore–Gomory) cho bài toán đóng gói vector, dựa trên công thức dòng chảy và nén đồ thị.

VPSolver là một bộ giải bài toán đóng gói vector lựa chọn nhiều tiêu chuẩn (multiple-choice vector packing) dựa trên công thức dòng chảy (arc-flow formulation) kết hợp nén đồ thị (graph compression). Dự án do Filipe Brandão phát triển, có thể giải quyết trên các trình giải MIP chung như Gurobi, GLPK, CPLEX, SCIP…

✨ Điểm nổi bật

• Công thức dòng chảy với nén đồ thị: tạo ra các mô hình mạnh tương đương phương pháp Gilmore–Gomory
• Hỗ trợ nhiều trình giải MIP: Gurobi, CPLEX, GLPK, COIN-OR, SCIP, lp_solve...
• Giao diện Python API: tương thích Python 2.7 và 3.x, hỗ trợ Jupyter Notebook
• Ứng dụng web (Web App): giao diện đồ họa trực tuyến
• Hỗ trợ Docker: dễ dàng triển khai và chạy trên mọi nền tảng
• Đa nền tảng: chạy trên Linux, macOS, Windows
• Công cụ dòng lệnh: hỗ trợ chuyển đổi định dạng VBP/MVP sang MPS/LP
• Tích hợp PyMPL: công cụ mô hình hóa linh hoạt

💡 Vì sao đáng chú ý

VPSolver nổi bật nhờ kết hợp giữa công thức dòng chảy mạnh mẽ và kỹ thuật nén đồ thị, giúp giảm đáng kể kích thước mô hình so với cách tiếp cận truyền thống. Phương pháp này sinh ra các mô hình tương đương với phương pháp Gilmore–Gomory nhưng hiệu quả hơn trong thực hành.

Phù hợp cho các bài toán đóng gói ngành công nghiệp như cắt nguyên liệu, phân bổ nguồn lực, và các biến thể đóng gói đa ràng buộc. Đặc biệt hữu ích khi cần giải các mô hình lớn với sự hỗ trợ từ các trình giải MIP chuyên nghiệp.

---

#Optimization #ArcFlow #VectorPacking #BinPacking #CuttingStock #GraphCompression #TiniX