Skip to main navigationSkip to main content
The University of Southampton
Mathematical Sciences

Quasi-phi-functions and optimal packing problems Seminar

Time:
11:00
Date:
2 June 2015
Venue:
02/2043

Event details

CORMSIS

We further develop our phi-function technique for solving Cutting and Packing problems. Here we introduce quasi-phi-functions for an analytical description of non-overlapping and containment constraints for 2D- and 3D-objects which can be continuously rotated and translated. These new functions can work well for various types of objects, for which ordinary phi-functions are too complicated (e.g. polytopes) or have not been constructed yet (e.g. ellipses). We also define normalized quasi-phi-functions and pseudonormalized (adjusted) quasi-phi-functions for modeling distance constraints. To show the advantages of our new quasi-phi-functions we apply them to the problem of placing a given collection of ellipses into a rectangular container of minimal area and the problem of placing a given collection of convex polytopes into a rectangular container of minimal volume. We use radical free quasi-phi-functions to reduce the problems to nonlinear programming problems and develop efficient solution algorithms. Our solution strategy for the problems consists of three major stages: 1) First we generate a number of starting points from the feasible set of the problem. We employ a new starting point algorithm (SPA), based on homothetic transformations of geometric objects. 2) Then starting from each point obtained at Step 1 we search for a local minimum of the objective function of our problem. We employ a new Local Optimization with Feasible Region Transformation (LOFRT) procedure. 3) Lastly, we choose the best local minimum from those found at Step 2. An essential part of our local optimization scheme (Step 2) is the LOFRT procedure that reduces the dimension of the problem and computational time. It is due to this reduction that our strategy can process large sets of objects (non-identical ellipses and non-identical polytopes). The actual search for a local minimum is performed by IPOPT solver, which is available at an open access noncommercial software depository (https://projects.coin-or.org/Ipopt). We present computational results that compare favourably with those published elsewhere recently.

Speaker information

Tatiana Romanova, National Academy of Sciences of Ukraine. Tatiana Romanova is an expert on cutting a packing, computer modelling, metaheuristics and exact algorithms applied to a wide range of cutting and packing problems, with a relevant number of publications in high impact journals.

Privacy Settings