Sep 20

International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research in Delft

I’m co-chairing the 15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR) with Willem-Jan van Hoeve. It will be will be held in Delft, The Netherlands, June 26-29, and co-located with the 28th International Conference on Automated Planning and Scheduling (ICAPS). We have just sent out the call for papers. Please submit!

The aim of the conference is to bring together interested researchers from Constraint Programming (CP), Artificial Intelligence (AI), and Operations Research (OR) to present new techniques or applications and to provide an opportunity for researchers in one area to learn about techniques in the others. A main objective of this conference series is also to give these researchers the opportunity to show how the integration of techniques from different fields can lead to interesting results on large and complex problems. Therefore, papers that actively combine, integrate, or contrast approaches from more than one of the areas are especially solicited. High quality papers from a single area are also welcome, if they are of interest to other communities involved. Application papers showcasing CP/AI/OR techniques on novel and challenging applications or experience reports on such applications are strongly encouraged.

The program committee invites submissions that include but are not limited to the following topics:

  • Inference and relaxation methods: constraint propagation, cutting planes, global constraints, graph algorithms, dynamic programming, Lagrangian and convex relaxations, heuristic functions based on constraint relaxation.
  • Search methods: branch and bound, intelligent backtracking, incomplete search, randomized search, portfolios, column generation, Benders decompositions or any other decomposition methods, local search, meta-heuristics.
  • Integration methods: solver communication, model transformations and solver selection, parallel and distributed solving, combining machine learning with combinatorial optimization.
  • Modeling methods: comparison of models, symmetry breaking, uncertainty, dominance relationships.
  • Innovative applications of CP/AI/OR techniques.
  • Implementation of CP/AI/OR techniques and optimization systems.

Submissions are of two types: regular papers (submitted for publication and presentation) and extended abstracts (submitted for presentation only). Outstanding regular paper submissions may be invited to be published directly in the journal Constraints through a “fast track” process.

This year’s conference will also introduce a distinguished paper award and a student paper award.

Sep 08

Scientific advisor at Dutch Railways (NS)

Last week I started at the Dutch Railways in Bob Huisman’s group on Maintenance Development as a scientific advisor, for one day a week. My aim is to support and further increase the exchange of knowledge and experience between Dutch Railways and Delft University of Technology. I aim to contribute new scientific developments in the area of algorithm design to this practical scheduling problem, but also to learn about important research questions regarding real-life problems. Concretely, I’m advising master and PhD students doing an internship with NS on the development of algorithms for shunting and service/maintenance logistics. The research group at NS consists of an inspired bunch of master students, PhD students and some tenure staff, all with strong ties to Utrecht, Erasmus, Eindhoven, Twente, or, of course, Delft University. I immediately felt at home.

These first two days consisted mainly of reading, listening, and learning. My expectations were more than just confirmed: this practical problem is significantly more complex than my typical benchmark problem. In fact this shunting problem can be seen as a combination of five (!) more basic/general problems such as matching, flow shop, path finding, etc.. In addition there are many “dirty details” (exceptions, security-related conditions, etc.), real data is incomplete, the realised situation may actually be different from the problem input, and using all of this effectively will require a significant change in the organisation. I like a good challenge!

The current algorithmic state of the art is a very smart local search approach by Roel van den Broek which he presented last Wednesday at the International Conference on Operations Research in Berlin. I have two concrete ideas to continue from this: I’d like to improve the quality of the results from the local search by embedding it in a branch-and-bound algorithm, and I’d like to get result that are a bit more robust to changes by applying ideas from robust and stochastic optimisation, while still using the local search procedure. I’m happy I also found a good student who wants to work with me, because this may be a but more work than just one day a week. Contact me or stay tuned for more.

Aug 23

Vacancy for a post-doctoral researcher in Algorithmics in Delft

We have an open position for a post-doctoral researcher in the Algorithmics group in TU Delft.

Aug 21

Solving Road Congestion Problems with Algorithms?

State-of-the-art in-car navigation systems contribute to preventing road congestion, because avoiding traffic jams helps dissolving it. Currently, the more advanced systems already are using both historic travel times as well as recently observed travel times to estimate future travel times for road segments, and base their route navigation advice upon these estimates. However, in our publication on Intention-Aware Routing of Electric Vehicles, we show that estimated travel times can be made even more accurate by also including the navigation advice for other vehicles, even though this may be dependent on later traffic conditions.

 

The published article shows the effect of exchanging such information on the combined travel and charging time of Electric Vehicles (EVs). The driving range of EVs depends on their installed battery capacity, which is limited because batteries are large, heavy, and costly. Consequently, for longer drives they need to recharge, in a way similar to the refueling of fossil-fuel-based vehicles. Very different, however, is the time it typically takes for such a refill: for EVs this can typically take 30 minutes, even on the fastest charger available. This is a problem in particular when the capacity at recharging stations is limited: if a driver arrives at a charging station (with an almost empty battery) and has to wait for another car to be charged first, this has a detrimental effect on the total travel time. Apart from the solution to design such charging stations for peak capacity requirements, solutions have been proposed to better coordinate the time and location where vehicles charge.

 

For example, a charging station could offer a reservation system where drivers can book a charging slot in advance as soon as they know at what time they will arrive at the station. Systems like these have been around for many years in other domains, e.g., for administration purposes at governmental front desks, restaurants, etc.. However, this system leads to significant inefficiencies when arrival conditions are uncertain. In particular this holds for travel times, since these may be very uncertain especially around peak times when such reservations matter. Reserving a larger time window introduces extra (lost opportunity) costs on the side of the charging station, or booking a later slot introduces extra costs on the side of the driver.

 

The solution proposed and evaluated in our research is a cooperative one, where all drivers share and coordinate their charging plans among themselves (conditional on encountered delays). We show which algorithmic solution can be used to combine stochastic information based on historic travel information with stochastic plans (policies) for routing and charging, and how this can be used for coordinating these policies. We show that this results in significantly reduced total travel times. If now only cars could use this system to coordinate road usage…

Aug 07

Funding awarded for project with Eindhoven in program Big Data: real time ICT for logistics

Geert-Jan van Houtum, Onno Boxma, Uzay Kaymak, Alp Akcay, Rik Eshuis, Willem van Jaarsveld, Stella Kapodistria, and Yingqan Zhang from Eindhoven University and Sicco Verwer and me from Delft have been awarded a grant for our research proposal on Real-time data-driven maintenance logistics with support from Philips, Fokker, and Nederlandse Spoorwegen.

Sicco and I will work with a post-doc on using learned predictive models for making real-time decisions regarding maintenance and service logistics, such that (i) possible predictive errors have little effect on the follow-up optimization problems, while (ii) the resulting optimization problems will be efficiently solvable. See also this NWO news post (in Dutch).

Jul 25

Learning by Teaching

Our master’s level course on Economics and Computation is given in the form of a seminar, using the principle of “learning by teaching“. We are quite happy with the current setup, so here I’d like to share some of the details.

The objectives of the course are first, that students can recognize situations where both computational and strategic aspects play a role and have an overview of known results, and second, that they have some in-depth experience with at least one of such situations (so, T-shaped).

 

As in many seminar-based courses, students are asked to form pairs and select one of the chapters in the book to prepare. What I think is less common, is that we ask them not only to give a (preferably interactive) lecture on that chapter, but also to select learning objectives, prepare and check homework exercises, and to prepare exam questions. We support them in a one-to-one meeting to discuss the lecture plan, where we also discuss the basics of teaching: aligning learning objectives, instructional method, and the assessment, and stress that learning occurs based on student activities, and is no direct consequence of activities of the teacher.

Next to this, students are asked to write an extension to their selected chapter: which topic in the literature is related but not included in the book? To be able to do this, students need to look into the literature (besides the book), and write about what they have read in their own words. Their first draft then is peer-reviewed, requiring them to think also about how their own text comes across to other students.

I think with this, we very effectively meet the learning objectives we set for our course: students get actively involved in the material and simultaneously practice with skills that are useful in any future job such as finding literature, explaining, and writing. Perhaps this setup is useful for some other courses as well?

Jul 25

Economics and Computation

Computer Science (CS) students need to learn about more than just pure CS. With the advancement of electronic markets, game theory turns out to be relevant for CS in many real-life situations. Where before, the matching of residents to hospitals and of kidney donors to patients through a nation-wide program were the main successes on the border of algorithm design and economics, nowadays some background in both economics and computer science is necessary to fully understand auctions for on-line advertisement and wireless frequencies, incentives (user motivation) in file-sharing, recommender systems, reputation systems, and digital currencies, among others.
David Parkes (Harvard) and Sven Seuken (University of Zurich) have written a book covering a large number of such examples. The book discusses the required background for truly understanding these economic systems and the respective computational considerations at a level accessible to master students in CS. At the moment of writing, the book still has to be published (see http://economicsandcomputation.org), but we were fortunate enough to be allowed to use some chapters in a masters-level course in Delft.
The objectives of the course are that students become aware of when it makes sense to consider not only the algorithmic/computational aspects of a problem, but also possible strategic behavior, and that they know where to look for. To reach these objectives, students are asked to form pairs and select one of the chapters in the book to prepare a lecture for. They are also asked to write an extension to their chapter: which topic in the literature is related and relevant, but not included in the book?
In last semester’s run of the course the topics for the extensions were the following:
  • Ch 5: account for fairness in peer-to-peer file sharing
  • Ch 9: give bounds on (randomized) truthful mechanisms
  • Ch 10: estimate click-through rates in ad-auctions
  • Ch 11: special cases in winner determination of combinatorial auctions
  • Ch 12: many-to-one matching
  • Ch 15: aggregate search results in meta-search engines
  • Ch 22: strategic behavior in block-chain mining pools
The book authors wrote me they very much liked the of the setup of the course and were impressed with the resulting extensions. I’m happy we have some good students in Delft!

Jul 15

Scheduling on Board a Navy Vessel

On board of a navy vessel there many activities need to be performed by the crew. When assigning these activities to crew members certain constraints have to be taken into account, such as that crew members can only perform one activity at a time, some activities can be carried out only by a subset of qualified crew members, and some activities may depend on others.

Three of our bachelor students have just completed a two-month project to support human planners with this complex scheduling task. In this project, they have analyzed the complexity of this problem (yes, it is complex: NP-complete), found and compared several translations to a mathematical program (such that it can be solved by a state-of-the-art solver such as Gurobi), and implemented a user interface for the human planner. Their report on all of this can be found in the TU Delft repository.

Jul 05

Future-proof Flexible Charging

After my pitch at the AMS Summer Event, the AMSTERDAM INSTITUTE FOR ADVANCED METROPOLITAN SOLUTIONS published a nice article about our research on algorithms for flexibly charging electric vehicles.