在 Gurobi 中正确制定约束 Python

Question

我正在使用带有 gurobi 的 python IDE 来建模和解决作业问题。这个问题虽然没有说明，但似乎是一个 OVRP（开放式车辆路由问题）（有一些额外的限制）。我现在的代码是：

from itertools import combinations
import gurobipy as gp
from gurobipy import GRB

def find_length(list):
    length = 0
    for i in range(len(list)):
        length += distances[list[i][0]][list[i][1]]
    return length


def find_tours(list):
    tours = []
    for start in list:
        this_tour = []
        begin = start[0]
        end = start[1]
        if begin == 0:

            this_tour.append(start)
            current = start
            while next_route_exists(current, list):
                current = find_next_route(current, list)
                this_tour.append(current)

            tours.append(this_tour)
    return tours


def find_next_route(current_route, list):
    end = current_route[1]
    for tuple in list:
        if tuple[0] == end:
            list.remove(tuple)
            return tuple


def next_route_exists(current_route, list):
    end = current_route[1]
    for tuple in list:
        if tuple[0] == end:
            return True
    return False


def subtourelim(model, where):
    if where == GRB.Callback.MIPSOL:
        # make a list of edges selected in the solution
        vals = model.cbGetSolution(model._vars)
        selected = gp.tuplelist((i, j) for i, j in model._vars.keys() if vals[i, j] > 0.5)

        tours = find_tours(selected)
        for tour in tours:
            if find_length(tour) > 400:
                # add subtour elimination constr. for every pair of cities in tour
                model.cbLazy(gp.quicksum(distances[i][j] for i, j in tour) <= 400)


# Distances between cities

distances = [[0, 180, 240, 85, 285, 205, 235, 255, 155, 120, 230, 340, 220, 160, 240],  # Α
             [0, 0, 255, 150, 125, 100, 175, 235, 25, 65, 95, 210, 55, 135, 215],  # Β1
             [0, 0, 0, 160, 235, 160, 105, 45, 245, 255, 195, 225, 310, 115, 50],  # Β2
             [0, 0, 0, 0, 215, 125, 150, 170, 130, 110, 160, 260, 200, 75, 150],  # Β3
             [0, 0, 0, 0, 0, 90, 130, 195, 150, 190, 50, 85, 155, 155, 185],  # Β4
             [0, 0, 0, 0, 0, 0, 70, 135, 110, 135, 40, 135, 155, 65, 120],  # Β5
             [0, 0, 0, 0, 0, 0, 0, 70, 175, 200, 95, 125, 225, 70, 55],  # Β6
             [0, 0, 0, 0, 0, 0, 0, 0, 235, 250, 165, 180, 290, 110, 20],  # Β7
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 40, 110, 225, 70, 130, 215],  # Β8
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 145, 265, 100, 135, 230],  # Β9
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 115, 135, 105, 150],  # Β10
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 240, 185, 175],  # Β11
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 190, 270],  # Β12
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 90],  # Β13
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]  # B14

n = 15
for i in range(n):
    for j in range(n):
        if j > i:
            distances[j][i] = distances[i][j]

dist = {(i, j): distances[i][j] for i in range(n) for j in range(n)}
m = gp.Model()

vars = m.addVars(dist.keys(), obj=dist, vtype=GRB.BINARY, name='route')

m.addConstrs(vars.sum(i, '*') <= 1 for i in range(1, n))  # a city might be the departure
m.addConstrs(vars.sum('*', i) == 1 for i in range(1, n))  # every city must be the destination

m.addConstr(vars.sum(0, '*') >= 1, "start")  # could have more than 1 vehicles
m.addConstr(vars.sum('*', 0) == 0)  # can't go back to start
m.addConstr(vars.sum(0, '*') <= 8, "start")  # can't have more than 8 vehicle

m.addConstrs(vars[i, i] == 0 for i in range(1, n))  # can't go to  current city from current city
m.addConstrs(vars[i, j] + vars[j, i] <= 1 for i in range(1, n) for j in range(1, n) if  j != i)  # eliminate double edges between cities

route_km = vars.prod(dist)
m.addConstr(route_km <= 400 * vars.sum(0, '*'))  # total km driven




# total vehicles used

total_vehicles = vars.sum(0, '*')
m.setObjective(total_vehicles, GRB.MINIMIZE)

# optimize model

m._vars = vars
m.Params.lazyConstraints = 1
m.optimize(subtourelim)
#m.optimize()

# get edges

vals = m.getAttr('x', vars)
selected = gp.tuplelist((i, j) for i, j in vals.keys() if vals[i, j] > 0.5)
print('')
tours = find_tours(selected)

i = 0
total=0
for tour in tours:
    i += 1
    print('Tour No ' + str(i) + ':')
    print(tour)
    print('is ' + str(find_length(tour)) + ' km long')
    print('')
    total+=find_length(tour)
print('Total : ' + str(total) + ' km')

我现在遇到的问题是，由于我是 gurobi 的新手，我无法表达我想要正确添加的约束，这导致出现错误的解决方案。问题在于此约束：

route_km = vars.prod(dist)
m.addConstr(route_km <= 400 * vars.sum(0, '*'))  # total km driven

这是错误的。我想添加一个约束条件，即每辆卡车最多可以行驶 400 公里。如果选择了另一个“城市”，则一旦行驶了该距离或无法行驶，就必须部署新卡车（卡车总数为 8，如约束中所述）。如果制定了这个约束，我相信我也可以消除这个惰性约束：

tours = find_tours(selected)
for tour in tours:
    if find_length(tour) > 400:
        # add subtour elimination constr. for every pair of cities in tour
        model.cbLazy(gp.quicksum(distances[i][j] for i, j in tour) <= 400)

提前感谢您的帮助，

乔治

Answer 1

惰性约束最适合具有相对大量约束的模型。例如，在旅行商问题的传统 MIP 模型中，subtour 消除约束的数量是指数级的，因此添加这些作为惰性约束是有意义的。

您似乎希望根据总行驶距离限制卡车的容量。在 HP Williams 的书中 Model Building in Mathematical Programming, the Lost baggage example is quite similar; here is a link to a Jupiter notebook for this example on the Gurobi website.

在 Gurobi 中正确制定约束 Python

Correctly formulate a constraint in Gurobi Python

python

operations-research

gurobi