Vách ngăn $N$ các mặt hàng vào $K$ phân vùng có kích thước bằng nhau trong khi vẫn giữ các nhóm trong các mục gốc
Giả sử có $N$ các mặt hàng đi vào $M$các nhóm. Để cho$c_i \in \{1, ..., M\}$ cho $i=1, ..., N$ đại diện cho thành viên nhóm cho mặt hàng $i$. Tôi muốn tìm một phân vùng thô hơn cho các mục vào$K$ nhóm mới, ở đâu $K < M$, với hai ràng buộc:
- các mục trong cùng một nhóm phải được gán cho cùng một phân vùng, và
- kích thước nhóm mới phải càng gần càng tốt.
Suy nghĩ ban đầu của tôi là xây dựng công thức này như một chương trình số nguyên phi tuyến tính, trong đó $y_{ij} = 1$ nếu mục $i$ được gán cho phân vùng $j$và bằng 0 nếu không. Sau đó, tôi sẽ có một tập hợp các ràng buộc:
- $\sum_{j=1}^K y_{ij} = 1$ cho $i=1,..., N$ (mỗi mục nên được chỉ định cho chính xác một phân vùng)
- $y_{ij} = y_{\ell j}$ cho tất cả $j=1, ..., K$ nếu $c_i = c_\ell$ (các mục trong cùng một nhóm phải được gán cho cùng một phân vùng)
và sau đó tôi có thể xác định $N_j = \sum_{i=1}^N y_{ij}$ và giảm thiểu
$$\sum_{j=1}^K \left(N_j - \frac NK \right)^2.$$
Tuy nhiên, mục tiêu cụ thể không thực sự quan trọng ở đây. Miễn là$N_j$ gần với $N/K$ cho tất cả $j$, Tôi không quan tâm nếu nó ở trong một $\ell_2$ hoặc là $\ell_1$ cảm giác hoặc điều gì đó khác một cách mơ hồ dọc theo những dòng đó.
Những câu hỏi của tôi:
- Có một công thức tốt hơn cho vấn đề này với một giải pháp đặc biệt dễ dàng?
- Những thuật toán nào sẽ giải quyết vấn đề này một cách chính xác? Có những cách nào để có được các giải pháp gần đúng tham lam nhanh chóng?
- Tôi cho rằng tôi sẽ cần tận dụng một số phần mềm tối ưu hóa hiện có để có được giải pháp của mình. Có bất kỳ lựa chọn tiêu chuẩn nào ở đây cho người dùng Python / Julia / R không? (Các mẫu mã được đánh giá cao!)
Một số thông tin cơ bản bổ sung: Về cơ bản, tôi đang tìm kiếm một cách tiếp cận hiệu quả hơn (về mặt tính toán) để loại bỏ xác thực chéo. Tiêu chuẩn hiện tại là để lại một nhóm duy nhất tại một thời điểm, sao cho bạn phù hợp$M$ mô hình, ở đâu $M$có thể khá cao. Trong thực tế, một cái gì đó như$K=5$ hoặc là $K=10$là đủ cho mục đích thống kê và xác nhận chéo sẽ có các thuộc tính chúng ta muốn miễn là mọi người trong cùng một nhóm đi vào cùng một nếp gấp và các nếp gấp có cùng kích thước. Thật phù hợp$M >> 10$ mô hình khi có nhiều nhóm thường không hiệu quả và không cần thiết.
Trả lời
Một cách tiếp cận là coi các nhóm là các công việc, với thời lượng của mỗi công việc bằng số lượng các mục trong nhóm của nó. Bây giờ hãy lên lịch cho những công việc này vào$K$ máy giống hệt nhau, giảm thiểu thời gian tạo ra, tức là, giảm thiểu $\max_j N_j$. LPT heuristic nhanh và mang lại$(2-1/K)$-xếp cận.
Câu hỏi đầu tiên: Trong mô hình IP, bạn không cần biến nhị phân cho mỗi tổ hợp mục và phân vùng. Với yêu cầu của bạn rằng các nhóm được giữ cùng nhau, bạn chỉ cần một tệp nhị phân cho mỗi kết hợp nhóm và phân vùng. Của bạn$y_{ij}=y_{\ell j}$các ràng buộc sẽ cho phép chức năng presolve của bộ giải thu nhỏ mô hình xuống kích thước này, nhưng bạn cũng có thể bắt đầu với công thức nhỏ hơn. Ngoài ra, thay vì đặt vấn đề thành bậc hai, tôi có thể sẽ giảm thiểu sự khác biệt giữa kích thước phân vùng nhỏ nhất và lớn nhất, là tuyến tính. Điều này không nhất thiết phải tạo ra một mô hình "đặc biệt dễ giải quyết", nhưng tùy thuộc vào kích thước vấn đề và trình giải quyết IP của bạn (và sự kiên nhẫn của bạn), nó có thể đủ dễ dàng.
Câu hỏi thứ hai: Bạn có thể giải quyết vấn đề một cách chính xác bằng cách sử dụng mô hình IP và bộ giải IP. Một kinh nghiệm nhanh có thể làm tốt một cách hợp lý là bắt đầu với$K$ phân vùng trống, sắp xếp các nhóm theo thứ tự kích thước giảm dần, sau đó gán mỗi nhóm vào phân vùng nhỏ nhất hiện tại.
Câu hỏi thứ ba: Tôi không thể nói về Julia hoặc Python (mặc dù tôi biết một số bộ giải IP cho Python), nhưng với RI sẽ có xu hướng sử dụng gói OMPR (DSL cho LP / IP) để viết mô hình. Đến lượt nó, OMPR sẽ dựa vào ROI để giải quyết mô hình và cả OMPR và ROI sẽ yêu cầu bạn tải một plugin dành riêng cho bộ giải (và tất nhiên, phải cài đặt bộ giải tương ứng).
Tôi đã hack một máy tính xách tay R bằng cách sử dụng OMPR và ROI với các trình cắm CPLEX tương ứng của chúng. Trong một vấn đề kiểm tra ngẫu nhiên với$N=5700$, $M=130$ và $K=10$, heuristic mà tôi đã mô tả thường có kích thước phân vùng trải rộng là 5 (kích thước từ 567 đến 572) và mô hình IP có mười phân vùng là 570 mỗi phân vùng (spread = 0). Heuristic mất một phần (nhỏ) của giây. Xây dựng mô hình IP và giải quyết nó bằng CPLEX mất khoảng chín giây.
Như mọi khi, số dặm của bạn sẽ thay đổi.
ADDENDUM: Tôi nghi ngờ (chính xác) rằng việc sử dụng số tròn cho các kích thước của vấn đề có thể làm cho mọi thứ đẹp hơn, vì vậy tôi đã thử $N=5723$, $M=137$ và $K=10$(đảm bảo rằng không có giải pháp nào có tất cả các kích thước phân vùng giống hệt nhau). Giải pháp IP quản lý mức chênh lệch là 1 (một số phân vùng có 572 mục, một số có 573, vẫn tốt hơn tôi nghĩ là có thể đạt được nói chung). Giải pháp heuristic có khoảng 30 (kích thước phân vùng từ 552 đến 582).
PHỤ LỤC 2: Tôi đã thêm một phương pháp heuristic xen kẽ theo cặp sau cái mà Rob gọi là phương pháp heuristic LPT. Trong ví dụ với$N=5723$v.v., heuristic hoán đổi theo cặp đã giảm mức chênh lệch từ 30 xuống 2, không hoàn toàn tối ưu (tối ưu là 1) nhưng gần hơn rất nhiều. Giống như LPT, heuristic hoán đổi mất chưa đầy một giây trong ví dụ này.