Activities

The members of the group are involved in research projects and organizes conferences. The group is responsible for a series of research seminars, held with irregular intervals.

Research Projects

AXIOM Design and experimental analysis of novel integrated optimization methods 2017 – 2021
PoShCoP Combined port and ship planning 2013 – 2016
DOMinant II Maritime and road based transport 2011 – 2015
DOMinant Maritime and road based transport 2007 – 2009

Conferences organized

LOT Molde 31.08.2014 – 02.09.2014
VeRoLog 2014 Oslo 22.06.2014 – 25.06.2014
Tristan 7 Tromsø 20.06.2010 – 25.06.2010
DOMinant workshop Molde 20.09.2009 – 22.09.2009
Solving Rich VRP Models Molde 16.06.2005 – 17.06.2005
TraLog Molde 25.08.2004 – 27.08.2004
ECCO XVI Molde 05.06.2003 – 07.06.2003
Nordic MPS '98 Molde 09.05.1998 – 10.05.1998

Research Seminars

The seminars are usually held on selected Fridays at 13:15 in room A-283. Announcements are made on this webpage and by e-mail to the optimization group and other relevant mailing lists.

Date Speaker Topic Abstract
Monday May 15 2017, 13:15, room B-262 Rodrigo Ferreira da Silva A GVNS Heuristic for the TSP with Time Windows, and the Reachability Problem on Very Large Graphs In this presentation, we will talk about two topics. The first topic is a General Variable Neighborhood Search (VNS) heuristic for the Traveling Salesman Problem with Time Windows (TSPTW). This approach was proposed in 2010, but many other subsequent approaches are based on the key concepts proposed in this paper and GVNS heuristic still remains the state-of-the-art for this problem. The second topic is the reachability problem on very large graphs. When a very large graph with hundreds of millions of vertices is given as input, it is not feasible to transverse the whole graph to answer each query. This scenario is becoming more common nowadays and relevant examples can be found in social networks, article citations, web graphs, traffic routing and internet of things (IoT).

Wednesday December 7 2016, 14:15, room A-202 Arild Hoff Heuristics for the Capacitated Modular Hub Location Problem In this talk we discuss a variant of the hub location problem, where the goal is to identify an optimal subset of facilities (hubs) to minimize the transportation cost while satisfying certain capacity constraints. In particular, we target the single assignment version, in which each node in the transportation network is assigned to only one hub to route its traffic. We consider here a realistic variant introduced previously, in which the capacity of edges between hubs is increased in a modular way. This reflects the practical situation in air traffic where the number of flights between two locations implies a capacity in terms of number of passengers. Then, the capacity can be increased in a modular way, as a factor of the number of flights. We propose heuristic methods to obtain high-quality solutions in short computational times. Specifically, we implement memory structures to create advanced search methods and compare them with previous heuristics on a set of benchmark instances. Memory structures have been widely implemented in the context of the tabu search methodology, usually embedded in local search algorithms. In this paper we explore an alternative design in which the constructive method is enhanced with frequency information and the local search is coupled with a path relinking post-processing. Statistical tests confirm the superiority of our proposal with respect to previous developments.

Friday September 9 2016, 13:15, room A-284 Juanjo Peiró Extending the uncapacitated r-allocation p-hub median problem In this seminar we will propose a heuristic procedure for a stochastic version of the Uncapacitated r-Allocation p-Hub Median Problem with non-stop services. In particular, we assume that the number of hubs to which a terminal can be allocated, is bounded from above by r. Additionally we consider the possibility of shipping traffic directly between terminals (non-stop services) in case this renders savings in the overall cost. Uncertainty is associated with the traffics to be shipped between nodes and with the transportation costs. If we assume that such uncertainty can be captured by a finite set of scenarios, each of which having some known occurrence probability, it is possible to develop a compact formulation for the deterministic equivalent problem. However, even for small instances of the problem, the model becomes too large to be easily tackled by a general purpose solver. This fact motivates the development of an approximate procedure, whose starting point is the determination of a feasible solution to every (deterministic) single-scenario problem. These solutions are then embedded into a process inspired by Path Relinking: gradually an initial solution to the overall problem is transformed by the incorporation of attributes from some guiding solutions. In our case, the guiding solutions are those found for the single-scenario problems. We report and discuss the results of the computational experiments performed using the well-known CAB data set.

Monday February 29 2016, 13:15, room B-262 Evellyn Cavalcante Combinatorial Relaxation Bounds and Preprocessing for Berth Allocation Problems In this talk, we discuss graph-theoretical results for a discrete optimization problem in maritime logistics. The Berth Allocation and Quay Crane Assignment Problem (BACAP) aims to allocate berthing position/time, and a number of quay cranes (QCs) for arriving vessels in a seaport container terminal. Feasible assignments in the BACAP need to fulfil requirements on desired berthing period and position, and an agreement on the QCs availability. Previous models for the BACAP based on generalized set partitioning formulations have been studied in the literature. We describe two combinatorial relaxations based on computing maximum weighted matchings in suitable graphs, providing dual bounds and a variable reduction technique. The results can be exploited in any algorithm building on an enumeration of set partitioning variables.

Monday December 14 2015, 13:15, room B-262 Phillippe Samer Exact solution of the minimum spanning tree problem under conflict constraints In this talk, we will briefly discuss approaches for the exact solution of the minimum spanning tree problem under conflict constraints. Given a graph G(V,E) and a set C of conflicting edge pairs, the problem consists of finding a conflict-free minimum spanning tree, i.e. feasible solutions may include at most one of the edges from each pair in C. The problem is NP-hard in the general case. Although formulations and algorithms have been discussed recently in the literature, computational results indicate considerably large duality gaps and a lack of optimality certificates for benchmark instances. In this work, we regard polyhedral representations of conflict-free edge subsets as stable sets in an auxiliary conflict graph G'(E,C). We present integer linear programming formulations including four classes of exponentially-many constraints: two of which correspond to classic polyhedral representations of spanning trees in G, and two for strengthening the intersection with relaxations of the polytope of stable sets in G' (with clique and odd-cycle inequalities). We introduce and evaluate a preprocessing method and branch and cut algorithms. Encouraging results consistently improve those previously available in the literature. New feasibility and optimality certificates are provided, and stronger dual bounds are already obtained in the initial linear relaxation of the formulations, even for the hardest instances in the standard benchmark.

Friday October 16 2015, 14:15, room A-284 Johan Oppen Variant of bin-packing problem We present a description and a solution algorithm for a new variant of the well-known two-dimensional bin packing problem with guillotine cuts. The problem is taken from the furniture industry, where boards are cut into parts to build cabinets, tables, shelves, etc. One of course wants to make cutting patterns which minimize the amount of waste, but it is also important to save operating time on the saw. This can be done by utilizing the maximum cutting height on the saw by cutting a stack of boards, all with the same cutting pattern, simultaneously. This means that in addition to minimizing waste, one seeks to minimize the number of stacks of boards to be cut by repeating the same cutting patterns a given number of times corresponding to the maximum height of a stack, which again depends on the maximum cutting height of the saw and the thickness of the boards. Computational testing shows that significant amounts of time can be saved without increasing the amount of waste.

Friday February 20 2015, 13:15, room A-283 Sebastián Urrutia Classic graph theory problems under disjunctive constraints In this talk we tackle two classic graph theory problems under disjunctive constraints. Negative (resp. Positive) disjunctive constraints forbid (resp. force) certain pairs of entities edges of the graph to simultaneously be part of the solution. For the Maximum Acyclic Subgraph problem under positive disjunctive constraints we show that to determine the existence of a feasible solution is an NP-Complete problem and for the same problem under negative disjunctive constraints we propose approximation algorithms. For the Minimum Spanning Tree problem under negative disjunctive constraints we propose a branch & cut approach.

Friday November 7 2014, 13:15, room A-283 Afonso Henrique Sampaio Oliveira The Pickup and Delivery Travelling Salesman Problem with Multiple Stacks In this work, we consider the Pickup and Delivery Travelling Salesman Problem with Multiple Stacks in which a single vehicle must serve a set of customer requests defined by a pair of pickup and delivery destinations of an item. The vehicle contains a fixed number of stacks, where each request is loaded at a pickup location and unloaded at the corresponding delivery location. Each stack has finite capacity, and its loading / unloading sequence must follow the last-in-first-out (LIFO) policy, i.e. for each stack, just the last item loaded can be unloaded at its corresponding delivery location. We propose a new integer programming formulation for this problem with a polyhedral representation described by exponentially-many inequalities and a branch-and-cut algorithm for solving the proposed formulation. Computational results show that our approach is competitive with the best algorithm in the literature. Also, two new certificates of optimality are provided and several optimality gaps are reduced.

Friday November 1 2013, 13:15, room A-283 Yohannes Yebabe Tesfai Fluctuation of the Prices of Crude Oil at International level explained by a Dynamic Discrete Stochastic Models Most energy consuming activities in the world are dependent on energy sources from crude oil. One of the characteristics of the price of crude oil is its high scale of wavering that can directly or indirectly affect the economic progress for both oil exporter and importer nations. The main aim of this study is to assess the fluctuations of the monthly average price of crude oil and price shocks at the international market using the daily recorded data from 1st Jan 2003 to 31st Dec 2012 from OPEC. The Autoregressive Moving Average model with exogenous inputs model (ARMAX) is used as an empirical model. The result of the study reveals that the ARMAX(2,0) discrete stochastic model captures the fluctuation of the log-transformed monthly average price with exogenous inputs of annual-time specific effects. In normal conditions we expect that the price shock is higher at higher price of the commodity. However, astonishingly the monthly average price of crude oil and the price shock in the international market are found to be uncorrelated. The ARIMAX(2,2,1) discrete stochastic model captures the fluctuation of the log-transformed price shock on crude oil with no exogenous input. In general, the problem of handling the fluctuation of the price of crude oil in the international market is not only attributed to unorthodoxies from the mean but also problems of price shocks emanating from unknown factors.

Friday October 5 2012, 13:15, room A-283 Luca Maria Gambardella Ant Colony Optimization for real world vehicle routing problems: from theory to applications Ant colony optimization (ACO) is a metaheuristic for combinatorial optimization problems. In this talk we report on its successful application to the vehicle routing problem (VRP). First, we introduce the basic principles of ant colony optimization, and we briefly present its application to the solution of the VRP and of its variants. Next we discuss the applications of ACO to a number of real-world problems: a VRP with time windows for a major supermarket chain in Switzerland; a VRP with pickup and delivery for a leading distribution company in Italy; a time dependent VRP for freight distribution in the city of Padua, Italy, where the travel times depend on the time of the day; and an on-line VRP in the city of Lugano, Switzerland, where customers’ orders arrive during the delivery process.

Friday September 28 2012, 13:15, room A-283 David Woodruff Software and an Experimental Environment for Stochastic Programming This is a follow-on to last year's talk, where we discussed software for stochastic programming. This year we will focus more on algorithmic issues. We will describe innovations in Progressive Hedging that are important in some logistics applications. Particular emphasis will be on issues related to using the algorithm on large computers with many processors.

Friday September 14 2012, 13:15, room A-283 Hideki Hashimoto An efficient local search framework for vehicle routing problems Vehicle routing problems have a wide range of applications. In this talk, taking the vehicle routing problem with time windows (VRPTW) as an example, I will explain an efficient local search framework that can be applied to many problems and report the computational results for benchmark instances of the VRPTW

Friday August 24 2012, 13:15, room A-283 Teodor Gabriel Crainic Modelling Demand Uncertainty in Two-Tiered City Logistics Planning City Logistics aims to reduce the negative impact of freight-vehicle movements on city-living conditions, particularly in terms of congestion/mobility and environment, while not penalizing its social and economic activities and fostering an efficient and sustainable transportation system. More precisely, one aims to reduce and control the number of freight vehicles operating within the city, improve the efficiency of freight movements and their environmental footprint, and reduce the number of empty vehicle-kilometres in, out, and through the city. The optimized consolidation of loads of different shippers and carriers within the same vehicles and the coordination of the resulting freight transportation activities within the city are key strategies in achieving these goals. In this talk, we focus on the tactical planning of two-tiered City Logistics systems based on these ideas, and investigate the issue of explicitly integrating the variability associated to demand into the tactical-planning processes and models. We describe a two-stage modelling framework, and discuss a number of strategies to adapt the plan to the observed demand together with the associated recourse formulations. Algorithmic and managerial issues related to these formulations are also addressed.

Friday June 1 2012, 13:00, room B-137 Anolan Milanés Programming the GPU with CUDA to accelerate combinatorial optimization problems Programs solving combinatorial optimization problems are commonly computationally intensive. The demand for solution of ever growing instances make parallelization an interesting technique not only for improving execution times, but also to allow solving larger instances. Recent developments on Graphics Processing Units (GPU) made them cheaper and easier to program using frameworks like CUDA or OpenCL. In this talk we describe the CUDA architecture and give a brief introduction on how to write parallel programs using CUDA, in order to take advantage of the potential of these devices.

Tuesday March 27 2012, 11:15, room 202 Mikhail Y. Kovalyov Selected combinatorial problems of logistics and production planning The lecture will present several life situations, which can be modeled as combinatorial optimization problems. Solution approaches will be briefly described. The lecture's plan is:

1. Knapsack and partition problems (project selection, workforce loading), 2. Lot-sizing (planning of production and order quantities), 3. Interval selection (combinatorial auctions, seat reservation), 4. Facility location and e-shopping, 5. Line balancing (design of transfer lines), 6. Vehicle routing (product delivery), 7. Planning and due date negotiation, 8. Batch scheduling.


Tuesday November 8 2011, 12:15, room 284 Olivia R. Liu Sheng Investigating predictive power of stock micro blog sentiment in forecasting future stock price directional movement This study attempts to discover and evaluate the predictive power of stock micro blog sentiment on future stock price directional movements. We construct a set of robust models based on sentiment analysis and data mining algorithms. Using 72,221 micro blog postings for 1909 stock tickers and 3874 distinct authors, our study reveals not only that stock micro blog sentiments do have predictive power for simple and marketadjusted returns respectively, but also that this predictive accuracy is consistent with the underreaction hypothesis observed in behavioral finance. We establish that stock micro blog with its succinctness; high volume and real-time features do have predictive power over future stock price movements. Furthermore, this study provides support for the model of irrational investor sentiment, recommends a complimentary investing approach using user-generated content and validates an instrument that may contribute to the monetization schemes for Virtual Investing Communities.

Friday October 28 2011, 14:15 Ricardo Camargo Benders decomposition for hub location problems In telecommunication and transportation systems, the hub location problem arises when we must flow commodities or information between several origin–destination pairs. Instead of establishing a direct node to node connection from an origin to its destination, the flows are concentrated with others at facilities called hubs. These flows are transported on links established between hubs, being then splitted and delivered to its final destination. Systems with this sort of topology are named hub-and-spoke (HS) systems or hub-and-spoke networks. They are designed to exploit the scale economies attainable through the shared use of high capacity links between hubs. Therefore, the problem is to find the least expensive HS network, selecting hubs and assigning traffic to them, given the demands between each origin–destination pair and the respective transportation costs. In this talk, we present how the Benders decomposition method, a classical exact method for large scale problems, can be used to tackle some hub location problems.

Thursday September 29 2011, 14:15 David Woodruff Software and an Experimental Environment for Stochastic Programming Although stochastic programming is a powerful tool for modeling decision-making under uncertainty, various impediments have historically prevented its wide-spread use. One factor involves the ability of non-specialists to easily express stochastic programming problems as extensions of their deterministic counterparts, which are typically formulated first. A second factor relates to the difficulty of solving stochastic programming models, particularly in the mixed-integer, non-linear, and/or multi-stage cases. Intricate, configurable, and parallel decomposition strategies are frequently required to achieve tractable run-times on large-scale problems. We simultaneously address both of these factors in our PySP software package, which is part of the Coopr open-source Python repository for optimization; the latter is distributed as part of IBM's COIN-OR repository. To formulate a stochastic program in PySP, the user specifies both the deterministic base model (supporting linear, non-linear, and mixed-integer components) and the scenario tree model (defining the problem stages and the nature of uncertain parameters) in the Pyomo open-source algebraic modeling language. Given these two models, PySP provides two paths for solution of the corresponding stochastic program. The first alternative involves writing the extensive form and invoking a standard deterministic solver. For more complex stochastic programs, we provide an implementation of Rockafellar and Wets' Progressive Hedging algorithm. Our particular focus is on the use of Progressive Hedging as an effective heuristic for obtaining approximate solutions to multi-stage stochastic programs. By leveraging the combination of a high-level programming language (Python) and the embedding of the base deterministic model in that language (Pyomo), we are able to provide completely generic and highly configurable solver implementations. PySP has been used by a number of research groups, including our own, to rapidly prototype and solve difficult stochastic programming problems.

September 16 2011 Sebastián Urrutia Graph Theory for Sport Scheduling Sport scheduling consists in deciding the day and the place of each game of a certain sport competition. In this talk we show how Graph Theory helps in the understanding of the problem and in the construction of algorithms capable of generating good schedules. In particular, we show that a very well known method for constructing sport schedules, do not generate good schedules to be used as initial solutions of local search algorithms. Then, we propose an alternative method.

April 15 2011 Jianyong Jin Introduction of Message passing interface(MPI) In the talk, I will introduce the basic information regarding what MPI is and how we can use in parallel programming.

March 18 2011 Jorge Luis Oyola Mendoza Multi-objective VRP In general VRPs with more than one objective, multi-objective, describe better real life situations. Since the decision makers are often in situations where more than one objective should be optimized. The presentation will be based mainly in a paper by Nicolas Jozefowiez, Frédéric Semet and El-Ghazali Talbi (multi-objective vehicle routing problems). In addition, there will be some reference to some methods or algorithms from other publications.

For information about the seminars, or if you want to give a presentation yourself, please contact

Professor Lars Magnus Hvattum

Phone: (+47) 71 21 42 23
E-mail: hvattum@himolde.no