Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems

Our paper “Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems” by Landir Saviniec, Maristela Santos, Alysson M. Costa and Lana Santos has been accepted for publication at the European Journal of Operational Research. The paper has part of the results from Landir’s PhD thesis.

[doi] [preprint]
Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems.  Saviniec, L., Santos, M. O., Costa, A.M., Santos, L. M.  European Journal of Operational Research (Accepted, 09/Aug/2019).



High school timetabling problems consist in building periodic timetables for class-teacher meetings considering compulsory and non-compulsory requirements. This family of prob- lems has been widely studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the efficient search of optimal or near-optimal solutions is still a challenge for many problems of practical size. In this paper, we investigate mixed- integer programming formulations and a parallel metaheuristic based algorithm for solving high school timetabling problems with compactness and balancing requirements. We pro- pose two pattern-based formulations and a solution algorithm that simultaneously exploits column generation and a team of metaheuristics to build and improve solutions. Extensive computational experiments conducted with real-world instances demonstrate that our formulations are competitive with the best existing high school timetabling formulations, while our parallel algorithm presents superior performance to alternative methods available in the literature.

Examining Trade-Offs in Piggybacking Flow Events while Making Environmental Release Decisions in a River System

Our paper “Examining Trade-Offs in Piggybacking Flow Events while Making Environmental Release Decisions in a River System” by Kaur, S., Horne, A. C., Nathan, R., Szemis, J. M., Gibson, L., Costa, A. M., Webb, J.A., Stewardson, M. has been published at the Journal of Water Resources Planning and Management.



High flow pulses (or spells or freshes) play a crucial role in maintaining the ecological health of a river system. Impoundment of water in a reservoir and release or diversion of water for human water needs has significantly altered the magnitude and frequency of flow pulses in many river systems, often reducing river ecological health. A limited volume of water is sometimes available for release into the river to reintroduce pulses specifically aimed at meeting ecological requirements (environmental water). If aiming to achieve maximum envi- ronmental benefit, such releases from the reservoir should be timed to augment or piggyback natural unregulated catchment flow events. These decisions must be made in presence of uncertainty of near-future unregulated catchment inflows entering the river. Making flow release decisions under this uncertainty poses the risk of either not achieving the benefit of the environmental flow release because too little envi- ronmental water is released, or of causing flood damage because too much is released. To date, assessment of risks associated with piggy- backing environmental flows have focused solely on the flooding risks. This paper considers assessment of trade-offs between environmental risks and flooding risks while making piggybacking decisions. The key contribution of the paper is a risk framework that allows for the assessment of both flooding and environmental risks when piggybacking of natural flow pulses occurs. The risk framework is used to assess rules or rules with varying levels of piggybacking on the trade-offs between environmental outcomes and flooding risks when releasing piggybacking flows under these rules for flow events under near-future forecast uncertainty. Spawning flows for a key fish species in the Yarra River in southeast Australia is used as a case study to compare three piggybacking rules. DOI: 10.1061/(ASCE)WR.1943- 5452.0001048. © 2019 American Society of Civil Engineers.


Call for papers: III International Conference on Agro Big Data and Decision Support Systems in Agriculture (BigDSSAgro 2019)

The Organizers of the III International Conference on Agro Big Data and Decision Support Systems in Agriculture (BigDSSAgro 2019) would like to invite you to participate in the conference by submitting a contributed paper (extended abstract).

BigDSSAgro 2019 will be held at Universidad Técnica Federico Santa María in Valparaíso, Chile, September 25-27, 2019.

The BigDSSAgro2019 conference is the third conference in the series devoted to decision support systems in agriculture, which combine Operational Research methods and Big Data techniques to support many real-world decision-making problems in small scale farming, industrial agriculture, smart farms, agri-business supply chains, land use and environmental protection, among others. In BigDSSAgro 2019, the scope will be extended to focus on decisions, technologies and innovation for the 2030 agriculture.

Authors are invited to submit extended abstracts of their recent work by May 20, 2019. See the submissions guidelines for more information in the conference web page. The Program Committee will select the papers to be presented on the basis of the submitted extended abstracts. It is expected that revised and extended versions will subsequently be submitted for publication in a post-conference special issue to be announced. The list of topics in which we invite submissions include, but are not limited to the following main areas:

-Operational research methods relevant to agriculture, forestry and environment.
-Sustainability indicators in agriculture and environment.
-Modelling sensor based data to get useful information.
-Big Data techniques with potential applications in agriculture.
-Optimization and simulation models, including agent based simulation.
-Decision support tools based on Big Data and Operational research techniques.
-Decision support tools based on GIS and their implications with Big Data.
-Economic aspects of adoption of Big Data analytics.
-Machine learning.
-Support Vector machine.
-Precision agriculture, digital agriculture.
-Industrial agriculture.
-Small scale farming.
-Agri-business supply chain.
-Land Use.
-Environment studies and environmental protection.

Important dates.
Submission start: April 1, 2019.
Submission deadline: May 20, 2019.
Author acceptance/rejection notification: July 15, 2019.
Camera-ready Extended Abstract deadlines: August 15, 2019.

We look forward to seeing you in Valparaíso.

Kind regards,
Víctor M. Albornoz (Universidad Técnica Federico Santa María)
Alejandro Mac Cawley (Pontificia Universidad Católica de Chile)

Conference General Chairs

A co-evolutionary matheuristic for the car rental capacity-pricing stochastic problem

Our paper “A co-evolutionary matheuristic for the car rental capacity-pricing stochastic problem” by Beatriz Oliveira, Maria Antónia Carravilla, José Fernando Oliveira and Alysson M Costa has been accepted for publication at the European Journal of Operational Research. This paper contains part of the results from Beatriz’s PhD thesis.

Link to paper.


When planning a selling season, a car rental company must decide on the number and type of vehicles in the fleet to meet demand. The demand for the rental products is uncertain and highly price-sensitive, and thus capacity and pricing decisions are interconnected. Moreover, since the products are rentals, capacity “returns”. This creates a link between capacity with fleet deployment and other tools that allow the company to meet demand, such as upgrades, transferring vehicles between locations or temporarily leasing additional vehicles.

We propose a methodology that aims to support decision-makers with different risk profiles plan a season, providing good solutions and outlining their ability to deal with uncertainty when little information about it is available. This matheuristic is based on a co-evolutionary genetic algorithm, where parallel populations of solutions and scenarios co-evolve. The fitness of a solution depends on the risk profile of the decision-maker and its performance against the scenarios, which is obtained by solving a mathematical programming model. The fitness of a scenario is based on its contribution in making the scenario population representative and diverse. This is measured by the impact the scenarios have on the solutions.

Computational experiments show the potential of this methodology regarding the quality of the solutions obtained and the diversity and representativeness of the set of scenarios generated. Its main advantages are that no information regarding probability distributions is required, it supports different decision-making risk profiles, and it provides a set of good solutions for an innovative complex application.

Algorithms for the power-p Steiner tree problem in the Euclidean plane

Our paper “Algorithms for the power-p Steiner tree problem in the Euclidean plane” by Christina Burt, Alysson Costa and Charl Ras has been published on a special issue on Exact and Heuristic Solutions for Optimization Problems from RITA.

Link to the full text.


We study the problem of constructing minimum power-$p$ Euclidean $k$-Steiner trees in the plane. The problem is to find a tree of minimum cost spanning a set of given terminals where, as opposed to the minimum spanning tree problem, at most $k$ additional nodes (Steiner points) may be introduced anywhere in the plane. The cost of an edge is its length to the power of $p$ (where $p\geq 1$), and the cost of a network is the sum of all edge costs. We propose two heuristics: a “beaded” minimum spanning tree heuristic; and a heuristic which alternates between minimum spanning tree construction and a local fixed topology minimisation procedure for locating the Steiner points. We show that the performance ratio $\kappa$ of the beaded-MST heuristic satisfies $\sqrt{3}^{p-1}(1+2^{1-p})\leq \kappa\leq 3(2^{p-1})$. We then provide two mixed-integer nonlinear programming formulations for the problem, and extend several important geometric properties into valid inequalities. Finally, we combine the valid inequalities with warm-starting and preprocessing to obtain computational improvements for the $p=2$ case.

Active management of environmental water to improve ecological outcomes

Our paper “Active management of environmental water to improve ecological outcomes” has been published at the Journal of Water Resources Planning and Management.

[doi] [cited by] [preprint] Active management of environmental water to improve ecological outcomes.  Horne, A., Kaur S., Szemis, J., Costa, A.M., Nathan, R., Angus Webb, J., Stewardson, M., Boland, N. , Journal of Water Resources Planning and Management 144 (2018)


Environmental water is being embraced by governments around the world as a means to partly restore rivers impacted by excessive river regulation and to protect those that are not yet overregulated. In cases where environmental water is provided as a water right, managers can make ongoing active management decisions regarding the timing and magnitude of environmental flows in response to changing conditions and understanding of environmental demands. Such active management should lead to improved environmental outcomes but also comes with a significant ongoing management cost when compared to rules-based environmental water releases. This study uses an optimization tool to examine the environmental gain achievable with the active management of environmental water compared to rules-based releases. A case study of the Yarra River, Victoria, Australia, demonstrates the potential for substantial environmental gains achieved through active management of environmental water.


Congratulations to Dr. Cheng Cheng

Cheng Cheng has had her PhD thesis approved at the University of Melbourne. Her thesis is titled “Optimisation of Disaster Waste Management Systems” and proposes models and algorithms for planning waste removal after disasters. Among other results, Cheng analysed the effect of using intermediate waste processing centers in the efficiency of the operations.

Congratulations to Cheng!




Congratulations to Dr. Beatriz Oliveira

Beatriz Brito Oliveira has defended her PhD thesis at the University of Porto. Her thesis is titled “Fleet and revenue management in car rental: quantitative approaches for optimization under uncertainty” and was supervised by Prof. Maria Antònia Carravilla and Prof. José Fernando Oliveira.

Beatriz spent three months with our research group in Melbourne. During this time she worked in the last chapter of her thesis, finalising the development of a matheuristic for the stochastic version of the car rental planning problem she tackled.

Congratulations to Beatriz, Maria Antònia and José Fernando for this strong piece of research!

Optimising elective surgery schedules

Our paper A Sequential Stochastic Mixed Integer Programming Model For Tactical Master Surgery Scheduling, by Ashwani Kumar, Mark Fackrell, Peter Taylor and Alysson M. Costa is now available online.


In this paper, we develop a stochastic mixed integer programming model to optimise the tactical master surgery schedule (MSS) in order to achieve a better patient flow under downstream capacity constraints. We optimise the process over several scheduling periods and we use various sequences of randomly generated patients’ length of stay scenario realisations to model the uncertainty in the process. This model has the particularity that the scenarios are chronologically sequential, not parallel. We use a very simple approach to enhance the non-anticipative feature of the model, and we empirically demonstrate that our approach is useful in achieving the desired objective. We use simulation to show that the most frequently optimal schedule is the best schedule for implementation. Furthermore, we analyse the effect of varying the penalty factor, an input parameter that decides the trade-off between the number of cancellations and occupancy level, on the patient flow process. Finally, we develop a robust MSS to maximise the utilisation level while keeping the number of cancellations within acceptable limits.


Returning in 2018, AMSI Optimise is an annual networking and research-training event that aims to strengthen mathematical optimisation research engagement and its applications across industry.

This event will comprise a three-day industry-focused conference, followed by a two-day research workshop. The symposium features expert and end-user talks, international guest speakers, collaboration showcases, industry challenge sessions and tutorials. The themes of the 2018 conference are Decision Making Under Uncertainty and Humanitarian Applications.

AMSI Optimise is aimed at:

  • anyone using optimisation, with opportunities to learn more about the current state of the art and to connect with others who have similar interests
  • industry practitioners interested in exploring the benefits of engagement with optimisation research
  • academics and postgraduate students wanting to better understand drivers and needs in this area

The event provides a forum to bring together people from the diverse companies and research disciplines that use and develop optimisation models and software. It provides a platform for research training and developing new collaborations in this vital area through PhD internships, research partnerships and postgraduate research projects.