On the Use of Equivalence Classes for Optimal and Sub-Optimal Bin Covering

Bin covering is an important optimization problem in many industrial fields, such as packaging, recycling, and food processing. The problem concerns a set of \emph{items}, each with its own \emph{value}, that are to be collected into \emph{bins} in such a way that the total value of each bin, as measured by the sum of its item values, is not lower than a \emph{target} value. The optimization problem concerns maximizing the number of bins. This is a combinatorial NP-hard problem, for which true optimal solutions can only be calculated in specific cases, such as when restricted to a small number of items.

This talk describes a formulation of the bin covering problem that pushes the limit of what can be solved by an ordinary desktop computer and allows to find the true optimum for over 1000 items.

The approach relies on \emph{equivalence classes}, where the items are partitioned into sets with all items of equal value. The formulation then, instead of explicitly enumerating each item and each bin as in the standard formulation, collects \emph{packages} that fulfill the target criterion and then lets the solver choose an optimal combination of packages. The idea of equivalence classes can be taken even further, to result in a suboptimal solution, which is compared to the true optimum and found to come within less than 10\% of the optimum.

Martin Fabian is Full Professor in Automation and Head of the Automation Research group within the Division of Systems and Control, at the Department of Electrical Engineering, Chalmers University of Technology. After a Master degree in Chemical Engineering, he received the Ph.D. degree in Control Engineering in 1995 from Chalmers University of Technology, Goteborg, Sweden. Martin Fabian pioneered (together with Professor Bengt Lennartson) the control of discrete event systems and its industrial application, at Chalmers and in Sweden. This on-going work has built up the research group in Automation, which now consists of six senior researchers, one PhD post-doc, and 15 PhD students among which 3 are industrial PhD students. The group is part of the Wingqvist/Vinnex Excellence Center, and co-hosts together with the Functional Programming group at the Department of Computer Science the Systematic Testing of Cyber-Physical Systems (SyTeC) strong research environment funded by the Swedish Research Council. Currently Martin Fabian teaches courses in Design and Scheduling of Automated Production Systems, and Discrete Event Control and Optimization. His research interests include formal methods for automation systems in a broad sense, merging the fields of Control Engineering, Computer Science, and Production Engineering; in particular the Supervisory Control Theory and its issues of calculational complexity. Recently he has transferred results from this application area into the field of model-based test generation. Professor Fabian has authored more than 100 publications, and is co-developer of the formal methods software tool Supremica available free for research and education at www.supremica.org. The Automation Research group has close connections with industrial collaborators, the main Swedish hi-tech companies Volvo, Zenuity, ABB.