1,721,082 research outputs found
Open Shop, Satellite Communication and a Theorem by Egervary (1931)
No full textWe briefly outline recent results showing that the classical Inukai algorithm for the SS/TDMA time slot assignment problem is equivalent to a previously published algorithm for a combinatorial optimization problem, and that both implement a technique developed in 1931 by Egervary
Exact solution of the two-dimensional finite bin packing problem
No full textGiven a set of rectangular pieces to be cut from an unlimited number of standardized stock pieces (bins), the Two-Dimensional Finite Bin Packing Problem is to determine the minimum number of stock pieces that provide all the pieces. The problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. We analyze a well-known lower bound and determine its worst-case performance. We propose new lower bounds which are used within a branch-and-bound algorithm for the exact solution of the problem. Extensive computational testing on problem instances from the literature involving up to 120 pieces shows the effectiveness of the proposed approach
Algorithmic approaches to the multiple knapsack assignment problem
Full text linkWe consider a variant of the multiple knapsack problem in which some assignment-type side constraints have to be satisfied. The problem finds applications in logistics sectors related, e.g., to transportation and maritime shipping. We derive upper bounds from Lagrangian and surrogate relaxations of a mathematical model of the problem. We introduce a constructive heuristic and a metaheuristic refinement. We study the computational complexity of the proposed methods and evaluate their practical performance through extensive computational experiments on benchmarks from the literature and on new sets of randomly generated instances. (C) 2018 Elsevier Ltd. All rights reserved
Reduction of the Three-Partition Problem
No full textThe three-partition problem is one of the most famous strongly NP-complete combinatorial problems. We introduce properties which, in many cases, can allow either a quick solution of an instance or a reduction of its size. The average effectiveness of the properties proposed is tested through computational experiments
Recent advances on two-dimensional bin packing problems
No full textWe survey recent advances obtained for the two-dimensional bin packing problem, with special emphasis on exact algorithms and effective heuristic and metaheuristic approaches. © 2002 Elsevier Science B.V
A lower bound for the non-oriented two-dimensional bin packing problem
No full textGiven a set of rectangular items, and an unlimited number of identical rectangular bins, we consider the problem of allocating, without overlapping, all the items to the minimum number of bins. We assume that the items may be rotated by 90°. The problem is strongly NP-hard, and has several industrial applications. No specific lower bound is known for it. We present a lower bound which explicitly takes into account the possible item rotation. The bound is embedded into an exact branch-and-bound algorithm. The average performance is evaluated through computational experiments. © 2002 Elsevier Science B.V
Relaxations and heuristics for the multiple non-linear separable knapsack problem
No full textWe consider the multiple non-linear knapsack problem with separable non-convex functions. The problem, which can be modeled as a (mixed) integer non-linear program, is extremely difficult to solve in practice. We present a fast heuristic algorithm, based on constructive techniques, surrogate relaxations, and local search improvements. Computational comparisons with exact and heuristic methods for general non-convex mixed integer non-linear programs show that the proposed approach provides good-quality solutions within small computing times
- …
