Как решить 3D мультибиновую упаковку с помощью OpenOpt

Я изучаю оптимизацию и новичок в OpenOpt.

Я хотел бы представить процессы, каждый из которых имеет 3 индикатора использования ресурсов (ЦП, память и сеть), и я хотел бы назначить N процессов на группы/бины в соответствии со следующими ограничениями:

sum(cpu) within a group < 100
sum(mem) within a group < 100
sum(net) within a group < 100
Minimize(number of groups) or maximize the sum of each resource within a group.

В идеале я хотел бы иметь такой тип вывода:

VM 1 assigned to group 1
VM 2 assigned to group 1
VM 3 assigned to group 1
VM 4 assigned to group 2
VM 5 assigned to group 2
VM 6 assigned to group 3
... and so on

Вопрос: Как я могу это сделать? Если это невозможно сделать с помощью OpenOpt, есть ли какая-либо другая библиотека, которая могла бы помочь мне в этом?

Вот мой исходный код: https://github.com/vonpupp/mdbp/blob/master/ksp_2.py

Большое спасибо!


python bin-packing mathematical-optimization
person Albert Vonpupp    schedule 09.10.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

Вот как создаются предметы:

def gen_vms():
    tg = tracegen.TraceGenerator()
    trace = tg.gen_trace()
    items = [{
                  'name': 'item %d' % i,
                  'weight': 1,
                  'cpu': t[0],
                  'mem': t[1],
                  'disk': t[2],
                  'net': t[3],
                  'n': 1
             } for i,t in islice(enumerate(trace), 200)]
    return items

И вот как создаются ограничения:

def add_constraint(values, constraint):
    return values[constraint] < 99

def add_constraints(values, constraint_list):
    return [add_constraint(values, constraint) for constraint in constraint_list]

def gen_costraints(constraint_list):
    global constraints
    constraints = lambda values: (add_constraints(values, constraint_list))

Процесс решения такой:

def solve_host():
    global items
    global constraints
    p = KSP('weight', list(items), constraints = constraints)
    result = p.solve('glpk', iprint = -1)

Более подробную информацию о том, как это сделать, можно найти здесь: https://github.com/vonpupp/2013-sbrc-experiments/blob/e2e8a2be320c8f77d67a5bc6bb822510564e80f3/myksp_oo.py

person Albert Vonpupp    schedule 12.12.2013
comment
откуда в вашей сути lib.tracegen.tracegen? - person JohnO; 17.02.2014
comment
Вы можете просматривать код из этого конкретного коммита прямо на github (это не суть, это полный репозиторий). Если вы ищете файл tracegen.py, вы можете найти его здесь: github.com/vonpupp/2013-sbrc-experiments/blob/ - person Albert Vonpupp; 17.02.2014