1,721,164 research outputs found
Feature Issue: The Past and Present of Optimization
No full textNumero speciale della rivista: European Journal of Operational Research Volume 219, Issue 3, curato da S. Martello e J. M. Paixao (Guest Editors
Feature Issue: Combinatorics for Modern Manufacturing, Logistics and Supply Chain
No full textNumero speciale della rivista: European Journal of Operational Research Volume 189, Issue 3, curato da M. Kovalyov, S. Martello (Guest Editors
Linear Assignment
No full textThe Assignment Problem (AP) is one of the most popular and intensivelystudied topics in combinatorial optimization.This paper gives and annotathed bibliography of the most relevant papers presented in the literature
Bounds for the Cardinality Constrained P||Cmax Problem
No full textWe consider the generalization of the classical P||Cmax problem arising when a given limit k is imposed on the number of jobs that can be assigned to any machine. This generalization has practicalinterest in the optimization of assembly lines for printed circuit boards (PCB). The problem is strongly NP-hard for general k, it is solvable in O(n log n) time for fixed k=2, while it remains strongly NP-hard for any fixed k >= 3. We consider immediate adaptations of simple upper and lower bounds for P||Cmax, and analyze their worst-case behavior. We show that the cardinality constraint does not strengthen the LP relaxation of the problem, and that the worst-case performance of the bounds for P||Cmax generally worsen when they are adapted to the new problem.New specifically tailored lower bounds are introduced, andtheir average tightness is evaluated through extensive computational experiments on randomly generated test instances
Feature Issue: Rich models in discrete optimization: Formulation and resolution (ECCO XVI)
No full textNumero speciale della rivista: European Journal of Operational Research Volume 175, Issue 3, curato da G. Hasle, A. Løkketangen, S. Martello (Guest Editors
Optimal Scheduling of Taskson Identical Parallel Processors
No full textWe consider the classical problem of scheduling n tasks with given processing time on m identical parallel processors so as to minimizethe maximum completion time of a task. We introduce lower bounds, approximationalgorithms and a branch-and-bound procedure for the exact solution of theproblem. Extensive computational results show that, in many cases, large-sizeinstances of the problem can be solved exactly
The K-Cardinality Assignment Problem.
No full textWe consider a generalization of the assignment problem in which an integer k is given and onewants to assign k rows to k columns so that the sum of the corresponding costs is a minimum.The problem can be seen as a 2-matroid intersection, hence is solvable in polynomial time; immediatealgorithms for it can be obtained from transformation to min-cost flow or from classicalshortest augmenting path techniques. We introduce original preprocessing techniques for findingoptimal solutions in which g< k rows are assigned, for determining rows and columns whichmust be assigned in an optimal solution and for reducing the cost matrix. A specialized primalalgorithm is finally presented. The average computational efficiency of the different approachesis evaluated through computational experiments
Models and algorithms for packing rectangles into the smallest square
No full textWe consider the problem of determining the smallest square into which a given set of rectangular items can be packed without overlapping. We present an ILP model, an exact approach based on the iterated execution of a two-dimensional packing algorithm, and a randomized metaheuristic. Such approaches are valid both for the case where the rectangles have fixed orientation and the case where they can be rotated by 90°. We computationally evaluate the performance and the limits of the proposed approaches on a large set of instances, including a number of classical benchmarks from the literature, for both cases above, and for the special case where the items are squares
- …
