Invited Session Fri.1.H 2032

Friday, 10:30 - 12:00 h, Room: H 2032

Cluster 11: Integer & mixed-integer programming [...]

Matheuristics

 

Chair: Marco Antonio Boschetti

 

 

Friday, 10:30 - 10:55 h, Room: H 2032, Talk 1

José M. Valério de Carvalho
SearchCol algorithms for the level bin packing problem

Coauthors: Filipe Alvelos, Elsa Silva

 

Abstract:
SearchCol, short for "metaheuristic search by column generation'', is an algorithmic framework for approximately solving integer programming / combinatorial optimization problems with a decomposable structure.
Each iteration of a SearchCol algorithm is made of three phases: (i) column generation is used to generate solutions to subproblems, (ii) a metaheuristic is used to search the (integer) solution space, and (iii) additional constraints, forcing or forbidding attributes of the incumbent solution, are included in the restricted master problem of column generation guiding the generation of new subproblem's solutions in the following iteration.
In this talk, we apply SearchCol algorithms to a bin packing problem where it is intended to minimize the number of used rectangular bins to pack a given set of rectangular items. Additionally, the items must be packed in levels. We present computational results for different variants of the SearchCol algorithms and compare them with other solution approaches.

 

 

Friday, 11:00 - 11:25 h, Room: H 2032, Talk 2

Patrick Schittekat
A matheuristic for competence building with the use of nurse re-rostering

Coauthor: Tomas Eric Nordlander

 

Abstract:
The global nursing shortage makes efficient use of these resources vital. Good nurse rosters assist but are often static and span over a long period while the daily personnel situation is more dynamic: nurses get sick, take short notice days off, etc. Commonly, these absences are handled by hiring extra nurses when needed. However, earlier analysis has shown that nurse rotation in combination with hiring is a much more efficient solution. Moreover, re-rostering gets easier if the hospital possesses the best mix of experience level and special skills. In other words, a more suitable competence profile makes re-rostering more beneficial. Nurse rotation (work regularly in another department) builds up competence, which allows for a more robust competence profile - departments become better suited to handle future personnel absences. We present a matheuristic that optimizes the competence profile under the assumption that nurse rotation is allowed and/or the hospital can buy in competence. Our preliminary experiments on small instances show how a more robust competence profile is much more efficient up to 40,%.

 

 

Friday, 11:30 - 11:55 h, Room: H 2032, Talk 3

Marco Antonio Boschetti
A Lagrangian heuristic for the sprint planning in agile methods

Coauthors: Turricchia Elisa, Golfarelli Matteo, Rizzi Stefano, Maniezzo Vittorio

 

Abstract:
Agile methods have been adopted by an increasing number of companies to make software development faster and nimbler. Most methods divide a project into sprints (iterations), and include a sprint planning phase that is critical to ensure the project success. Several factors impact on the optimality of a sprint plan, e.g., the estimated complexity, business value, and affinity of the user stories (functionalities) included in each sprint, which makes the planning problem difficult.
We present an approach for the sprint planning in agile methods based on a MIP model. Given the estimates made by the project team and a set of development constraints, the optimal solution is a sprint plan that maximizes the business value perceived by users.
Solving to optimality the model by a MIP solver (e.g., IBM Ilog Cplex) takes time and for some instances even to find a feasible solution requires too large computing times for an operational use. For this reason we propose a Lagrangian heuristic based on a relaxation of the proposed model and some greedy algorithms. Computational results on both real and synthetic projects show the effectiveness of the proposed approach.

 

  payday loan . What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.