การสร้างแบบจำลอง Python สำหรับ ILP Minimum Dominating Set (MDS)

Question

ฉันกำลังเขียนโค้ดสำหรับแก้ปัญหาMDSปัญหาคือ:\begin{align}\min&\quad\sum_{v\in V}y_v\\\text{s.t.}&\quad y_v+\sum_{(u,v)\in E}y_u\ge1\quad\forall v\in V\\&\quad y_v\in\{0,1\}\quad\forall v\in V.\end{align}

ฉันใช้Pulpและnx.networkใน python เพื่อจำลองปัญหาดังต่อไปนี้:

• ปัญหา prob = pulp.LpProblem("MinimumDominatingSet", pulp.LpMinimize)
• ตัวแปร y = pulp.LpVariable.dicts("y", g.nodes(), cat=pulp.LpBinary)
• วัตถุประสงค์ for (v,u) in g.edges(): prob += pulp.lpSum(y)
• ข้อ จำกัด for (v,u) in g.edges(): prob += y.get(v) + sum(y.get(u) for (v,u) in g.edges) >= 1

ฉันได้ลองทดสอบผลลัพธ์ด้วยรูปดาวง่ายๆ ขออภัยผลลัพธ์ไม่ถูกต้อง ฉันสงสัยว่าอาจมีปัญหากับการสร้างแบบจำลองข้อ จำกัด

ใครช่วยแนะนำฉันผ่านสิ่งนี้ได้ไหม

Answer 1

วัตถุประสงค์ของคุณควรเป็นprob+= pulp.lpSum(y)และข้อ จำกัด ควรเป็น:

for v in g.nodes():
       prob += y[v] + pulp.lpSum([y[u] for u in g.neighbors(v)]) >= 1