Как использовать индексы и импортировать данные для математической оптимизации Python PuLP

Раньше я использовал средства моделирования оптимизации, но прошло какое-то время, и я все еще учусь делать это на python. Я провел небольшое онлайн-исследование и использую версию PuLp с открытым исходным кодом https://pythonhosted.org/PuLP/ < / а>

Я сформулировал следующее и работаю в трех местах. Мои вопросы заключаются в том, как сформулировать проблему с импортированными данными из CSV, поскольку мой набор данных фактически включает 70 местоположений. Было бы глупо вводить количество возможных маршрутов к этим маршрутам; Я полагаю, что есть способ лучше запрограммировать это. Я понимаю, как использовать csv.reader (), но не уверен, как продолжить формулировку проблемы.

Пример модели:

"""
Traveling Salesman Problem (TSP) Simplified Model
Date: 2017-03-30
"""

# Import PuLP modeler functions
from pulp import *

# Create the 'prob' variable to contain the problem data
prob = LpProblem("The TSP Problem1",LpMinimize)

# Formulation summary
#   The decision variable x is equal to 1 or 0, whether the path is chosen
#   Each path has a cost associated with it
#   The objective is to choose the shortest path
#   The constraint, essentially, is that each location is visited

# The LpVariable class has four parameters
    # the first is an arbitrary name
    # the second is the lower bound
    # the third is the upper bound
    # the fourth is the type of data, discrete or continuous
x12=LpVariable("flow12",0,None,LpInteger)
x13=LpVariable("flow13",0,None,LpInteger)
x21=LpVariable("flow21",0,None,LpInteger)
x23=LpVariable("flow23",0,None,LpInteger)
x31=LpVariable("flow31",0,None,LpInteger)
x32=LpVariable("flow32",0,None,LpInteger)

# The objective function is added to 'prob' first
# the objective is to minimize the total distance traveled 
# the numbers represent the distances between two variables

prob += 30*x12 + 5*x13 +25*x21 + 1*x23 + 5*x31 + 8*x32, "Total Distance Traveled"


# The constraints: 

# each location needs to be on the route but only once
prob += x12 + x32 == 1.0, "Location2 is visited"
prob += x13 + x23 == 1.0, "Location3 is visited"
prob += x21 + x31 == 1.0, "Location1 is visited"

# each location is departed exactly once
prob += x31 + x32 == 1.0, "Location3 is departed"
prob += x21 + x23 == 1.0, "Location2 is departed"
prob += x12 + x13 == 1.0, "Location is departed"

# The problem data is written to an .lp file
prob.writeLP("SupplyChainAssignment.lp")

# The problem is solved using PuLP's choice of Solver
prob.solve()

# The status of the solution is printed to the screen
print "Status:", LpStatus[prob.status]

# Each of the variables is printed with it's resolved optimum value
for v in prob.variables():
    print v.name, "=", v.varValue

# The optimized objective function value is printed to the screen
print "Total Cost TSP Assignment = ", value(prob.objective)

Это конец примера, который в настоящее время работает.

Я думаю, что могу использовать следующие словари для определения расстояния:

distance = {'x12': 30,
            'x13': 5,
            'x21': 25,
            'x23': 1, 
            'x31': 5,
            'x32': 8}

Но я не уверен, что для переменных будет работать следующее:

x = {'x12',
     'x13', 
     'x21',
     'x23', 
     'x31',
     'x32'}

x=LpVariable("flow",0,1,LpInteger)

И это также не решает мой вопрос о том, как переписать ограничения с использованием индексов, поэтому я не проверял, сработает ли мое предположение о синтаксисе выше:

prob += x12 + x32 == 1.0, "Location2 is visited"
prob += x13 + x23 == 1.0, "Location3 is visited"
prob += x21 + x31 == 1.0, "Location1 is visited"

# each location is departed
prob += x31 + x32 == 1.0, "Location3 is departed"
prob += x21 + x23 == 1.0, "Location2 is departed"
prob += x12 + x13 == 1.0, "Location is departed"

Любые предложения о том, что я должен прочитать, или если есть какие-либо примеры, на которые вы могли бы указать мне, были бы полезны.

Спасибо!


person windyvation    schedule 30.03.2017    source источник


Ответы (1)


Прочтите еще немного документации, и вы увидите несколько хороших примеров.

https://pythonhosted.org/PuLP/CaseStudies/a_blending_problem.html#solution-to-full-problem

Из этого документа вы увидите следующее


# A dictionary called 'ingredient_vars' is created to contain the referenced Variables
ingredient_vars = LpVariable.dicts("Ingr",Ingredients,0)

Поскольку затраты и ингредиенты_вары теперь являются словарями со ссылочными ключами в качестве имен ингредиентов, данные могут быть просто извлечены с помощью списка, как показано. Функция lpSum () добавит элементы полученного списка. Таким образом, целевая функция просто вводится и ей присваивается имя:

# The objective function is added to 'prob' first
prob += lpSum([costs[i]*ingredient_vars[i] for i in Ingredients]), "Total Cost of Ingredients per can"

Дальнейшие понимания списков используются для определения других 5 ограничений, каждое из которых также имеет имена, описывающие их.

# The five constraints are added to 'prob'
prob += lpSum([ingredient_vars[i] for i in Ingredients]) == 100, "PercentagesSum"
prob += lpSum([proteinPercent[i] * ingredient_vars[i] for i in Ingredients]) >= 8.0, "ProteinRequirement"
prob += lpSum([fatPercent[i] * ingredient_vars[i] for i in Ingredients]) >= 6.0, "FatRequirement"
prob += lpSum([fibrePercent[i] * ingredient_vars[i] for i in Ingredients]) <= 2.0, "FibreRequirement"
prob += lpSum([saltPercent[i] * ingredient_vars[i] for i in Ingredients]) <= 0.4, "SaltRequirement"

В этом примере вы можете увидеть, как определить проблему с помощью словарей переменных и словарей параметров.

Затем вам нужно будет использовать модуль csv для чтения данных параметров (я бы порекомендовал csv.DictReader для этого)

Но вы правы, было бы неплохо иметь конкретный пример в документации.

person Stuart Mitchell    schedule 31.03.2017
comment
Я уже прочитал все на этом сайте, включая ссылку / пример в этой ссылке. Однако это не решило мой вопрос о синтаксисе Python для модели LP при импорте данных. - person windyvation; 31.03.2017