0

dpcplex モデルを使用しているいくつかの制約に基づいて、20x38 のバイナリ マトリックスを生成したいと考えています。マトリックス セルの一部は、以下のように事前定義されています (行、列、パラメータ)。

[(8,3,0),(14,0,0),(14,2,0),(16,0,0),(16,1,0),(12,0,0),( 10,0,0)、(10,8,0)、(10,9,0)、(17,7,0)、(17,8,0)、(8,0,0)、(13、 8,0),(13,9,0),(1,0,1),(15,19,0)]

他のマトリックス セルにいくつかの制約を入力する必要があります。

  • 列の合計は 10 でなければなりません
  • 行の合計は 19 に等しくなければなりません
  • 各行の最後の 4 つのセルは代替でなければなりません: 1010 または 0101 のみが許可されます
  • 0 または 1 が 2 つ以上連続しない
  • 各行の 5 つのセルごとの合計は [2,3] の範囲内でなければなりません: 11011 または 00100 はありません
  • 連続する 0 のペアの合計は <=3 である必要があります。各行には、00 のペアが 3 つ以上、11 のペアが 3 つ以上あることはできません。

問題は、モデルが解を返さないことです。私のモデルが正しいかどうかはわかりません。

ここに私のコードがあります:

from docplex.mp.model import Model

cond=[[8,3,0],[1,37,0],[6,9,0]]

model = Model("MatrixComple")

R = [i for i in range(20)]
R1=[i for i in range(38)]
R2=[34,35,36,37]
R3=[i for i in range(36)]
R4=[i for i in range(34)]
R5=[i for i in range(37)]
idx = [(i, j) for i in R for j in R1 ]

x = model.binary_var_dict(idx,name= "x")

"""pre-defined cells"""
for i in R:
    for j in R1:
        for item in cond:
            i1,i2,i3=item
            model.add_constraint(x[i1, i2] == i3)

"""sum of columns must be equal to 10   """    
model.add_constraints(model.sum(x[i, j] for i in R) == 10 for j in R2)

"""sum of rows must be equal to 19  """
model.add_constraints(model.sum(x[i, j] for j in R1) == 19 for i in R)

"""(apply to all rows)last 4 cells of each row must be alternative: just 1010 or 0101 is allowed"""
model.add_constraints(model.sum(x[(i, j)] for j in R2 ) == 2 for i in R  )
model.add_constraints(x[(i, 34)] ==x[(i, 36)]  for i in R  )


"""no more that 2 consecutive 0s or 1s : 110 or 001 or 101 or 010
this rule can not be applied to pre-defined cells. For example if we have 000 or 111 in pre-defined conditions,
we need to apply this rule for the rest of matrix not the pre-defined cells
""" 
model.add_constraints(model.sum(x[i, j]+x[i,j+1]+x[i,j+2] for j in R3) <=2 for i in R)
model.add_constraints(model.sum(x[i, j]+x[i,j+1]+x[i,j+2] for j in R3) >=1 for i in R)


""" (apply to all rows) sum of every 5 cells in each row must be in range [2,3] : no 11011 or 00100 is allowed """
model.add_constraints(model.sum(x[i, j]+x[i,j+1]+x[i,j+2]+x[i,j+3]+x[i,j+4]for j in R4) <=3 for i in R)
model.add_constraints(model.sum(x[i, j]+x[i,j+1]+x[i,j+2]+x[i,j+3]+x[i,j+4]for j in R4) >=2 for i in R)

""" (apply to all rows) sum of pair of consecutive 0s must be <=3 : in each row we are not allowed to have 
more than 3 pair of 00 """

for i in R:
    s=0
    for j in R5:
            if x[i, j]==x[i,j+1]==0:
                    s+=1
    model.add_constraint(s<= 3)

""" (apply to all rows) sum of pair of consecutive 1s must be <=3 : in each row we are not allowed to have 
more than 3 pair of 11 """
for i in R:
    s=0
    for j in R5:
            if x[i, j]==x[i,j+1]==1:
                    s+=1
    model.add_constraint(s<= 3)

solution = model.solve()
print(solution)
4

3 に答える 3

1

問題全体を解決する時間はありませんが、最後の 2 つのブロック (連続する値の制約) で重大な問題を見つけることができます。まず、指定されたコードは TypeError を発生させます。

TypeError: Cannot use == to test expression equality, try using Python is operator or method equals: x_0_0 == x_0_1

これには正当な理由があります。DOcplex では、変数間の「==」演算子がオーバーロードされて、制約、つまりモデルのオブジェクトが構築されます。このオブジェクトには Python の真理値がなく、Python の if ステートメントでは使用できません。

また、s使用している変数は DOcplex 変数ではないため、制約のポストには使用できません。

制約を実装するには、Docplex で可能なアプローチを次に示します。各 (i, j) セルに対して、制約を定義します。これは、(i,j) と (i,j+1) が両方ともゼロに等しい場合に満たされ、格納されます。リスト内の行のすべての制約:

for i in R
   twozs = [x[i,j] + x[i, j+1] == 0 for j in R5]

これらの制約はモデルに追加されないことに注意してください。どの制約が満たされているかどうかは気にしないため、満たされた制約の合計 (1 行あたり) が 3 未満であることだけが必要です。AS 制約はバイナリ変数に変換できます。これらの制約の合計が 3 未満であることを追加する必要があります。これは、多くても 3 つの制約が満たされることを意味します。このブロックの完全なコードは次のとおりです。

for i in R
   twozs = [x[i,j] + x[i, j+1] == 0 for j in R5]
   model.add(model.sum(twozs) <= 3)

同様の方法で、「2 つのセルが 1 に等しい」制約の 2 番目のブロックを修正する方法を簡単に理解できます。

ただし、最終モデルは解決しません。

実行不可能なモデルを調査するための、Docplex での 2 つの一般的なトリックを次に示します。

  1. 制約に名前を付ける
  2. リラクサー オブジェクトを使用して問題を緩和してみてください。リラクサーはいくつかの制約を緩和し、実現可能な解決策に到達するためにどの制約を緩和する必要があったかを示します。
    solution = model.solve()
    if solution is None:
        from docplex.mp.relaxer import Relaxer
        rx = Relaxer()
        rs = rx.relax(model)
        rx.print_information()

お役に立てれば。

于 2020-04-27T14:41:38.533 に答える
0

「連続する 1 0r 0 は 3 つまで」という制約の修正されたコード:

for i in r_rows:
    all_consecs = (x[i,j] == x[i,j+1] for j in range(n_cols-1))
    model.add(model.sum(all_consecs) <= 2, f"no_more_than_2_consecs_{i}")

ここでの主な関心点は、論理制約を式として使用する方法です。論理制約は true または false にすることができ、その真の値は実際には非表示のバイナリ変数に格納され、式で自由に使用できます (ここでは Model.sum() のように)。

于 2020-05-04T14:54:01.330 に答える