Optimized Packings with Applications

This chapter addresses the problem of determining stowage plans for containers into a ship, which is the so-called master bay plan problem (MBPP). As a novel issue and variant of MBPP, in the present work we consider the stowage of hazardous containers that follows the principles included in the segregation table of the International Maritime Dangerous Goods (IMDG) Code. Formally, the MBPP consists in determining how to stow a set of n containers, split into different groups, according to their size, type, class of weight and destinations, into a set of m available slots, that are locations either on the deck or in the stow, of predetermined bays of a containership. Some structural and operational constraints, related to both the containers and the ship, have to be satisfied. The need of stowing dangerous goods implies to take into account additional constraints to be verified in each slot concerning the safety of the whole cargo, for which dangerous goods are categorized into different types and forced to be stowed away from incompatible ones. We face such variant of MBPP on the basis of its relationship with the bin packing problem, where items are containers and the bins are sections of the ship available for the stowage of hazardous containers. In particular, following a step by step procedure for properly loading all containers on board, we show how the segregation rules derived from the IMDG Code impact on the available slots of the bins. A real life case study is reported.

Resource management in datacenters involves assigning virtual machines with changing resource demands to physical machines with changing capacities. Recurrently, the changes invalidate the assignment and the resource manager recomputes it at runtime. The assignment is also subject to changing restrictions expressing a variety of user requirements. The present chapter surveys this application of vector packing—called the VM reassignment problem—with an insight into its dynamic and heterogeneous nature. We advocate flexibility to answer these issues and present BtrPlace, a flexible and scalable heuristic solution based on Constraint Programming.

Packing for engineering design involves the development and use of methods to determine the arrangement of a set of subsystems or components within some enclosure to achieve a set of objectives without violating spatial or performance constraints. Packing problems, also known as layout optimization problems are challenging because they are highly multimodal, are characterized by models that lack closed-form representations, and require expensive computational procedures. The time needed to resolve intersection calculations increases exponentially with the number of objects to be packed while the space available for the placement of these components becomes less and less available.

This paper presents a multiyear research effort targeting the development of computational tools for packing optimization problems which are encountered at different stages of engineering design with special interest in automotive design. Due to increasingly realistic engineering applications, the problems feature a rising level of complexity and therefore require optimization models and approaches with growing sophistication. To be relevant to automotive design, the packing problems account for the free shape of objects and consider either their compact packing within an envelope or their noncompact packing in the presence of multiple criteria used to evaluate system performance. The packing problems are represented by single or multiobjective optimization problems (MOPs) while the solution approaches rely on evolutionary algorithms due to the level of complexity that precludes development of effective exact methods.

This chapter examines the problem of packing tetris-like items, orthogonally, with the possibility of rotations, into a convex domain, in the presence of additional conditions. An MILP (Mixed Integer Linear Programming) and an MINLP (Mixed Integer Nonlinear Programming) models, previously studied by the author (Fasano, Solving Non-standard Packing Problems by Global Optimization and Heuristics. SpringerBriefs in Optimization, Springer Science + Business Media, New York, 2014), are surveyed. An efficient formulation of the objective function, aimed at maximizing the loaded cargo, is pointed out for the MILP model. The MINLP one, addressed to the relevant feasibility sub-problem, has been conceived to improve approximate solutions, as an intermediate step of a heuristic process. A space-indexed model is further introduced and the problem of approximating polygons by means of tetris-like items investigated. In both cases an MILP formulation has been adopted. An overall heuristic approach is proposed to provide effective solutions in practice. One chapter of this book focuses on the relevant computational aspects (Gliozzi et al., Container loading problem MIP-based heuristics solved by CPLEX: an experimental analysis. In: Fasano, G., Pintér, J.D. (eds.) Optimized Packings and Their Applications. Springer Optimization and Its Applications, Springer Science + Business Media, New York, 2015).

The International Space Station (ISS) is one of the most challenging currently ongoing space programs. It has led to a number of very demanding logistic issues, in particular in relation to the on-orbit maintenance and resource resupply.

A fleet of launchers and vehicles is periodically made available by the most prominent space agencies in order to serve this scope. An overall traffic plan schedules the recurrent upload and download interventions. The relevant Cargo Manifest (delivered by NASA) establishes, for each carrier launch and re-entry, the shipment that is supposed to be transported from Earth to orbit and vice versa.

The European Space Agency (ESA) contributed annually to the ISS logistics from 2008 to 2014, by accomplishing five Automated Transfer Vehicle (ATV) missions. The ATV transportation system was conceived to support the recurrent upload phases from Earth to the ISS.

Within the relevant cargo accommodation context, in addition to tight balancing conditions, intricate three-dimensional packing issues arose. Furthermore, besides the remarkable complexity related, per se, to the loading aspects, very strict deadlines were usually imposed to accomplish the task. Last minute upgrades or even significant changes, moreover, often were expected to take place.

CAST (Cargo Accommodation Support Tool) is a dedicated optimization framework, funded by ESA and developed by Thales Alenia Space to carry out the whole analytical ATV cargo accommodation. This chapter describes the ATV loading problem first. The basic concept of CAST is further outlined, highlighting the advantages of the methodology adopted, both in terms of solution quality and time saving. Current extensions and possible future enhancements are investigated.

In real-life problems of cutting and packing very often placement constraints are present. For instance, defective regions of the raw material (wooden boards, steel plates, etc.) shall not become part of the desired products. More generally, due to different quality demands, some products may contain parts of lower quality which are not allowed for other goods. Within this work we consider one- and two-dimensional rectangular cutting and packing problems where items of given types have to be cut from (or packed on) raw material such that an objective function attains its maximum. In the one-dimensional (1D) case, we assume for each item type that allocation intervals (regions of the raw material) are given so that any item of the same type must be completely contained in one of the corresponding allocation intervals. In addition, we deal with problems where the lengths of the 1D items of a given type may vary within known tolerances. In the two-dimensional (2D) case, where rectangular items of different types have to be cut from a large rectangle, we investigate guillotine cutting under the condition that defective rectangular regions are not allowed to be part of the manufactured products (even not partially). For these scenarios we present solution strategies which rely on the branch and bound principle or on dynamic programming. Based on properties of the corresponding objective functions we discuss possibilities to reduce the computational complexity. This includes the definition of appropriate sets of potential allocation (cut) points which have to be inspected to obtain an optimal solution. By dominance considerations the set of allocation points is kept small. In particular, the computational complexity becomes independent of the unit of measure of the input data. Possible generalizations will be discussed as well.

The issue of placing small boxes orthogonally, generally with the possibility of rotations, into a big box, maximizing the loaded volume, is usually referred to as the container loading problem. Despite its being notoriously of an NP-hard typology, a number of algorithms work out this problem very efficiently. The task becomes, nonetheless, even more challenging when additional conditions have to be taken account of. In such cases, a modeling-based approach is supposedly the most suitable and this definitely holds, in particular, when balancing requirements are posed. These, indeed, entail constraints of strong global impact that can hardly be coped with by sequential procedures, based on a step by step incremental loading of items.

MIP (Mixed Integer Programming) models relevant to the container loading problem or possible extensions of it are available in specialized literature. A dedicated MILP (Mixed Integer Linear Programming) formulation, supporting an overall heuristic approach, addressed to non-standard packing issues, is discussed in another chapter of this book. Hereinafter, some relevant computational aspects are looked into, restricting the consideration to the container loading problem, as per its classical statement. An ad hoc heuristics, derived from the above-mentioned overall approach, is outlined. The use of IBM ILOG CPLEX as an MILP optimizer is considered. Case studies concerning the solution of the MILP model tout court, when the instances involved are not of a large-scale nature, are reported first. Outcomes relevant to the ad hoc heuristics are further shown through a number of difficult instances. Examples of container loading issues, involving also balancing conditions, are additionally provided.

The issue of light pollution, unnecessary lighting of outdoor areas, came into focus in the last 10 years. This is the reason why observatories should not be built in highly populated areas, it also disturbs the wild life, and it raises questions about energy conservation too. Based on its capabilities, LED technology offers a solution to this problem. Nowadays, travellers can visit many cities in developed countries and encounter LED street lights in streets as application of this technology spreading in public lighting. Designing orientation of LEDs in such street lights is a difficult problem as we need to use multiple LED packages to light an as large area as an incandescent light bulb can. Determining correct angles is a global optimization problem, a complex mathematical task related to the field of covering problems. In this chapter, we present an automatic designing method to construct LED configurations for street lights and a light pattern computation technique to evaluate these configurations. To speed up the whole designing process, a possible way of parallelization is also discussed.

Using a regular grid to approximate a container, packing objects is reduced to assigning objects to the nodes of the grid subject to non-overlapping constraints. The packing problem is then stated as a large scale linear 0-1 optimization problem. Different formulations for non-overlapping constraints are presented and compared. Valid inequalities are proposed to strengthening formulations. This approach is applied for packing circular and L-shaped objects. Circular object is considered in a general sense as a set of points that are all the same distance (not necessary Euclidean) from a given point. Different shapes, such as ellipses, rhombuses, rectangles, octagons, etc., are treated similarly by simply changing the definition of the norm used to define the distance. Nesting objects inside one another is also considered. Numerical results are presented to demonstrate the efficiency of the proposed approach.

The problem of packing boxes into a large box is often only a part of a complex problem. For example in furniture supply chain applications, one needs to decide what trucks to use to transport furniture between production sites and distribution centres and stores, such that the furniture fits inside. Such problems are often formulated and sometimes solved using general-purpose integer programming solvers.

This chapter studies the problem of identifying a compact formulation of the multi-dimensional packing component in a general instance of integer linear programming, reformulating it using the discretisation of Allen–Burke–Mareček, and solving the extended reformulation. Results on instances of up to 10,000,000 boxes are reported.

In this chapter we investigate coverings of a square with uniform circles of minimal radius, with uncertainties in the actual locations of the circles. This setting is an example model of deploying sensors or other kind of observation units so that there are uncertainties in their deployments. Possible examples include scenarios when the deployment has to be made remotely (e.g., from the air) into a potentially dangerous place, deployments into a location with unknown terrain, or deployments influenced by the weather. Our goal is to produce coverings that are optimal in terms of a minimal radius, and are also robust in the following sense: wherever the circles are actually placed within a given uncertainty region, the result is still guaranteed to be a covering. We investigate three special uncertainty regions: first we prove that for uniform circular uncertainty regions the optimal robust covering can be created from the exact optimal covering without uncertainties, provided that the exact covering configuration is feasible for the robust scenario. For uncertainty regions given by line segments and by general convex polygons we design a bi-level optimization method combining a complete and rigorous global search and a derivative free black-box search, and show the efficiency of the method on some examples.

Spatial resources are often an important consideration in shipbuilding and large-scale manufacturing industries. Spatial scheduling problems (SSP) involve the non-overlapping arrangement of jobs within a limited physical workspace such that some scheduling objective is optimized. The jobs are typically heavy and occupy large areas, requiring that the same contiguous units of space be assigned throughout the duration of their processing time. This adds an additional level of complexity to the general scheduling problem. Since solving large instances using exact methods becomes computationally intractable, there is a need to develop alternate solution methodologies to provide near optimal solutions for these problems. Much of the literature focuses on minimizing the makespan of the schedule. We propose two heuristic methods for the minimum sum of completion times objective. Our approach is to group jobs into a batch and then apply a scheduling heuristic to the batches. We show that grouping jobs earlier in the schedule, although intuitive, can result in poor performance when jobs have sufficiently large differences in processing times. We provide bounds on the performance of the algorithms and also present computational results comparing the solutions to the optimal objective obtained from the integer programming formulation for SSP. With a smaller number of jobs, both algorithms produce comparable solutions. For instances with a larger number of jobs and a higher variability in spatial dimensions, we observe that the efficient area model outperforms the iterative model both in terms of solution quality and run time.

In this chapter we further develop the main tool of our studies,phi-functions. We define new functions, called quasi-phi-functions, that we use for analytic description of relations of geometric objects placed in a container taking into account their continuous rotations, translations, and distance constraints. The new functions are substantially simpler than phi-functions for some types of objects. They also are simple enough for some types of objects for which phi-functions could not be constructed. In particular, we derive quasi-phi-functions for certain 2D&3D-objects. We formulate a basic optimal packing problem and introduce its exact mathematical model in the form of a nonlinear continuous programming problem, using our quasi-phi-functions. We propose a general solution strategy, involving: a construction of feasible starting points, a generation of nonlinear subproblems of a smaller dimension and decreased number of inequalities; a search for local extrema of our problem using subproblems. To show the advantages of our quasi-phi-functions we apply them to two packing problems, which have a wide spectrum of industrial applications: packing of a given collection of ellipses into a rectangular container of minimal area taking into account distance constraints; packing of a given collection of 3D-objects, including cuboids, spheres, spherocylinders and spherocones, into a cuboid container of minimal height. Our efficient optimization algorithms allow us to get local optimal object packings and reduce considerably computational cost. We applied our algorithms to several inspiring instances: our new benchmark instances and known test cases.

On the one hand, in the famous graph coloring problem, each vertex of the considered graph has to get a single color. If two vertices are connected with an edge, then their colors have to be different. The goal consists in coloring the graph with the smallest number of colors. On the other hand, consider the packing problem where items have to be loaded in a container. For each item, we have to decide in which container it will be assigned. As some pairs of items are incompatible, they cannot be loaded in the same container. The goal is to load all the items in a minimum number of containers. Even if the correspondence between these two problems is obvious (a vertex is an item, a color is a container, and an edge represents an incompatibility), there is no obvious bridge between the packing and the graph coloring literatures. In this chapter, some packing problems will be modeled and solved with graph coloring models and methods.