ALIO/EURO 2021-2022: XTH JOINT ALIO/EURO INTERNATIONAL CONFERENCE ON APPLIED COMBINATORIAL OPTIMIZATION
PROGRAM FOR MONDAY, APRIL 11TH
Days:
next day
all days

View: session overviewtalk overview

08:45-09:00 Session 00

Welcome Session

09:00-10:30 Session MA1
09:00
Parliament Seating Assignment Problems
PRESENTER: Frits Spieksma

ABSTRACT. Motivated by evidence that the seating of members of a parliament has impact on their voting behavior, we consider the problem to assign seats in a parliament to its members. From a theoretical perspective, we prove that the seating assignment problem is strongly NP-hard in several restricted settings. Further, we present a Mixed Integer Programming formulation of the problem, and we design a heuristic. We report on computational experiments. Finally, from a practical perspective, we describe a case-study involving the Dutch parliament.

09:22
Adaptation of Vogel's method for solving the Unbalanced Assignment Problem

ABSTRACT. The assignment problem is present to a greater or lesser extent in the management of any organization, some examples being the stages of the production process or in the management of human resources. The problem consists of relating two groups of resources, the agents, which can be workers or manufacturing machines, and the jobs or tasks. In this paper we solve a specific version of this type of problem, called Unbalanced Assignment Problem when tasks exceed machines. For this purpose, the Vogel approximation method used in the Transportation problem is modified. A bibliographic review of the methods used in the literature for this problem is made. The performance of the proposed algorithm is presented and implemented in Python programming language. To validate the method, it is compared with results of other authors, and with the exact method through CPLEX. A statistical analysis of the results is performed on 200 problems from an open repository. The results indicate that the proposed method obtains better results in 4 out of 8 instances of the literature and in the 200 problems there are no significant differences in the mean of the total assignment cost with respect to the optimum, however, the proposed method obtained these solutions in a significantly shorter time compared to the exact method.

09:44
A backtracking-based procedure for a three-dimensional packing problem
PRESENTER: Ivo Koch

ABSTRACT. In this work we consider the following packing problem in the three dimensional space, which arises in the context of transportation of refrigerated medical products. The input data is given by a set of products and a set of container types. Each product consists of a certain amount of boxes, specified by their width, length, and height. Each container type is specified by its internal width, length, and height, and it also has a cost and a maximum internal volume that can be filled with products. The problem consists in placing the products in containers minimizing the total cost of used containers, in such a way that (a) each product must be vertically placed in each container, (b) no overlaps between products exist, (c) each product is placed either on the container floor or at least 70 % of its base is located above other products, (d) the maximum filled volume of each container is not exceeded, and (e) each product is combined with different products in at most one container. There are no limits to the amount of containers of each type that may be used.

We present a heuristic procedure for this problem. We resort to a dynamic programming procedure for the mono-container and mono-product subproblem, based on similar existing algorithms for the pallet loading problem. Based on the generation of all possible combinations of mono-product containers, we propose a backtracking-based procedure in order to complete the assignment of the remaining boxes. We present intensive computational experiments, which show that the solution times on real instances are acceptable and that the obtained solutions are appropriate to be used in practice.

10:06
A sliding window matheuristic to the floorplanning of VLSI circuits

ABSTRACT. This work approaches the packing soft rectangles problem applied in the context of planning and allocation of modules for network connections in large-scale VLSI integrated circuits. In this problem, modules that can have flexible dimensions must be allocated in circuits. Furthermore, the allocation must be carried out so as to minimize the wirelenght used to integrate the modules. A matheuristic approach is proposed to solve the VLSI circuit design problem. Combining mathematical programming and a heuristic method, an iterative sliding window procedure uses different sorting criteria for the modules to be allocated, based on an initialization strategy. The model used was based on works in the literature. To evaluate the method's performance, computational tests were performed with reference instances of the MCNC set in the C++ programming language with the CPLEX solver. The influence of different criteria in the initial ordering on the result will be analyzed.

09:00-10:30 Session MA2
09:00
Optimization tools for the zonification and routing of garbage collection trucks in the Argentine city of Berazategui

ABSTRACT. A solution approach based on mixed-integer linear programming models, heuristics and local search algorithms has been developed to optimize the residential waste collection system in the Argentine city of Berazategui. The goal is to achieve efficiency in the collection routes and to balance the workload among garbage collectors and among truck drivers. Once the results of this work are fully implemented, the disparity of workload among the former should decrease by 76%; the total travel distance of the trucks should be reduced by 22% and the distribution of work among drivers should be fairer.

09:22
Network design model to determine optimal bicycle infrastructure
PRESENTER: Antonio Mauttone

ABSTRACT. The study of rational methods to assist the planning of bicycle facilities has increased in the last years, since the interest in using the bicycle for daily trips has grown due to the need of reduce traffic congestion, decrease travel time, mitigate air and noise pollution, and develop physical activities that benefit health. We propose an optimization model for designing a bicycle network, which considers two relevant problem features: (i) each section of the network can be built adopting a technological alternative taken from a set of given candidates, (ii) discontinuities should be avoided as much as possible.A discontinuity occurs when a user is forced to traverse part of her or his path from origin to destination without having appropriate infrastructure. We formulate the problem as a variant of the fixed-charge uncapacitated multicommodity network design problem over a multi-layer graph structure. We apply the model to an instance taken from the literature and to the city of Montevideo, Uruguay. The computational experiments include sensitivity analysis with respect to the construction budget and the penalty of discontinuities. Numerical results are analyzed in terms of several output measures including user cost, distance traveled, discontinuities experienced, distribution offlow, budget and network length among the different technologies.

09:44
Selection of schools in districts using a bi-objective MILP model: A case study from Paraguay
PRESENTER: Tadeo Saldívar

ABSTRACT. The district of Abaí in the department of Caazapá, Paraguay, has building infrastructure conditions that can be improved in order to improve the quality of education. The reduction of schools could contribute to better management. Unfortunately, any change in the operation of the system generates strong resistance to change when it comes to closing schools. We present a bi-objective model that simultaneously seeks to reduce the total cost of the education system and minimize the number of students displaced from schools that must be closed.

10:06
A Mixed Integer Programming model for peasant farmers in developing countries: A study case from Paraguay

ABSTRACT. In developing countries, governmental support programs push agricultural supply chain networks to optimize farmer food security and promote rural growth. Decision-making in a system like this is complicated, given the many cropping options available and the many criteria regarding nutrition, income, work capacity that must be satisfied. We propose the use of a mathematical optimization model to help decision-making in this environment. We test our model in a case study for the Department of Caazapá, Paraguay, where the rural population is 80%, and 42% is poor people. The optimization model allows addressing the complexity of the problem, leads to suggest changes in the number of crops, improving the production and rotation mix, decreasing the total cost in the system, and satisfying almost the same nutritional requirements.

10:30-11:00Coffee Break
11:00-12:00 Session MB1: Plenary Talk
11:00
Optimizing the reliability of geographic networks with heterogeneous failures

ABSTRACT. In general, networks are subject to a trade-off between a low probability of network unavailability and the very high cost associated with the impossibility of providing service in that case. The objective of the reliability optimization problem is to find the network with the highest reliability among all networks belonging to a given family. The most common assumption for component failures is that vertices do not fail, and edges fail randomly with equal probability and independently of each other. This presentation focuses specifically on overcoming this assumption. We will discuss why it is essential to approach the design problem considering heterogeneous failure models. We will also present new mathematical models that cope with heterogeneous failures and remain tractable.

12:00-13:50 Session MC1
12:00
A Time-Space Network Formulation for rhe Planning of Delivery Using Mobile Depots from an Urban Consolidation Centre

ABSTRACT. Using a time-space network, we formulated a network flow problem to model the dispatch of MDs from the UCCs addressing the complexity of the synchronisation between the UCC and the MDs fleet. In addition, to the common flow conservation restrictions, the proposed model also includes customers and parking points time windows, MDs capacity constraints, and minimum and maximum parking time constraints. The decision variables of this model represent the flow of MDs in the time-space network and the customer assignment to nearby parking points. Finally, the objective function minimises the number of MDs and, lexicographically, the distance between customers and parking points. We implemented the time-space network optimisation model in a commercial algebraic modelling language. Preliminary results show that the formulation of the space-time network allows the proper modelling of the dispatching of the MDs from the UCC to serve a set of customers scattered in a given region. At the conference, we will show the analysis to evaluate the model performance using instances inspired in Melbourne's Central Business District (CBD) as a case study.

12:22
Modeling demand-price dependence in lot-sizing optimization
PRESENTER: Jéssica Costa

ABSTRACT. We consider a convex mixed integer nonlinear program to model a lot-sizing optimization problem, in which demand decreases as the price of the sold product increases. To model the demand-price dependence, we propose a hyperbolic function and compare it to a linear demand-price dependence in the literature. By analyzing the parameters of the hyperbolic function, we show its potential to better model the realistic dependence between demand and price. We illustrate the solution of the problem by solving an instance with the Muriqui Optimizer solver and compare the hyperbolic and linear models.

12:44
A simulation and optimization approach to reduce bus bunching in urban transport
PRESENTER: Citlali Olvera

ABSTRACT. Bus bunching is a phenomenon that deteriorates reliability and efficiency in public transportation systems. This phenomenon occurs when two or more buses of the same line arrive simultaneously at the same station due to interruptions in their schedules. In this work, we use bus holding times at stations to maintain quasi-regular headways and thus reduce bus bunching. Our solution approach uses a simulation and a mathematical model with quadratic constraints. Both processes are executed in a real-time setting. The results show a 47% and 30% reduction in bus bunching and waiting times, respectively.

13:06
Last-mile deliveries with drone and lockers

ABSTRACT. In this work we define a routing problem that arises in last-mile delivery of parcels in which customers can be served either directly at home by truck or by a drone that uses the truck as launching point, or in a self-service mode via pickup points normally called lockers. We propose mixed integer linear programming formulations and branch-and-cut algorithms to solve the problem and investigate their effectiveness.

12:00-13:30 Session MC2
12:00
Mixed integer programming formulations for a non-preemptive parallel machine scheduling problem
PRESENTER: Luis M Torres

ABSTRACT. The problem studied in this paper is motivated by the operations at the Internal Revenue Service of Ecuador. In this system, officials in charge must decide how many service counters must be active at any time to serve the incoming flow of customers and minimize the total number of man-hours that are necessary to serve such counters. This problem can be modeled as a multi-period non-preemptive parallel machine scheduling problem. In this research, two different integer programming formulations are proposed, where some lower bounds and valid inequalities are provided for both formulations. Moreover, computational results on real-world instances are reported.

12:22
Sports scheduling and managerial aspects: insights for Argentina’s National Basketball League

ABSTRACT. A competition’s structure and a league’s schedule represent key strategic decisions from a managerial standpoint. Argentina’s National Basketball League (LNB) has undergone a major transformation since 2014, following a schedule design resembling the National Basketball Association (NBA), reducing total distance traveled using a variant of the Traveling Tournament Problem (TTP). In this work, we consider an alternative league design, with a time-constrained schedule similar to the existing one before 2014, and revisit some well known model that incorporates the matches interest distribution throughout the tournament. For six LNB’s seasons, we observe that our approach reduces the overall distance traveled in several seasons and that under moderate assumptions regarding stadium attendance our model translates into higher revenue.

12:44
Approximation algorithm for resource-constrained project scheduling in underground mining operations
PRESENTER: Rodrigo Carrasco

ABSTRACT. Underground mining operations have many challenges. Some of these hurdles occur even before operations start, like the strategic planning phase. During this step, the mine is segmented into blocks according to the geophysical characteristics of the mine. Then, the planner needs to determine in what order to process the dierent blocks in order to maximize some scheduling metric like net present value (NPV). This step is highly challenging since mines consist of thousands (and sometimes millions) of blocks and have a plethora of operational constraints and precedence requirements among blocks. Furthermore, each block consumes a certain amount of dierent resources, which are limited. This planning problem is akin to the Resource-Constrained Project Scheduling Problem (RCPSP) in the scheduling literature. It is one of the topics most reviewed by the scheduling and combinatorial optimization literature. This problem has been proved to be NP-Hard, and many techniques have been used to tackle it. This work proposes an approximation algorithm that can provide good solutions for the RCPSP in reasonable execution times.

13:06
Prescriptive maintenance scheduling
PRESENTER: Anthony D. Cho

ABSTRACT. This work presents a maintenance scheduling model considering prognostic information provided by a predictive system. In particular, we developed a system based on run-to-failure signals segmentation and Long Short-Term Memory (LSTM) neural networks that returns the prediction of remaining useful life when a fault is present in a component. We incorporate such predictions in a stochastic optimization model using chance constraint. These constraints help control the number of failed components and consider the distance between them to reduce sparsity and minimize the total maintenance cost. Our results show that the capacity to solve problems is relatively large compared to experimental results described in most of the literature in reasonable computational time.

13:30-15:00Lunch Break
15:00-16:30 Session MD1
15:00
Constructing branching trees of geostatistical simulations
PRESENTER: Juan Valencia

ABSTRACT. In this work we tackle a strategic open-pit mine planning problem by using branching trees of geostatistical simulations, multi-stage programming, and scenario reduction techniques. The main challenges in this problem are to solve an NP-hard optimization problem and to incorporate into the algorithm adaptiveness to the newly observed ore grades of recently mined levels. To solve these challenges, our work presents an innovative orebody and optimization modeling. Indeed, first, our orebody modeling considers the uncertainty on ore grades and models new ore-grade information that becomes available in each time period through a branching tree of conditional geostatistical simulations. Second, our multi-stage programming algorithm dynamically learns and adapts based on the ore grades observed in recently mined levels. Third, we control the computational burden of our algorithm by applying scenario reduction techniques. In this way, our approach gives an adaptive mine plan, in contrast to the traditional approach of giving a single mine plan that does not adapt to the ore grades as they are revealed when mining.

15:22
A Parallel Bucket-Based Bottom-Left-Fill Algorithm for Nesting Problems Using a Semi-Discrete Representation
PRESENTER: Sahar Chehrazad

ABSTRACT. We discuss the parallelization of the bottom-left-fill algorithm to solve nesting problems on multicore processors. The algorithm uses a semi-discrete representation of both the 2D non-convex pieces and the strip. In case several rotation angles are allowed for each piece, the computation of the tentative placement for each angle is parallelized using OpenMP, limiting the number of threads to the number of rotation angles. The speedup is further limited due to load imbalance. Therefore, we develop a bucket-based bottom-left-fill algorithm, which subdivides the pieces in buckets and places the buckets, while computing an optimal ordering of the pieces in each bucket to improve the solution, i.e., to minimize the length of the strip. The many possible orderings of the pieces in a bucket allow to create many tasks that can be executed concurrently. Dynamic load balancing is used. We evaluate the parallel performance and the solution quality of this new algorithm, using different bucket sizes.

15:44
Sparse Solutions for the Unbounded Minimum Knapsack Problem with Procurement Applications
PRESENTER: Gonzalo Romero

ABSTRACT. We study the unbounded minimum knapsack problem (UMK). We show that both the optimal policy and existing approximation algorithms may require using all item types available, making them impractical in supply chain procurement applications. We design an algorithm for generating sparse solutions for the UMK, which are restricted to pre-selecting and using a limited number of item types to serve all demands. We show that our algorithm enjoys a parametric worst-case performance guarantee, for any demand, with respect to the optimal policy that has access to all item types available.

16:06
Multi-resource balancing - a case of a German kitchen manufacturer
PRESENTER: Sina Gläser

ABSTRACT. We address a multi-resource balancing-problem at Nobilia-Werke J.Stickling GmbH & Co. KG (Nobilia), the leading kitchen manufacturer in Germany. Nobilia produces kitchen furniture at two production facilities, both located in Verl, Germany. In recent years, the demand for Nobilia kitchens has increased steadily. The necessary expansion of production has been achieved by expanding to a second plant. Both plants can produce the same products and are currently operating at almost full capacity. Every day more than 3,000 individually designed kitchens are produced and delivered by Nobilia’s own fleet of delivery vehicles. All kitchens are made to order with each produced kitchen being assigned to a specific customer. The storage and retrieval of kitchen cabinets would not create any value - on the contrary, additional handling would even increase the quality risk. Therefore, Nobilia maintains no warehouse for finished goods. The customised cabinets of a kitchen are manufactured in parallel and aggregated just in sequence for loading into trucks immediately after production. A smooth flow of materials is essential to ensure on-time completion and loading of a whole kitchen. 

We present an integer programming model and consider a multi-criteria objective function as well as a set of constraints reflecting Nobilia’s requirements. We propose a software based solution approach for Nobilia’s instance sizes. The results of our computational experiments on real-world data demonstrate that our approach provides significant benefits.

16:30-17:15 Session ME1: Special Session
16:30
Large scale applied Combinatorial Optimization in MercadoLibre
PRESENTER: Daniel Severin
19:00-20:30

Welcome Reception