-
Fast Neighborhood Search Heuristics for the Colored Bin Packing Problem
Authors:
Renan F. F. da Silva,
Yulle G. F. Borges,
Rafael C. S. Schouery
Abstract:
The Colored Bin Packing Problem (CBPP) is a generalization of the Bin Packing Problem (BPP). The CBPP consists of packing a set of items, each with a weight and a color, in bins of limited capacity, minimizing the number of used bins and satisfying the constraint that two items of the same color cannot be packed side by side in the same bin. In this article, we proposed an adaptation of BPP heuris…
▽ More
The Colored Bin Packing Problem (CBPP) is a generalization of the Bin Packing Problem (BPP). The CBPP consists of packing a set of items, each with a weight and a color, in bins of limited capacity, minimizing the number of used bins and satisfying the constraint that two items of the same color cannot be packed side by side in the same bin. In this article, we proposed an adaptation of BPP heuristics and new heuristics for the CBPP. Moreover, we propose a set of fast neighborhood search algorithms for CBPP. These neighborhoods are applied in a meta-heuristic approach based on the Variable Neighborhood Search (VNS) and a matheuristic approach that combines linear programming with the meta-heuristics VNS and Greedy Randomized Adaptive Search (GRASP). The results indicate that our matheuristic is superior to VNS and that both approaches can find near-optimal solutions for a large number of instances, even for those with many items.
△ Less
Submitted 8 July, 2024; v1 submitted 6 October, 2023;
originally announced October 2023.
-
Algorithms for the Bin Packing Problem with Scenarios
Authors:
Yulle G. F. Borges,
Vinícius L. de Lima,
Flávio K. Miyazawa,
Lehilton L. C. Pedrosa,
Thiago A. de Queiroz,
Rafael C. S. Schouery
Abstract:
This paper presents theoretical and practical results for the bin packing problem with scenarios, a generalization of the classical bin packing problem which considers the presence of uncertain scenarios, of which only one is realized. For this problem, we propose an absolute approximation algorithm whose ratio is bounded by the square root of the number of scenarios times the approximation ratio…
▽ More
This paper presents theoretical and practical results for the bin packing problem with scenarios, a generalization of the classical bin packing problem which considers the presence of uncertain scenarios, of which only one is realized. For this problem, we propose an absolute approximation algorithm whose ratio is bounded by the square root of the number of scenarios times the approximation ratio for an algorithm for the vector bin packing problem. We also show how an asymptotic polynomial-time approximation scheme is derived when the number of scenarios is constant. As a practical study of the problem, we present a branch-and-price algorithm to solve an exponential model and a variable neighborhood search heuristic. To speed up the convergence of the exact algorithm, we also consider lower bounds based on dual feasible functions. Results of these algorithms show the competence of the branch-and-price in obtaining optimal solutions for about 59% of the instances considered, while the combined heuristic and branch-and-price optimally solved 62% of the instances considered.
△ Less
Submitted 24 May, 2023;
originally announced May 2023.
-
Query Understanding for Natural Language Enterprise Search
Authors:
Francisco Borges,
Georgios Balikas,
Marc Brette,
Guillaume Kempf,
Arvind Srikantan,
Matthieu Landos,
Darya Brazouskaya,
Qianqian Shi
Abstract:
Natural Language Search (NLS) extends the capabilities of search engines that perform keyword search allowing users to issue queries in a more "natural" language. The engine tries to understand the meaning of the queries and to map the query words to the symbols it supports like Persons, Organizations, Time Expressions etc.. It, then, retrieves the information that satisfies the user's need in dif…
▽ More
Natural Language Search (NLS) extends the capabilities of search engines that perform keyword search allowing users to issue queries in a more "natural" language. The engine tries to understand the meaning of the queries and to map the query words to the symbols it supports like Persons, Organizations, Time Expressions etc.. It, then, retrieves the information that satisfies the user's need in different forms like an answer, a record or a list of records. We present an NLS system we implemented as part of the Search service of a major CRM platform. The system is currently in production serving thousands of customers. Our user studies showed that creating dynamic reports with NLS saved more than 50% of our user's time compared to achieving the same result with navigational search. We describe the architecture of the system, the particularities of the CRM domain as well as how they have influenced our design decisions. Among several submodules of the system we detail the role of a Deep Learning Named Entity Recognizer. The paper concludes with discussion over the lessons learned while developing this product.
△ Less
Submitted 11 December, 2020;
originally announced December 2020.
-
Text Mining Descriptions Of Dreams: aesthetic and clinical efforts
Authors:
Renato Fabbri,
Fabiane M. Borges
Abstract:
Dreams are highly valued in both Freudian psychoanalysis and less conservative clinical traditions. Text mining enables the extraction of meaning from writings in powerful and unexpected ways. In this work, we report methods, uses and results obtained by mining descriptions of dreams. The texts were collected as part of a course in Schizoanalysis (Clinical Psychology) from dozens of participants.…
▽ More
Dreams are highly valued in both Freudian psychoanalysis and less conservative clinical traditions. Text mining enables the extraction of meaning from writings in powerful and unexpected ways. In this work, we report methods, uses and results obtained by mining descriptions of dreams. The texts were collected as part of a course in Schizoanalysis (Clinical Psychology) from dozens of participants. They were subsequently mined using various techniques for the achievement of poems and summaries, which were then used in clinical sessions by means of music and declamation. The results were found aesthetically appealing and effective to engage the audience. The expansion of the corpus, mining methods and strategies for using the derivatives for art and therapy are considered for future work.
△ Less
Submitted 26 October, 2017;
originally announced November 2017.
