5

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?

Improve this question
1
  • 1
    Can you add more information about typical problem sizes. Ie. what is the number of devices to choose from and can one device be used several times? Commented Mar 3, 2011 at 11:21

3 Answers 3

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

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.

Improve this answer

3 Comments

What happen when more devices and more io types are needed ? reinventing an ILP solver isn't going to help.
@BatchyX: If they're not actually going to increase, then spending a lot of research time to write something more efficient is premature optimization.
"premature optimization" is the worst excuse i've heard to oppose learning the right tool for the job. knowing the tool might be useful later. And ILP solvers are intuitive these days, even LibreOffice can solve ILPs with a nice GUI(Tool/Solver). programs like lpsolve can be used in the command line, taking a text file as input. Not mentionning the numerous APIs.
1

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

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.