A Combinatorial optimization problem

[csopi]

Hi,
I have the following optimization problem. I have a list of tasks that I should be able to perform with my tools. Each tool costs a certain amount of money, and may be used to carry out a finite number of tasks. The goal is to choose an optimal set of tools in such a way that the toolset can do all the required tasks, while the total cost should be minimal.

Any idea what kind of algorithm shall I use to solve this? It looks like a standard combinatorial optimization problem, I suppose there should be a solution for it.

Many thanks!

 

[BvU]

Start here and use the terms as search terms to find somethingof interest. It's a wide subject where there's a lot to earn, so there's an awful lot of material

 

[csopi]

Start here and use the terms as search terms to find somethingof interest. It's a wide subject where there's a lot to earn, so there's an awful lot of material

Thanks for the immediate reply! I have heard about this one, actually already tried a basic version. I am wondering if there are other methods? B & B is an "art" for me, not sure what is the most efficient way for bound estimation, that's why I am asking.

 

[Jarvis323]

Can you formulate similar to a weighted bipartite matching problem (with tools on one side, and tasks on the other), and solve it as a min-cost max-flow problem using the network simplex algorithm?

 

[StoneTemplePython]

Thanks for the immediate reply! I have heard about this one, actually already tried a basic version. I am wondering if there are other methods? B & B is an "art" for me, not sure what is the most efficient way for bound estimation, that's why I am asking.

To be clear everything is an "art" when you're dealing with NP Hard problems. Combinatorial optimization problems invariably fall under into this bucket or close relative, unless there is some very special structure to exploit (see dynamic programming in particular if you find a way to make subproblems overlap and above post on network simplex, which roughly means very special linear program that gets integer results).

Other power tools are dynamic programming and mixed integer programming (MIP). These are for exact solutions and run in exponential time. A quick and easy bound on optimality comes when you relax the integer domain requirement of your problem and run it as a linear program.

There are tons of approximation algorithms out there as well, including some very powerful stuff with semidefinite programming that I've been meaning to learn. Local search with randomness sprinkled in is a popular method (simulated annealing being a well known flavor of this).

- - - -
In general this not an easy class of problems and it takes a lot of sophistication (and patience) to deal with this stuff. Sometimes people find ways to mix and match tools, creating an ensemble approach.

If it were me, I'd first code up the mixed integer program (and actually first run the LP relaxation to get a fast bound). Give the MIP a few hours and see if it terminates.

 

[sysprog]

This 2013-2014 paper: The Simplex Algorithm is NP-mighty, by Yann Disser and Martin Skutella, has some good insights regarding use of the simplex algorithm as a tool for for solving NP-hard problems.