Python optimization problem

Question

I need to solve a problem. I have 5 devices. All of them have 4 types of input-output types. And there is a target I / O combination. At the first stage, I want to find all the combinations between the devices so that the total I / O number of the selected devices is equal to or more 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 also limitations. In combinations, max. the number of devices can be no more than 5.

In the second stage, among the combinations found, I will choose the cheapest.

I actually managed to solve this problem using loops in Python. I work like a charm. But it takes too much time, although I use cython.

What other options can I learn from this problem?

Answer 1

, PuLP. ( , LP, GLPK).

, :

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

, , n1 = 2 n2 = 1, - 0.

Answer 2

. 5 , ( ) 6^5=7776 ( , 6). , . , .

script , .

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))

Python 2.7.

Answer 3

You can also solve this problem using the Python Constraint module from 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 leads to the following conclusion:

{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 variables are called using zero-based indexing. Device1 corresponds to 0, Device2 corresponds to 1, etc.)