Optimization problem in Python

问题:

I need to solve a problem. I have 5 devices. They all have 4 kind of I/O types. And there is a target input/output combination. At first step, I want to find all combinations among the devices so that the total I/O number of selected devices are all equal or greater than the target values. Let me explain:

# Devices=[numberof_AI,numberof_AO,numberof_BI,numberof_BO,price]

Device1=[8,8,4,4,200]
Device1=[16,0,16,0,250]
Device1=[8,0,4,4,300]
Device1=[16,8,4,4,300]
Device1=[8,8,2,2,150]

Target=[24,12,16,8]

There are constraints as well. In combinations, max. number of devices can be 5 at most.

At the second step, among the combinations found, I will pick the cheapest one.

Actually, I managed to solve this problem with for loops in Python. I works like a charm. But it takes too much time even though I use cython.

What other options can I benefit from for this kind of problem?

回答1:

You can use a linear programming package like PuLP. (note this also requires you to install an LP library like GLPK).

Here's how you would use it to solve the example you gave:

import pulp

prob = pulp.LpProblem("example", pulp.LpMinimize)

# Variable represent number of times device i is used
n1 = pulp.LpVariable("n1", 0, 5, cat="Integer")
n2 = pulp.LpVariable("n2", 0, 5, cat="Integer")
n3 = pulp.LpVariable("n3", 0, 5, cat="Integer")
n4 = pulp.LpVariable("n4", 0, 5, cat="Integer")
n5 = pulp.LpVariable("n5", 0, 5, cat="Integer")

# Device params
Device1=[8,8,4,4,200]
Device2=[16,0,16,0,250]
Device3=[8,0,4,4,300]
Device4=[16,8,4,4,300]
Device5=[8,8,2,2,150]

# The objective function that we want to minimize: the total cost
prob += n1 * Device1[-1] + n2 * Device2[-1] + n3 * Device3[-1] + n4 * Device4[-1] + n5 * Device5[-1]

# Constraint that we use no more than 5 devices
prob += n1 + n2 + n3 + n4 + n5 <= 5

Target = [24, 12, 16, 8]

# Constraint that the total I/O for all devices exceeds the target
for i in range(4):
    prob += n1 * Device1[i] + n2 * Device2[i] + n3 * Device3[i] + n4 * Device4[i] + n5 * Device5[i] >= Target[i]

# Actually solve the problem, this calls GLPK so you need it installed
pulp.GLPK().solve(prob)

# Print out the results
for v in prob.variables():
    print v.name, "=", v.varValue

Running this is extremely fast, and I get that n1 = 2 and n2 = 1 and the others are 0.

回答2:

Just check all combinations. As you have just 5 devices, that makes (at most) 6^5=7776 possibilities (since each of the five positions might be unused you have to use 6). Then for each possibility, you check whether it fulfils your criteria. I don't see why this should take so much time.

The following script takes not a second on my machine to compute the stuff.

d1=[8,8,4,4,200]
d2=[16,0,16,0,250]
d3=[8,0,4,4,300]
d4=[16,8,4,4,300]
d5=[8,8,2,2,150]
dummy=[0,0,0,0,0]

t=[24,12,16,8]

import itertools
def computeit(devicelist, target):
    def check(d, t):
        for i in range(len(t)):
            if sum([dd[i] for dd in d]) < t[i]:
                return False
        return True
    results=[]
    for p in itertools.combinations_with_replacement(devicelist, 5):
        if check(p, t):
            results.append(p)
    return results

print(computeit([d1,d2,d3,d4,d5,dummy],t))

Requires Python 2.7.

回答3:

One could also solve this problem using the Python Constraint module by Gustavo Niemeyer.

import constraint

Device1=[8,8,4,4,200]
Device2=[16,0,16,0,250]
Device3=[8,0,4,4,300]
Device4=[16,8,4,4,300]
Device5=[8,8,2,2,150]

Target=[24,12,16,8]

devices = [Device1, Device2, Device3, Device4, Device5]
vars_number_of_devices = range(len(devices))
max_number_of_devices = 5

problem = constraint.Problem()
problem.addVariables(vars_number_of_devices, range(max_number_of_devices + 1))
problem.addConstraint(constraint.MaxSumConstraint(max_number_of_devices), vars_number_of_devices)
for io_index, minimum_sum in enumerate(Target):
    problem.addConstraint(constraint.MinSumConstraint(minimum_sum, [device[io_index] for device in devices]), vars_number_of_devices)

print min(problem.getSolutions(), key=lambda distribution: sum([how_many * devices[device][-1] for device, how_many in distribution.iteritems()]))

This produces the following output:

{0: 2, 1: 1, 2: 0, 3: 0, 4: 0}

Thus, the optimal solution is 2 x Device1, 1 x Device2, 0 x Device3, 0 x Device4, 0 x Device5.

(Note that the variables are named using zero-based indexing. Device1 corresponds to 0, Device2 corresponds to 1, and so on.)