Нахождение минимального значения функции с 11 390 625 комбинациями переменных - PullRequest
Новая
       42

Нахождение минимального значения функции с 11 390 625 комбинациями переменных

1 голос
/ 20 марта 2019

Я работаю над кодом, чтобы найти оптимальное сочетание диаметра и количества трубопроводов.Задача состоит в том, чтобы найти наименьшую сумму перепадов давления в шести трубопроводах.

Поскольку у меня есть 15 вариантов дискретных размеров диаметров, которые [2,4,6,8,12,16,20,24,30,36,40,42,50,60,80], которые могутдля любого из шести конвейеров, которые у меня есть в системе, список возможных решений становится 15 ^ 6, что равно 11 390 625

. Для решения этой проблемы я использую смешанное целочисленное линейное программирование с использованием Pulpпакет.Я могу найти решение для комбинации одинаковых диаметров (например, [2,2,2,2,2,2] или [4,4,4,4,4,4]), но мне нужно идтичерез все комбинации (например, [2,4,2,2,4,2] или [4,2,4,2,4,2], чтобы найти минимум. Я пытался сделать это, но процесс занимает очень много временивремя для прохождения всех комбинаций. Есть ли более быстрый способ сделать это?

Обратите внимание, что я не могу рассчитать падение давления для каждого трубопровода, так как выбор диаметра повлияет на общее падение давления в системе. Следовательно,в любое время мне нужно рассчитать перепад давления каждой комбинации в системе.

Мне также нужно ограничить проблему таким образом, чтобы скорость / сечение площади трубопровода> 2.

Вашпомощь очень ценится.

Первая попытка моего кода следующая: 

from pulp import * 
import random 
import itertools
import numpy

rate = 5000
numberOfPipelines = 15 

def pressure(diameter):
    diameterList = numpy.tile(diameter,numberOfPipelines)
    pressure = 0.0
    for pipeline in range(numberOfPipelines):
        pressure +=  rate/diameterList[pipeline]
    return pressure 
diameterList = [2,4,6,8,12,16,20,24,30,36,40,42,50,60,80]

pipelineIds = range(0,numberOfPipelines)
pipelinePressures = {} 

for diameter in diameterList: 
   pressures = [] 
   for pipeline in range(numberOfPipelines): 
      pressures.append(pressure(diameter))
   pressureList = dict(zip(pipelineIds,pressures))
   pipelinePressures[diameter] = pressureList 
   print 'pipepressure', pipelinePressures 
prob = LpProblem("Warehouse Allocation",LpMinimize)

use_diameter = LpVariable.dicts("UseDiameter", diameterList, cat=LpBinary) 
use_pipeline = LpVariable.dicts("UsePipeline", [(i,j) for i in pipelineIds for j in diameterList], cat = LpBinary)

## Objective Function: 
prob += lpSum(pipelinePressures[j][i] * use_pipeline[(i,j)] for i in pipelineIds for j in diameterList)

## At least each pipeline must be connected to a diameter: 
for i in pipelineIds: 
   prob += lpSum(use_pipeline[(i,j)] for j in diameterList) ==1 

## The diameter is activiated if at least one pipelines is assigned to it: 
for j in diameterList: 
  for i in pipelineIds: 
     prob += use_diameter[j] >= lpSum(use_pipeline[(i,j)])


## run the solution

prob.solve()
print("Status:", LpStatus[prob.status])

for i in diameterList:
    if use_diameter[i].varValue> pressureTest:
        print("Diameter Size",i)

for v in prob.variables():
    print(v.name,"=",v.varValue)

Это то, что я сделал для комбинированной части, которая заняла очень много времени. 

xList = np.array(list(itertools.product(diameterList,repeat = numberOfPipelines)))
        print len(xList)
        for combination in xList:
            pressures = [] 
            for pipeline in range(numberOfPipelines):
               pressures.append(pressure(combination))
            pressureList = dict(zip(pipelineIds,pressures))
            pipelinePressures[combination] = pressureList
            print 'pipelinePressures',pipelinePressures

1 Ответ

2 голосов
/ 21 марта 2019

Я бы перебрал все комбинации, думаю, у вас возникли бы проблемы с памятью, в противном случае вы пытались бы смоделировать ВСЕ комбинации в MIP.

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

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

...