Добавление ограничения в оптимизацию линейного программирования с использованием PULP

Question

Следующий код дает мне лучшие места для отдыха, сохраняя при этом низкие расходы:

from pulp import *
import numpy as np
import pandas as pd
import re 

#write a scaper before hand
data = pd.read_csv('clymb_adventures.csv')
problem_name = 'GoingOnVacation'
aval_vacation_days = 10

def optimize_vacation_schedule(aval_vacation_days):

# create the LP object, set up as a minimization problem --> since we 
want to minimize the costs 
prob = pulp.LpProblem(problem_name, pulp.LpMinimize)


#create decision variables
decision_variables = []
for rownum, row in data.iterrows():
    variable = str('x' + str(rownum))
    variable = pulp.LpVariable(str(variable), lowBound = 0, upBound = 1, cat= 'Integer') #make variables binary
    decision_variables.append(variable)

print ("Total number of decision_variables: " + str(len(decision_variables)))

#create objective Function -minimize the costs for the trip
total_cost = ""
for rownum, row in data.iterrows():
    for i, schedule in enumerate(decision_variables):
        if rownum == i:
            formula = row['cost']*schedule
            total_cost += formula

prob += total_cost
print ("Optimization function: " + str(total_cost)) 


#create constrains - total vacation days should be no more than 14
total_vacation_days = ""
for rownum, row in data.iterrows():
    for i, schedule in enumerate(decision_variables):
        if rownum == i:
            formula = row['duration']*schedule
            total_vacation_days += formula

prob += (total_vacation_days == aval_vacation_days)


#now run optimization
optimization_result = prob.solve()
assert optimization_result == pulp.LpStatusOptimal
prob.writeLP(problem_name + ".lp" )
print("Status:", LpStatus[prob.status])
print("Optimal Solution to the problem: ", value(prob.objective))
print ("Individual decision_variables: ")
for v in prob.variables():
    print(v.name, "=", v.varValue)

if __name__ == "__main__":
    optimize_vacation_schedule(aval_vacation_days)

Образец набора данных:

destination duration    cost    description                 location
0   Baja          7      899    Hike Bike                [31223,23123]
1   Nepal         11     899    culture of the Himalayas [91223,28123]
2   Spain         8      568    Sport climb              [66223,23123]
3   Yosemite      3      150    Guided hiking            [0223,23123]
4   Utah          6      156    Hike.                    [35523,23123]
5   Okla          1      136    Hike.                    [25523,23123]

Я добавил дополнительное поле "местоположение" в наборе данных.

Чего я хочу достичь, так это, если решатель дает мне три 3 местоположения в качестве оптимального решения, то он должен убедиться, что максимальное манхэттенское расстояние между двумя последовательными предлагаемыми цитатами не превышает 3000 с использованием координат местоположения?

Пример: если solver предлагает Yosemite,Utah и Okla. Прежде чем предлагать их, он должен проверить, что расстояние от Yosemite до Utah меньше 3000, а Utah до Okla меньше 3000.

Это также делает это проблемой маршрутизации.

Так, как я могу добавить ограничение, которое сохраняет расстояние между двумя последовательно предложенными городами ниже 3000, используя координаты местоположения. Пожалуйста помоги

Спасибо!!!!

Answer 1

Если вы хотите добавить условие x(i,j) == 1 в качестве ограничения, вы должны создать второй набор переменных решения. Пусть ключ будет кортежем (i, j), а значением будет LpVariable с cat='Binary'. Затем вам нужно установить некоторые дополнительные ограничения.

ПРИМЕЧАНИЕ. Я предполагаю, что x - это словарь, где ключ - это местоположение, а значение - это переменная решения. Я не уверен, почему вы использовали здесь список. Потребуется некоторая модификация, чтобы соответствовать вашей структуре.

import itertools

locations = ['Baja', 'Nepal', 'Spain', ...]
x = LpVariable.dicts('x', destinations, cat='Binary'

prob = LpProblem('Vacation', pulp.LpMinimize)

# non-duplicative cominations
destination_pairs = itertools.combinations(locations, 2)

# new decision variables
# i is destination1, j is destination2
y = {(i, j): LpVariable('y', cat='Binary') for i, j in destination_pairs}

# new constraints
# if x[i] or x[j] is 0, then y[(i,j)] has to be zero
# if y[(i, j)] is 1, then x[i] and x[j] both have to be one
for i, j in destination_pairs:
    prob += y[(i, j)] <= x[i]
    prob += y[(i, j)] <= x[j]
    prob += y[(i,j] >= x[i] + x[j] - 1

# this ensures that a combination is chosen
prob += lpSum(y.values()) >= 1