Combinatorial optimization implementation

Question

I've been given a problem to solve which, at first glance, appears to be some sort of generalized assignment problem (a subset of combinatorial optimization problems: http://en.wikipedia.org/wiki/Generalized_assignment_problem).

The description of the problem is quite unclear and not written in English; please bear with me as I try to explain it as best I can:

I am given a set of "cuts" (tasks) to be performed on large marble blocks of specific sizes. The goal is to complete every task in a given list while minimizing the amount of marble lost. If I have, for example, a starting block of size 20, then I can cut it in different ways to fulfill a certain amount of tasks while making sure I don't "lose" marble in the process. If I need sub-blocks of 3, 5, 6 and 6, then a block of initial size 20 will do just fine as I will have no lost marble (3+5+6+6 = 20).

Thus, the goal is to fulfill every task whilst losing as little marble as possible. I may use any number of starting blocks, so long as the tasks are all completed. One additionnal constraint is that each task which specifies a sub-block of length L also has a "class" assigned to it, which represents what specific machine is required to do this specific cut. Given a starting block, I am unable to use more than 3 different classes to cut my block. I can do as many cuts as I want on one machine, as long as I don't change classes more than twice.

Here is an example of data that can be given to me:

2 20 38
7
20
4 1
7 1
3 1
25 1
22 2
22 1
20 2
17 1
10 1
22 2
27 2
26 2
15 3
13 4
12 5
15 6
27 4
27 5
27 7
27 2

The first line gives the number of different blocks that can be used to perform all given tasks, as well as the sizes of each starting block.

The second line gives the total number of different "classes" of cuts, which represent the number of different machines that can execute the needed cuts.

The third line gives the total amount of cuts (tasks) needed to complete the operation. In this case, exactly 20 tasks need to be performed to complete the problem.

The rest of the lines give the needed cut as well as the class associated with this task.

To recapitulate, I need to perform a certain list of tasks with any number of given starting blocks whilst attempting to minimize the amount of lost/unwanted marble.

So my question is: What is a good approach to this problem? I believe a greedy approximation algorithm might be a straightforward and simple way to find a reasonable solution, but I'm honestly not sure.

I apologize in advance if the given problem is unclear, if you need addtionnal information then feel free to make a request for clearer instructions.

Thanks!

PS: The algorithm will be written in Java, if that helps.

Answer 1

If I understand correctly, then (ignoring the "class" constraints) this is the Cutting Stock problem. This is an NP-hard optimisation problem that is usually solved by formulating it as an ILP and then applying a special kind of ILP solver technique called column generation. Briefly, the ILP has a variable for each possible pattern, or way of cutting a marble block into a maximal set of sub-blocks, that records the number of blocks that should be cut in that particular pattern. But there can be a vast number of possible patterns, most of which will not be used at all in an optimal solution; column generation allows the ILP solver to work with a smaller set of variables that is guaranteed to contain all the nonzero ones (i.e. all the patterns that are actually used).

There's a lot of good information on the Wikipedia page. Of particular interest is the fact that if there is only one initial block size, then minimising waste is the same as minimising the number of master blocks used, and then the problem is equivalent to Bin Packing. This problem is still NP-hard, but it's one of the "nice" ones: there are simple heuristics that (provably) get very close to the optimal solution. You might be able to adapt this into a heuristic for your problem.

One nice feature of formulating the problem as an ILP is that it shouldn't be difficult to add in more constraints corresponding to the class constraints.