主页 / coding / 问题 / 77937790
Accepted
Ryan
Asked: 2024-02-05 06:13:49 +0800 CST

用 pyomo 制定邻接约束时卡住了

  • 772

我试图attributes根据邻接约束分配到 3 x 3 矩阵，但我一直在制定邻接约束。我一直以为我已经得到了答案，但当我尝试时，结果却并不如预期。

因此，elements 被预先排列成element_map9 x 17 矩阵。每个 9element都有 17 attributes，它们始终为零或一。

selement在 3 x 3 矩阵中处于固定位置：

[[0, 3, 6
  1, 4, 7
  2, 5, 8]]

例如，中的elementat 索引固定在 3 x 3 矩阵中的位置。并且毗邻.2element_map(2,0)(2,0)(1,0), (1,1), (2,1)

限制条件是：

  1. 每个place最多可以attribute分配 4 个（完成）
  2. 每个place必须attributes分配一个或多个（完成）
  3. attribute每个选定的splace必须等于零（完成）
  4. 邻接约束：下面用一个例子解释（需要帮助）
import pyomo.environ as pyo
import numpy as np


"""
fit elements into matrix based on adjacency rules
"""


class Element:

    """a convenience to hold the rows of attribute values"""
    def __init__(self, row):
        self.attributes = tuple(row)

    def attribute(self, idx):
        return self.attributes[idx]

    def __repr__(self):
        return str(self.attributes)


class Position:
 
    """a convenience for (x, y) positions that must have equality & hash defined for consistency"""
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return f'({self.x}, {self.y})'

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        if isinstance(other, Position):
            return (self.x, self.y) == (other.x, other.y)
        return False

# each 'row' corresponds to an element
# each 'column' corresponds to an attribute of the various elements
# here, each element has attributes which are always 0 or 1
element_map = np.array([[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0],
                        [1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1],
                        [0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1],
                        [0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
                        [1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
                        [1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
                        [0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
                        [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
                        [1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1]])



print(element_map, 'map')
print (element_map.shape)

matrix_a_rows = 3
matrix_a_cols = 3
matrix_a = np.zeros((matrix_a_rows, matrix_a_cols))

mask = np.arange(1,(matrix_a_rows*matrix_a_cols)+1).reshape(matrix_a_cols, matrix_a_rows).T


def get_element(position):
    #get the element vector at a position
    x,y =position.x, position.y
    idx = mask[x,y]-1
    return idx #return 0-indexed element idx

def adj_xy(mat, p: Position):
    x, y = p.x, p.y
    res = []
    rows = len(mat) - 1
    cols = len(mat[0]) - 1
    for i in range(x - 1, x + 2):
        for j in range(y - 1, y + 2):
            if all((0 <= i <= rows, 0 <= j <= cols, (i, j) != (x, y))):
                res.append(Position(i, j))
    return res

# SET UP ILP
m = pyo.ConcreteModel('matrix_fitter')

# SETS

elements = np.array([np.array(row) for row in element_map])


m.P = pyo.Set(initialize=[Position(x, y) for x in range(len(matrix_a)) for y in range(len(matrix_a[0]))],
              doc='positions')

m.A = pyo.Set(initialize=list(range(len(element_map[0]))), doc='attribute')

    
# VARS
# place element e in position p based on attribute a being 0...
m.place = pyo.Var(m.P, m.A, domain=pyo.Binary, doc='place')

# OBJ:  minimize attributes assigned to each position
m.obj = pyo.Objective(expr=pyo.sum_product(m.place), sense=pyo.minimize)

#each place must have 4 or fewer attributes assigned to it
m.attr_constraint = pyo.ConstraintList()
for p in m.P:
    s = 0
    for a in m.A:
        s += m.place[p,a]
    m.attr_constraint.add(s <= 4)

#each place must have one or more attributes assigned to it
m.enzyme_constraint = pyo.ConstraintList()
for p in m.P:
    s = 0
    for a in m.A:
        s += m.place[p,a]
    m.attr_constraint.add(s >= 1)


#the selected attribute for each position must be equal to zero 
m.cut_constraint = pyo.ConstraintList()
for p in m.P:
    e_idx = get_element(p)
    element = elements[e_idx]
    for i,a in enumerate(m.A):
        if element[i] == 1:
            m.cut_constraint.add(m.place[p,a] == 0)

#adjacency constraint
#doesn't work as expected
#This is where I need help...
m.adjacency_constraint = pyo.ConstraintList()
for p in m.P:
    plate_element = elements[get_element(p)]
    neighbor_positions = adj_xy(matrix_a, p)
    print (p, 'place')
    for i,a in enumerate(m.A):
        s = 0
        for j,aa in enumerate(m.A):
            for neighbor in neighbor_positions:
                neighbor_element = elements[get_element(neighbor)]
                neighbor_element_attribute = neighbor_element[i]
                s += m.place[neighbor,aa]*neighbor_element_attribute


        m.adjacency_constraint.add(s >= len(neighbor_positions)*m.place[p,a])


solver = pyo.SolverFactory('cbc')

results = solver.solve(m, tee=True)

print(results, 'results')
if results.solver.termination_condition == pyo.TerminationCondition.optimal:
    for idx in m.place.index_set():
        if m.place[idx].value == 1:
            s = 0
            att = idx[1]
            
            neighs = adj_xy(matrix_a, idx[0])
            for i in neighs:
                place_element = elements[get_element(i)]
                s += place_element[att]

            print(idx, 'idx', s)
    if pyo.value(m.obj) == matrix_a_rows * matrix_a_cols:
        # all positions were filled
        print('success!')
    else:
        print(f'the number of elements that can be placed is {pyo.value(m.obj)} / {matrix_a_rows * matrix_a_cols}')

else:
    print('Problem with model...see results')
print (element_map)

看起来element_map像这样：

[[0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0]
 [1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 1]
 [0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1]
 [0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1]
 [1 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1]
 [1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1]
 [0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1]
 [0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1]
 [1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1]]

...我得到的结果是：

((0, 0), 0) idx 2 
((0, 0), 1) idx 2 
((0, 0), 9) idx 2 
((0, 0), 16) idx 3
((0, 1), 5) idx 2 
((0, 1), 6) idx 2 
((0, 1), 9) idx 4 
((0, 2), 3) idx 2 
((1, 0), 1) idx 2 
((1, 0), 5) idx 2 
((1, 1), 4) idx 7 
((1, 1), 15) idx 4
((1, 2), 1) idx 2 
((2, 0), 0) idx 3 
((2, 1), 3) idx 4 
((2, 2), 7) idx 2

格式为：((x,y), selected_attribute). (x,y)是 3 x 3 矩阵中的坐标，并且是为此selected_attribute选定的 s 之一。attributeplace

例子

让我们考虑elementat (1,1)，因为它与所有其他 相邻places。这方面的数据element是：

[1 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1]

结果中选定的attributes是和。对此，查看,是一个不错的选择，因为除了倒数第二个之外，所有的值都为。然而，另一个选定的, , 不好，因为倒数第二个元素的at 索引为零。对于at ，将与以下索引结合使用：，因为对于倒数第二个，这些值都是。(1,1)415element_mapattribute 4elementelement1attributeattribute15attribute15element(1,1)attribute 4attribute3 or 9 or 16elementattribute1

邻接约束定义

因此邻接约束应该是：将attributes 分配给 a place，使得所有相邻的places 至少具有1所有选定attributes 中的一个值。这是一个最小化问题，所以总的来说，我希望attribute分配给每个place满足约束的最小数量的 s 。

我希望这是清楚的，如果有什么我可以澄清的，请发表评论；谢谢阅读！

python

1 个回答

  1. Best Answer

    你需要几个组件......

    首先，您需要一个索引列表，其中包含与每个地点相邻的地点。如果您使用单位数字索引系统，则类似于：

    neighbors = { 0: [1, 3, 4], 1: [0, 3, 4, 5, 2], ...}

    这些指数将成为确保覆盖范围的约束求和的基础。类似于伪代码/未经测试的内容：

    def cover(model, base, neighbor):
    return sum(model.place[base, a] * element_map[neighbor, a] for a in attributes) >= 1

# make some flat list of all the possible base-neighbor combos...
bn = [(b, n) for b in neighbors for n in neighbors[b] ]

model.neighbor_coverage = pyo.Constraint(bn, rule=cover)

    基本上指出，对于每个基本邻居组合，您必须选择一些place可以生成覆盖范围的属性。

    尝试看看是否可以旋转。如果卡住了，评论回来！

    • 1

相关问题