1,721,059 research outputs found
An optimization algorithm for a penalized knapsack problem
No full textWe study a variation of the knapsack problem in which each item has a profit, a weight and a penalty; the sum of profits of the selected items minus the largest penalty associated with the selected items must be maximized. We present an ILP formulation and an exact optimization algorithm
Mathematical programming algorithms for bin packing problems with item fragmentation
No full textIn this paper we consider a class of bin packing problems from the literature having the following distinctive feature: items may be fragmented at a price. Problems of this kind arise in diverse application fields like logistics and telecommunications, and have already been extensively tackled from an approximation point of view. We focus on the case in which splitting produces no overhead, a fixed number of bins is given and the number of fragments or fragmentations needs to be minimized. We first investigate the theoretical properties of the problem. Then we elaborate on them to devise mathematical programming models and algorithms, yielding both exact optimization algorithms and effective heuristics. An extensive experimental campaign proves that our approach is very effective, and highlights which features make an instance computationally harder to solve
An optimization algorithm for the ordered open-end bin-packing problem
No full textThe ordered open-end bin-packing problem is a variant of the bin-packing problem in which the items to be packed are sorted in a given order and the capacity of each bin can be exceeded by the last item packed into the bin. We present a branch-and-price algorithm for its exact optimization. The pricing subproblem is a special variant of the binary knapsack problem, in which the items are ordered and the last one does not consume capacity. We present a specialized optimization algorithm for this subproblem. The speed of the column generation algorithm is improved by subgradient optimization
steps, allowing for multiple pricing and variable fixing. Computational results are presented on instances of different sizes
and items with different correlations between their size and their position in the given order
Exactly solving packing problems with fragmentation
No full textIn packing problems with fragmentation a set of items of known weight is given, together with a set of bins of limited capacity; the task is to find an assignment of items to bins such that the sum of items assigned to the same bin does not exceed its capacity. As a distinctive feature, items can be split at a price, and fractionally assigned to different bins. Arising in diverse application fields, packing with fragmentation has been investigated in the literature from both theoretical, modeling, approximation and exact optimization points of view. We improve the theoretical understanding of the problem and we introduce new models by exploiting only its combinatorial nature. We design new exact solution algorithms and heuristics based on these models. We consider also variants from the literature with different objective functions and the option of handling weight overhead after splitting. We present experimental results on both datasets from the literature and new, more challenging, ones. These show that our algorithms are both flexible and effective, outperforming by orders of magnitude previous approaches from the literature for all the variants considered. By using our algorithms we could also assess the impact of explicitly handling split overhead, in terms of both solutions quality and computing effort
A branch-and-price algorithm for the multilevel generalized assignment problem
No full textThe multilevel generalized assignment problem (MGAP) is a variation of the generalized assignment problem, in which agents can execute tasks at different efficiency levels with different costs. We present a branch-and-price algorithm that is the first exact algorithm for the MGAP. It is based on a decomposition into a master problem with set-partitioning constraints and a pricing subproblem that is a multiple-choice knapsack problem. We report on our computational experience with randomly generated instances with different numbers of agents, tasks, and levels; and with different correlations between cost and resource consumption for each agent-task-level assignment. Experimental results show that our algorithm is able to solve instances larger than those of the maximum size considered in the literature to proven optimality
Electric Vehicle Routing Problem with Multiple Recharge Technologies (EVRP-MRT) Dataset
No full textIn this repository, the benchmark dataset for the Electric Vehicle Routing Problem with Multiple Recharge Technologies is introduced (EVRP-MRT). The whole benchmark is composed by 66 instances comprised by 5 to 30 customers and 3 to 9 recharge stations. All instances are solved to proven optimality. Instances and optimal solutions are presented in xml format, compliant with the VRP-rep specifications. The VRP-rep instance mapper was used to draw the graph of each instance (and its solution) in png format
Column generation for the variable cost and size bin packing problem with fragmentation
Full text linkBin Packing Problems with Item Fragmentation (BPPIF) are variants of classical Bin Packing in which items can be split at a price. We extend BPPIF models from the literature by allowing a set of heterogeneous bins, each potentially having a different cost and capacity. We introduce extended formulations and column generation algorithms to obtain good bounds with reasonable computing effort. We test our algorithms on instances from the literature. Our experiments prove our approach to be more effective than state-of-the-art general purpose solvers
Asynchronous Column Generation
No full textIn this paper we face a very fundamental problem in Operations Research: to find good dual bounds to generic mixed integer mathematical programs (MIPs) as quickly as possible. In particular, we focus on the scenario where large scale data needs to be considered, multicore CPU architectures are available, and massive parallelism can be exploited by means of decomposition methods. We consider column generation techniques to solve extended formulations obtained by means of Dantzig-Wolfe decomposition for MIPs. We propose a concurrent algorithm, that relaxes the synchronized behavior of classical column generation. Our approach relies on simple data structures and efficient synchronization, still providing the same global convergence properties of classical sequential column generation methods. We present and discuss the results of an extensive experimental campaign, comparing our concurrent algorithm to both a naive parallelization of column generation and the cutting planes algorithm implemented in state-of-the-art commercial optimization packages, considering large scale datasets of a hard packing problem from the literature as representative benchmark. Our approach turns out to be on average one order of magnitude faster than competitors, attaining almost linear speedups as the number of available CPU cores increases
Balanced compact clustering for efficient range queries in metric spaces
No full textGiven a set of points in a metric space, an additional query point and a positive threshold, a range query determines the subset of points whose distance from the query point does not exceed the given threshold. This paper tackles the problem of clustering the set of points so as to minimize the number of distance evaluations required by a range query. This problem models the efficient extraction of information from a database when the user is not interested in an exact match retrieval, but in the search for similar items. Since this need has become widespread in the management of text, image, audio and video databases, several data structures have been proposed to support such queries. Their optimization, however, is still left to extremely simple heuristic rules, if not to random choices. We propose the Balanced Compact Clustering Problem (BCCP) as a combinatorial model of this problem. We discuss its approximation properties and the complexity of special cases. Then, we present two Integer Programming formulations, prove their equivalence and introduce valid inequalities and variable fixing procedures. We discuss the application of a general-purpose solver on the more efficient formulation. Finally, we describe a Tabu Search algorithm and discuss its application to randomly generated and to real-world benchmark instances up to one hundred thousands points
- …
