在 Gurobi 中添加大小为 n 的二进制变量

Question

我正尝试在 Gurobi（Python 界面）中实施设施位置优化模型。我在翻译模型时遇到了一些困难。数学模型如下图：

其中 dloc,floc 是需求（客户）和设施（仓库）位置的 (x,y) 坐标。 dloc 数量是常数（即 50），与作为决策变量的 floc 相反：这些由求解器计算。另外，x,y 坐标是 0 到 100 之间的浮点数。

其中一个关键问题是我不知道如何添加设施变量，设施变量的数量可以是0到n之间的任意值。

到目前为止我的代码：

from gurobipy import *
import numpy as np
import math


def distance(a, b):
    dx = a[0] - b[0]
    dy = a[1] - b[1]
    return math.sqrt(dx ** 2 + dy ** 2)

customer = np.random.uniform(0,100,[50,2])
print(customer)

m = Model()

n = m.addVar(lb=0.0, ub=GRB.INFINITY,vtype=GRB.INTEGER) #number of candidate facilities

facility={}
for j in range(n):
    facility[j] = m.addVar(vtype=GRB.BINARY, name="facility%d" % j) #certainly this is not correct, as an error is reported as 'Var' object cannot be interpreted as an integer

floc = ?

所以我尝试了另一种方法，通过手动设置固定数量的候选设施作为临时解决方法：

from gurobipy import *
import numpy as np
import math

customer = np.random.uniform(0,100,[50,2])
print(customer)

m = Model()

###Variable
dc={}
x={}
y={}
assign={}

for j in range(10):
    dc[j] = m.addVar(lb=0,ub=1,vtype=GRB.BINARY, name="DC%d" % j)
    x[j]= m.addVar(lb=0, ub=100, vtype=GRB.CONTINUOUS, name="x%d")
    y[j] = m.addVar(lb=0, ub=100, vtype=GRB.CONTINUOUS, name="y%d")
for i in range(len(customer)):

    for j in range(len(dc)):
        assign[(i,j)] = m.addVar(lb=0,ub=1,vtype=GRB.BINARY, name="Cu%d from DC%d" % (i,j))

###Constraint
for i in range(len(customer)):
    for j in range(len(dc)):
        m.addConstr(((customer[i][0] - x[j])*(customer[i][0] - x[j]) +\
                              (customer[i][1] - y[j])*(customer[i][1] - y[j])) <= 40*40 + 100*100*(1-assign[(i,j)]))

for i in range(len(customer)):
    m.addConstr(quicksum(assign[(i,j)] for j in range(len(dc))) == 1)

for i in range(len(customer)):
    for j in range(len(dc)):
        m.addConstr(assign[(i, j)] <= dc[j])

n=0
for j in dc:
    n=n+dc[j]

m.setObjective(n,GRB.MINIMIZE)

m.optimize()

print('\nOptimal Solution is: %g' % m.objVal)
for v in m.getVars():
    print('%s %g' % (v.varName, v.x))

任何人都可以在 Gurobi 中演示模型的翻译，这将很有帮助。

Answer 1

我认为您对 n 的定义没有问题。尽管如此，我还是重写了您的代码，以使其不那么冗长且更易于理解。首先我们创建给定的集合和常量：

from gurobipy import Model, GRB, quicksum
import numpy as np

m = Model()

demo_coords = np.random.uniform(0, 100, size=(50, 2)) # Just for demonstration

# Sets and Constants
demand = [f"i{k}" for k in range(1, 51)]
facilities = [ f"facility{k}" for k in range(1, 11) ]
dloc = {fac : demo_coords[i] for i, fac in enumerate(demand)}
maxdist = 40
M = 10e6

请注意，dloc 是一个字典，因此 dloc[i] 将为您提供坐标对于需求点 i。那么 dloc[i][0] 是 x 坐标， dloc[i][1] 是 y 坐标。

现在我们可以创建变量并将它们存储在 gurobi tubledict:

# Variables
floc = m.addVars(facilities, 2, name="floc")
isopen = m.addVars(facilities, vtype=GRB.BINARY, name="isopen")
assign = m.addVars(demand, facilities, vtype=GRB.BINARY, name="assign")
n = m.addVar(vtype=GRB.INTEGER, name="n")
m.update()

使用m.addConstrs()，约束可以写成

# Constraints
m.addConstrs(((dloc[i][0] - floc[j, 0]) * (dloc[i][0] - floc[j, 0]) \
    + (dloc[i][1] - floc[j, 1])*(dloc[i][1] - floc[j, 1]) \
    <= maxdist**2 + M * (1 - assign[i, j]) \
    for i in demand for j in facilities), name="distance")

m.addConstrs((quicksum(assign[i, j] for j in facilities) == 1\
              for i in demand), name="assignDemand")

m.addConstrs((assign[i, j] <= isopen[j] for i in demand for j in facilities),\
name="closed")

m.addConstr(n == quicksum(isopen[j] for j in facilities), name="numFacilities")

# zip is needed to iterate over all pairs of consecutive facilites
m.addConstrs((isopen[j] >= isopen[jp1] \
    for j, jp1 in zip(facilities, facilities[1:])), name="order")

请注意，虽然在距离约束中写 floc[j, 0] 不是问题，但您不能写 dloc[i, 0]，因为 dloc 是 python 字典和 floc 是一个元组字典。

正在设置 objective 函数并调用 m.optimize()

# Objective
m.setObjective(n, sense=GRB.MINIMIZE)

m.optimize()

if m.status == GRB.OPTIMAL:
    print(f"Optimal Solution is: {m.objVal}")
    print("--------------")
    for var in m.getVars():
        print(var.varName, var.X)

给我最优解 n = 3。

在 Gurobi 中添加大小为 n 的二进制变量

Add binary variable with size n in Gurobi

python

gurobi