packing

Solving the parallel processor scheduling and bin packing problems with contiguity constraints: mathematical models and computational studies

  • FB Akcay
  • Maxence Delorme
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    The parallel processor scheduling and bin packing problems with contiguity constraints are important in the field of combinatorial optimization because both problems can be used as components of effective exact decomposition approaches for several two-dimensional packing problems. In this study, we provide an extensive review of existing mathematical formulations for the two problems, together with … Read more

    Lower bounds on the lattice-free rank for packing and covering integer programs

  • Merve Bodur
  • Alberto Del Pia
  • Santanu S. Dey
  • Marco Molinaro
    • Categories Cutting Plane Approaches, Integer Programming Tags , , , , ,

    In this paper, we present lower bounds on the rank of the split closure, the multi-branch closure and the lattice-free closure for packing sets as a function of the integrality gap. We also provide a similar lower bound on the split rank of covering polyhedra. These results indicate that whenever the integrality gap is high, … Read more

    Large-scale packing of ellipsoids

  • Ernesto G. Birgin
  • R. D. Lobato
    • Categories Nonlinear Optimization Tags , , ,

    The problem of packing ellipsoids in the n-dimensional space is considered in the present work. The proposed approach combines heuristic techniques with the resolution of recently introduced nonlinear programming models in order to construct solutions with a large number of ellipsoids. Numerical experiments illustrate that the introduced approach delivers good quality solutions with a computational … Read more

    Aggregation-based cutting-planes for packing and covering integer programs

  • Merve Bodur
  • Alberto Del Pia
  • Santanu S. Dey
  • Sebastian Pokutta
  • Marco Molinaro
    • Categories Cutting Plane Approaches, Integer Programming Tags , , , ,

    In this paper, we study the strength of Chvatal-Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs). Aggregation cuts are obtained as follows: Given an IP formulation, we first generate a single implied inequality using aggregation of the original constraints, then obtain the integer hull of the set defined … Read more

    A multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem

  • José Fernando Gonçalves
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Production and Logistics, Stochastic Approaches Tags , , , , ,

    This paper addresses a constrained two-dimensional (2D), non-guillotine restricted, packing problem, where a fixed set of small rectangles has to be packed into a larger stock rectangle so as to maximize the value of the rectangles packed. The algorithm we propose hybridizes a novel placement procedure with a genetic algorithm based on random keys. We … Read more

    A MIP Approach for some Practical Packing Problems: Balancing Constraints and Tetris-like Items

  • Giorgio Fasano
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , , ,

    This paper considers packing problems with balancing conditions and items consisting of clusters of parallelepipeds (mutually orthogonal, i.e. tetris-like items). This issue is quite frequent in space engineering and a real-world application deals with the Automated Transfer Vehicle project (funded by the European Space Agency), at present under development. A Mixed Integer Programming (MIP) approach … Read more

    A hybrid heuristic for the constrained two-dimensional non-guillotine orthogonal cutting problem

  • José Fernando Gonçalves
  • Mauricio G.C. Resende
    • Categories Applications - OR and Management Sciences, Meta Heuristics Tags , , , , ,

    This paper addresses a constrained two-dimensional (2D) non-guillotine cutting problem, where a fixed set of small rectangles has to be cut from a larger stock rectangle so as to maximize the value of the rectangles cut. The algorithm we propose hybridizes a novel placement procedure with a genetic algorithm based on random keys. We propose … Read more