クラスでの生徒の最適な割り当てをどのように見つけますか？

Question

レベルAの瞳孔、レベルBの瞳孔24、レベルCの瞳孔30の3つのクラスに割り当てる必要があります。 クラスはほぼ同じサイズである必要があります。 異なるレベルを1つのクラスに混在させることはできますが、避けることができればより良い方法です。いずれにせよ、クラス内の1つのレベルから0人の生徒、または6人以上の生徒がいるはずです。

このコンビナトリアル最適化の問題を解決できますか？以下は、入力と出力のサンプルです。あなたが一般的な問題を解決する方法を私に示すことができる場合、ボーナスポイント！

入力：

pupils = { "A" : 23, "B" : 24, "C": 30 } 

出力例（非常に良いではない！）

Class #1 : {'A': 9, 'B': 6, 'C': 10}, 
Class #2 : {'A': 10, 'B': 9, 'C': 7}, 
Class #3 : {'A': 11, 'B': 9, 'C': 6} 

編集：Here私の非常にハック、完全に文書化されていない、半ブルートフォースコードです。それは醜いですが、それは動作します！私はより洗練されたソリューションをどのように書くことができるかを学びたいと思っています。

Answer 1

ここでの基本的な難点は、多目的最適化の問題があることです。

1. 取得似たクラスが
2. がから十分な学生を持つ
3. クラスあたりのレベルの数を最小限に抑えるサイズ：あなたは3つのことを持っている私はあなたが目的または「ソフトな制約」を考慮するかということに興味を考えますあるクラスの学生がいる場合、クラス内のレベル。

これはAMPLで最適化モデルを書いたことに注意してください。あなたがPythonを使用しているので、あなたが使うことができるPuLPやpyomoのようなPython用の同様の最適化モデリング言語があります。モデルは翻訳するのが難しいはずがありません。

ここでは、問題の（整数）線形を維持しながら、目的の数値1を強調する整数プログラミングモデルとデータファイルを示します。この目的で、最適化問題は、あなたの例題で示したのと同じ解決策を見つけます。うまくいけば、この上に構築し、他の制約や客観的な用語を追加し、より良い解決策を得ることができます。

最大のクラスサイズを最小にすることが目的です。関心のある変数はy [i、j]です。 LEVELのi [i、j]、CLASSのjは、クラスjに割り当てられたレベルiの生徒の数です。それは、あなたがそのレベルに割り当てられている場合、各クラスの各レベルからの学生の最小数の入力を持っていることを前提としています。

目的関数はあなたが望むものではないかもしれませんが、線形のクラスサイズを等しくしようとする方法です。私はこれが問題を解決する最も効率的な方法であるとは約束していません。問題のためのより良いカスタムアルゴリズムがあるかもしれませんが、私がしなければならなかったのは、制約と目的を表現し、アルゴリズムを書かないことでした。おそらくあなたの使用には十分です。

neos-serverでソルバーグロビを使用する。ORG（あなたがlpsolveや他のオープンソースの最適化ソルバーを使用することができます）、私は解決策を持って

y := 
1 1 14 
1 2 9 
1 3 0 
2 1 6 
2 2 0 
2 3 18 
3 1 6 
3 2 16 
3 3 8 
; 

モデル：あなたの例のための

set LEVEL ordered; 
set CLASS; 

param maxClassSize {CLASS}; 
param minLevelNumberInClass {LEVEL, CLASS}; 
param numInLevel {LEVEL}; 

var z >= 0; 
var y{LEVEL, CLASS} integer, >= 0; 
var x{LEVEL, CLASS} binary; 

#minimize maximum class size 
minimize obj: 
    z; 

subject to allStudentsAssigned {i in LEVEL}: 
    sum {j in CLASS} y[i,j] = numInLevel[i]; 

#z is the largest of all classes sizes 
subject to minMaxZ {j in CLASS}: 
    z >= sum {i in LEVEL} y[i,j]; 

subject to maxClassSizeCon {j in CLASS}: 
    sum {i in LEVEL} y[i,j] <= maxClassSize[j]; 

#xij = 1 if any students from level i are in class j 
subject to defineX {i in LEVEL, j in CLASS}: 
    y[i,j] <= min(numInLevel[i], maxClassSize[j]) * x[i,j]; 

#if any students from level i are assigned to class j, then there is a minimum 
#if x[i,j] = 1, y[i,j] >= minLevelNumberInClass[i,j] 
subject to minLevel {i in LEVEL, j in CLASS}: 
    minLevelNumberInClass[i,j] * x[i,j] <= y[i,j]; 

データファイル：

set LEVEL := 1 2 3; 
set CLASS := 1 2 3; 

param minLevelNumberInClass: 
    1 2 3 := 
1 6 6 6 
2 6 6 6 
3 6 6 6 
; 

param maxClassSize := 
1 77 
2 77 
3 77 
; 

param numInLevel := 
1 23 
2 24 
3 30 
;