พาร์ทิชัน $N$ รายการเข้าไป $K$ พาร์ติชันที่มีขนาดเท่ากันในขณะที่ยังคงรักษากลุ่มไว้ในรายการดั้งเดิม
สมมติว่ามี $N$ รายการที่เข้ามา $M$กลุ่ม ปล่อย$c_i \in \{1, ..., M\}$ สำหรับ $i=1, ..., N$ แสดงถึงการเป็นสมาชิกกลุ่มสำหรับรายการ $i$. ฉันต้องการหาพาร์ติชันที่หยาบกว่าของรายการใน$K$ กลุ่มใหม่ที่ไหน $K < M$โดยมีข้อ จำกัด สองประการ:
- รายการในกลุ่มเดียวกันต้องถูกกำหนดให้กับพาร์ติชันเดียวกันและ
- ขนาดกลุ่มใหม่ควรใกล้เคียงกันมากที่สุด
ความคิดเริ่มต้นของฉันคือการกำหนดสิ่งนี้เป็นโปรแกรมจำนวนเต็มที่ไม่ใช่เชิงเส้นโดยที่ $y_{ij} = 1$ ถ้ารายการ $i$ ถูกกำหนดให้กับพาร์ติชัน $j$และเป็นศูนย์อย่างอื่น จากนั้นฉันจะมีข้อ จำกัด ชุดหนึ่ง:
- $\sum_{j=1}^K y_{ij} = 1$ สำหรับ $i=1,..., N$ (แต่ละรายการควรกำหนดให้กับพาร์ติชันเดียว)
- $y_{ij} = y_{\ell j}$ เพื่อทุกสิ่ง $j=1, ..., K$ ถ้า $c_i = c_\ell$ (รายการในกลุ่มเดียวกันต้องกำหนดให้กับพาร์ติชันเดียวกัน)
แล้วฉันก็สามารถกำหนดได้ $N_j = \sum_{i=1}^N y_{ij}$ และย่อเล็กสุด
$$\sum_{j=1}^K \left(N_j - \frac NK \right)^2.$$
อย่างไรก็ตามวัตถุประสงค์เฉพาะไม่สำคัญที่นี่ ตราบใดที่$N_j$ อยู่ใกล้กับ $N/K$ เพื่อทุกสิ่ง $j$ฉันไม่สนใจว่ามันจะอยู่ในไฟล์ $\ell_2$ หรือ $\ell_1$ ความรู้สึกหรืออย่างอื่นอย่างคลุมเครือตามแนวเหล่านั้น
คำถามของฉัน:
- มีวิธีการแก้ปัญหาที่ง่ายกว่านี้หรือไม่?
- อัลกอริทึมใดที่จะแก้ปัญหานี้ได้อย่างแน่นอน มีวิธีการแก้ปัญหาโดยประมาณอย่างรวดเร็วหรือไม่?
- ฉันคิดว่าฉันจะต้องใช้ประโยชน์จากซอฟต์แวร์เพิ่มประสิทธิภาพที่มีอยู่เพื่อให้ได้โซลูชันของฉัน มีตัวเลือกมาตรฐานสำหรับผู้ใช้ Python / Julia / R หรือไม่? (ตัวอย่างโค้ดชื่นชมมาก!)
พื้นฐานเพิ่มเติมบางประการ: โดยพื้นฐานแล้วฉันกำลังมองหาวิธีการที่มีประสิทธิภาพมากขึ้น (เชิงคำนวณ) ในการตรวจสอบความถูกต้องข้ามกลุ่ม มาตรฐานปัจจุบันคือปล่อยให้กลุ่มเดียวออกในเวลาที่คุณเหมาะสม$M$ โมเดลที่ไหน $M$ได้ค่อนข้างสูง ในทางปฏิบัติบางอย่างเช่น$K=5$ หรือ $K=10$เพียงพอสำหรับวัตถุประสงค์ทางสถิติและการตรวจสอบความถูกต้องข้ามจะมีคุณสมบัติที่เราต้องการตราบเท่าที่ทุกคนในกลุ่มเดียวกันเข้าสู่การพับเดียวกันและการพับมีขนาดใกล้เคียงกัน พอดี$M >> 10$ โมเดลเมื่อมีหลายกลุ่มมักไม่มีประสิทธิภาพและไม่จำเป็น
คำตอบ
แนวทางหนึ่งคือการคิดว่ากลุ่มเป็นงานโดยมีระยะเวลาของแต่ละงานเท่ากับจำนวนรายการในกลุ่ม ตอนนี้กำหนดเวลางานเหล่านี้ใน$K$ เครื่องจักรที่เหมือนกันการลดขนาดล้อแม็กนั่นคือย่อส่วน $\max_j N_j$. LPT heuristic รวดเร็วและให้ผลตอบแทน$(2-1/K)$- ประมาณ
คำถามแรก: ในโมเดล IP คุณไม่จำเป็นต้องมีตัวแปรไบนารีสำหรับการรวมรายการและพาร์ติชันแต่ละชุด ตามความต้องการของคุณที่ให้รวมกลุ่มไว้ด้วยกันคุณเพียงแค่ต้องมีไบนารีสำหรับการรวมกลุ่มและพาร์ติชันแต่ละชุด ของคุณ$y_{ij}=y_{\ell j}$ข้อ จำกัด จะทำให้ฟังก์ชั่น Presolve ของตัวแก้ย่อขนาดโมเดลลงให้เหลือขนาดนี้ แต่คุณอาจเริ่มต้นด้วยสูตรที่เล็กลงก็ได้เช่นกัน นอกจากนี้แทนที่จะสร้างปัญหากำลังสองฉันอาจจะลดความแตกต่างระหว่างขนาดพาร์ติชันที่เล็กที่สุดและใหญ่ที่สุดซึ่งเป็นเส้นตรง สิ่งนี้ไม่จำเป็นต้องสร้างโมเดลที่ "ง่ายเป็นพิเศษ" ในการแก้ปัญหา แต่ทั้งนี้ขึ้นอยู่กับขนาดปัญหาและตัวแก้ IP ของคุณ (และความอดทนของคุณ) มันอาจจะง่ายพอ
คำถามที่สอง: คุณสามารถแก้ปัญหาได้อย่างแม่นยำโดยใช้โมเดล IP และตัวแก้ IP การฮิวริสติกอย่างรวดเร็วที่อาจทำได้ดีพอสมควรคือการเริ่มต้นด้วย$K$ พาร์ติชันว่างจัดเรียงกลุ่มตามลำดับขนาดจากมากไปหาน้อยจากนั้นกำหนดแต่ละกลุ่มให้กับพาร์ติชันที่เล็กที่สุดในปัจจุบัน
คำถามที่สาม: ฉันไม่สามารถพูดแทน Julia หรือ Python ได้ (แม้ว่าฉันจะรู้จักตัวแก้ IP บางตัวสำหรับ Python) แต่ด้วย RI จะมีแนวโน้มที่จะใช้แพ็คเกจ OMPR (DSL สำหรับ LP / IP) ในการเขียนโมเดล OMPR จะพึ่งพา ROI ในการแก้โมเดลและทั้ง OMPR และ ROI จะกำหนดให้คุณต้องโหลดปลั๊กอินเฉพาะสำหรับตัวแก้ (และแน่นอนว่าต้องติดตั้งตัวแก้ปัญหาที่เกี่ยวข้อง)
ฉันแฮ็กโน้ตบุ๊ก R โดยใช้ OMPR และ ROI ด้วยปลั๊กอิน CPLEX ตามลำดับ เกี่ยวกับปัญหาการทดสอบแบบสุ่มด้วย$N=5700$, $M=130$ และ $K=10$ฮิวริสติกที่ฉันอธิบายโดยทั่วไปจะมีการแพร่กระจายขนาดพาร์ติชันเป็น 5 (ขนาดตั้งแต่ 567 ถึง 572) และโมเดล IP มีพาร์ติชัน 10 พาร์ติชันเท่ากับ 570 พาร์ติชัน (สเปรด = 0) ฮิวริสติกใช้เวลา (เล็ก ๆ ) เสี้ยววินาที การสร้างแบบจำลอง IP และการแก้ปัญหาด้วย CPLEX ใช้เวลาประมาณเก้าวินาที
เช่นเคยระยะทางของคุณจะแตกต่างกันไป
เพิ่มเติม: ฉันสงสัย (อย่างถูกต้อง) ว่าการใช้ตัวเลขกลมๆสำหรับขนาดของปัญหาอาจทำให้สิ่งต่างๆดีขึ้นดังนั้นฉันจึงลอง $N=5723$, $M=137$ และ $K=10$(ซึ่งทำให้มั่นใจได้ว่าไม่มีโซลูชันใดที่มีขนาดพาร์ติชันเหมือนกันทั้งหมด) โซลูชัน IP มีการจัดการการแพร่กระจาย 1 (บางพาร์ติชันมี 572 รายการบางส่วนมี 573 รายการซึ่งยังดีกว่าที่ฉันคิดว่าทำได้โดยทั่วไป) โซลูชันฮิวริสติกมีการแพร่กระจาย 30 (ขนาดพาร์ติชันตั้งแต่ 552 ถึง 582)
ภาคผนวก 2: ฉันได้เพิ่มฮิวริสติกการแลกเปลี่ยนแบบคู่กันหลังจากที่ร็อบเรียกว่าฮิวริสติก LPT ในตัวอย่างด้วย$N=5723$ฯลฯ ฮิวริสติกแบบ swap swap ลดการแพร่กระจายจาก 30 เป็น 2 ซึ่งไม่เหมาะสมนัก (เหมาะสมที่สุดคือ 1) แต่ใกล้กว่ามาก เช่นเดียวกับ LPT ฮิวริสติกการแลกเปลี่ยนใช้เวลาไม่เกินหนึ่งวินาทีในตัวอย่างนี้