2
$\begingroup$

I'm trying to devise an algorithm to solve the bin packing problem with conflicts (sometimes referred to as BPPC, or BPC).

The problem is defined as follows: consider a set $V$ of $n$ items, where each item $i$ has an associated positive weight $w_i$, and $n$ identical bins of capacity $C$. In addition, there is an undirected graph $G=(V,E)$ representing the conflicts between items. The problem is to assign all items to the minimum number of bins without exceeding $C$ and in such a way that no bin contains conflicting items.

Now I understand that this problem is a combination of the graph coloring problem, and the normal bin packing problem, but I can't quite figure out how to merge algorithms designed for one or the other into a single algorithm suitable for solving this problem.

$\endgroup$
  • $\begingroup$ What kind of algorithm are you looking for? A heustiric? Approximation? Exact? $\endgroup$ – Tom van der Zanden May 9 at 7:00
  • $\begingroup$ @TomvanderZanden Since it's NP-Hard, I'd expect that a Heuristic/Approximation algorithm would be the only approach that will produce results in a timely fashion $\endgroup$ – protango May 9 at 9:22
  • $\begingroup$ @protango Even though it is NP hard, instances with lots of restrictions can often be easy to solve because all the restrictions reduce the number of possible cases. $\endgroup$ – gnasher729 Jun 7 at 11:16
  • $\begingroup$ @gnasher729 that could strongly depend on the algorithm being used. Do you have a reference for that on this particular problem, or is it by personal experience working with BPPC? $\endgroup$ – dhasson Jun 9 at 1:32
1
$\begingroup$

I have found the following resources that should be useful.

A first line of work has been on the domain of approximation algorithms and focused on achieving results for particular classes of the conflict graph:

[1] Jansen, Klaus. "An approximation scheme for bin packing with conflicts." Journal of combinatorial optimization 3.4 (1999): 363-377.

[2] Epstein, Leah, and Asaf Levin. "On bin packing with conflicts." SIAM Journal on Optimization 19.3 (2008): 1270-1298.

In [1], the author proposes an asymptotic approximation scheme for the bin packing problem with conflicts restricted to $d$-inductive graphs with constant $d$. This graph class contains trees, grid graphs, planar graphs and graphs with constant treewidth. The algorithm's number of bins within a factor of $1 + \varepsilon$ of optimal, having runtime polynomial both in $n$ and $1/\varepsilon$. This is an algorithmic theory paper with no experimental results are provided.

In [2], the authors study both online and offline variants of BPC, again, only on specific graph classes, e.g. perfect graphs, interval graphs and bipartite graphs. They improve on previous approximation ratio by Jahnsen and Öhring for perfect graphs. As an example of the results, they create a 2.5-approximation algorithm for the perfect graph case. Again a theoretical work where no numerical examples are shown.

A second line of work is concerned with implementation and heuristics (I am including branch-and-bound algorithms on this category even though they follow a different paradigm) and includes the following publications:

[3] Muritiba, Albert E. Fernandes, et al. "Algorithms for the bin packing problem with conflicts." Informs Journal on computing 22.3 (2010): 401-415.

[4] Sadykov, Ruslan, and François Vanderbeck. "Bin packing with conflicts: a generic branch-and-price algorithm." INFORMS Journal on Computing 25.2 (2013): 244-255.

In [3], the authors present new methods for finding upper and lower bounds for the BPC optimal solution, and a couple algorithmic approaches for the BPC:

  1. Evolutionary Algorithms and Tabu search
  2. Branch and price (that is, branch and bound combined with a column generation scheme) using a set covering formulation.

They show benchmark results consistently improving previous methods from the literature. They also left the benchmark instances and computational results available online, which could be useful to OP or other interested people. At this link you can find conference presentation slides related to this work. They used CPLEX, which is a commercial solver for optimization.

Finally [4], which is available at one of the authors' ResearchGate profile here. As in [3], the authors propose a branch-and-price algorithm for this problem using a set covering formulation, but the methods' details are different. They tested the approach on several instances, creating a specific variant for the case where the conflict graph $G$ is an interval graph, while also developing an approach for the general case. They tested their algorithm on both kinds of scenarios, and experimental results show their approach outperformed previous algorithms in several instances, both in terms of execution time and of achieving optimality. The work was implemented using BaPCod, a branch-and-price framework developed in C++ by a group at INRIA.


As a summary:

  • Having graph coloring as a particular case, it's hard to approximate the BPC. Good results have been attained using heuristic methods and branch and price with set covering formulations.
  • So, you could try starting with the simplest steps of the method presented by Fernandes-Muritiba et al- that is, lower and upper bounds and Evolutionary Algorithms and see if they fulfill your needs in terms of solution quality and execution time. There are several frameworks for implementing evolutionary algorithms, e.g. DEAP in Python.
  • If you'd rather have a general approximation guarantee, and if the conflict graph instances you work with fall within the categories of their studies, evaluate implementing algorithms from the first line of work.
  • I'd leave using branch and price approaches for later, especially in case of a tight development timeframe or if you don't have access to an optimization solver license.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.