Research

Interests

My main research interest is in constraint programming and more generally the techniques, methods, and theory of solving combinatorial (optimization) problems. However, I really enjoy learning new things and thinking about them. Here is an incomplete list of areas that I have at some point investigated

  • Constraint programming
  • Compilers
  • Formal methods
  • Programming languages
  • Programming paradigms
  • Algorithms and data structures
  • Complexity theory
  • Distributed systems
  • Geometric algorithms
  • Computer game playing
  • Programming competitions
  • The practice of programming (what does it mean to code in a professional setting)
  • How to structure and code a GUI
  • Teaching programming and computational thinking
  • Typesetting
  • Database implementations

Research software

Gecode is a constraint programming system. It is a toolkit that can be used both for creating applications and for developing new constraint programming systems.

My main research in constraint programming was done while being the third core team members of Gecode from before it was released. The most recent code for Gecode can be found on GitHub.

While publications are often viewed as the main scientific output of a researcher, I think my most important contribution is the time I spent on helping develop Gecode. As a measure of the impact, a Google Scholar search for Gecode shows more than 1600 results.

All publications

2018

Monte Carlo Methods for the Game Kingdomino

Magnus Gedda, Mikael Z. Lagerkvist, and Martin Butler

Kingdomino is introduced as an interesting game for studying game playing: the game is multiplayer (4 independent players per game); it has a limited game depth (13 moves per player); and it has limited but not insignificant interaction among players.

Several strategies based on locally greedy players, Monte Carlo Evaluation (MCE), and Monte Carlo Tree Search (MCTS) are presented with variants. We examine a variation of UCT called progressive win bias and a playout policy (Player-greedy) focused on selecting good moves for the player. A thorough evaluation is done showing how the strategies perform and how to choose parameters given specific time constraints. The evaluation shows that surprisingly MCE is stronger than MCTS for a game like Kingdomino.

All experiments use a cloud-native design, with a game server in a Docker container, and agents communicating using a REST- style JSON protocol. This enables a multi-language approach to separating the game state, the strategy implementations, and the coordination layer.

Forthcoming in: IEEE Conference on Computational Intelligence and Games 2018. To be held in Maastricht, The Netherlands, August 14-17, 2018.

pdf arxiv

2013

Laser Cutting Path Planning Using CP

Mikael Z. Lagerkvist, Martin Nordkvist, and Magnus Rattfeldt

Sheet metal cutting using lasers is ubiquitous in the industry, and is used to produce everything from home decorations to excavator scoops. Metal waste is costly for the industry, both in terms of money, but also in terms of an increased environmental footprint. Tomologic develops a unique optimisation system that can reduce this waste drastically. This paper presents a CP approach to the Laser Cutting Path Planning Problem (LCPPP), a very hard important sub problem within the Tomologic optimisation system. A solution to the LCPPP is, given a packing of some details on a metal sheet, an ordering of the cuts necessary to separate the details from the sheet. The problem is complicated by physical factors such as heat from the laser beam, or details moving or flexing. In the paper, we explain the problem in detail and present our CP approach that we developed for solving the problem. The possibility (in CP) of custom search heuristics turned out to be crucial to be able to solve the problem efficiently, as these could be made to guide the search to good first solutions.

In: Christian Schulte, editor. Principles and Practice of Constraint Programming - 19th International Conference, {CP} 2013, Uppsala, Sweden, volume 8124 of Lecture Notes in Computer Science, pages 790–804. Springer, September 2013. DOI 10.1007/978-3-642-40627-0

Copyright Springer-Verlag, the original publication is available at www.springerlink.com

pdf

2010

Modeling and Programming with Gecode

Christian Schulte, Guido Tack, Mikael Z. Lagerkvist.

Modeling and Programming with Gecode provides comprehensive documentation of how to model and program with Gecode.

The first part of the document explains modeling and solving constraint problems with Gecode. It explains how to program, compile, link, and execute these models. It provides an overview of integer, Boolean, and set variables and constraints, modeling support, search, and Gist. This is complemented by a collection of interesting case studies of how to model with Gecode.

The remaining, more advanced, parts are about programming with Gecode. They explain in great detail and with numerous examples the concepts and techniques for programming constraints, branchings, search engines, and new variable types with Gecode. The parts’ coverage puts users on par with Gecode’s developers.

Technical documentation, 2010.

pdf

2009

Propagator Groups

Mikael Z. Lagerkvist and Christian Schulte.

This paper introduces propagator groups as an abstraction for controlling the execution of propagators as implementations of constraints. Propagator groups enable users of a constraint programming system to program how propagators within a group are executed.

The paper exemplifies propagator groups for controlling both propagation order and propagator interaction. Controlling propagation order is applied to debugging constraint propagation and optimal constraint propagation for Berge-acyclic propagator graphs. Controlling propagator interaction by encapsulating failure and entailment is applied to general reification and constructive disjunction. The paper describes an implementation of propagator groups (based on Gecode) that is applicable to any propagator-centered constraint programming system. Experiments show that groups incur little to no overhead and that the applications of groups are practically usable and efficient.

In: Ian Gent, editor, Fifteenth International Conference on Principles and Practice of Constraint Programming, Lisbon, Portugal, volume 5732 of Lecture Notes in Computer Science, pages 524-538. Springer-Verlag, September, 2009. DOI 10.1007/978-3-642-04244-7_42.

Copyright Springer-Verlag, the original publication is available at www.springerlink.com

pdf

2008

Techniques for Efficient Constraint Propagation

Mikael Z. Lagerkvist.

This thesis explores three new techniques for increasing the efficiency of constraint propagation: support for incremental propagation, improved representation of constraints, and abstractions to simplify propagation.

Support for incremental propagation is added to a propagator-centered propagation system by adding a new intermediate layer of abstraction, advisors, that capture the essential aspects of a variable- centered system. Advisors are used to give propagators a detailed view of the dynamic changes between propagator runs. Advisors enable the implementation of optimal algorithms for important constraints such as extensional constraints and Boolean linear in-equations, which is not possible in a propagator-centered system lacking advisors.

Using Multivalued Decision Diagrams (MDD) as the representation for extensional constraints is shown to be useful for several reasons. Classical operations on MDDs can be used to optimize the representation, and thus speeding up the propagation. In particular, the reduction operation is stronger than the use of DFA minimization for the regular constraint. The use of MDDs is contrasted and compared to a recent proposal where tables are compressed.

Abstractions for constraint programs try to capture small and essential features of a model. These features may be much cheaper to propagate than the unabstracted program. The potential for abstraction is explored using several examples.

These three techniques work on different levels. Support for incremental propagation is essential for the efficient implementation of some constraints, so that the algorithms have the right complexity. On a higher level, the question of representation looks at what a propagator should use for propagation. Finally, the question of abstraction can potentially look at several propagators, to find cases where abstractions might be fruitful.

An essential feature of this thesis is an novel model for general placement constraints that uses regular expressions. The model is very versatile and can be used for several different kinds of placement problems. The model applied to the classic pentominoes puzzle will be used through-out the thesis as an example and for experiments.

Licentiate dissertation, Royal Institute of Technology, 2008.

pdf

Modeling Irregular Shape Placement Problems with Regular Constraints

Mikael Z. Lagerkvist and Gilles Pesant.

The regular constraint is a powerful global constraint with many possible uses. It was introduced to model certain common constraints in rostering problems. In this paper we show how to use it to model placement problems with irregular shapes. The technique is illustrated by solving Pentominoes and Solitaire Battleships. The efficiency of the basic model is improved by projecting out irrelevant information. Experimental results on Pentomino packing benchmark instances indicate that this simple approach can be competitive with specialized algorithms. From the applications we can identify some areas for improvement in the implementation of regular constraints.

First Workshop on Bin Packing and Placement Constraints BPPC’08. 2008.

pdf

2007

Advisors for Incremental Propagation

Mikael Z. Lagerkvist and Christian Schulte.

While incremental propagation for global constraints is recognized to be important, little research has been devoted to how propagator-centered constraint programming systems should support incremental propagation. This paper introduces advisors as a simple and efficient, yet widely applicable method for supporting incremental propagation in a propagator-centered setting. The paper presents how advisors can be used for achieving different forms of incrementality and evaluates cost and benefit for several global constraints.

In: Christian Bessière, editor, Thirteenth International Conference on Principles and Practice of Constraint Programming, Providence, RI, USA, volume 4741 of Lecture Notes in Computer Science, pages 409-422. Springer-Verlag, September, 2007. DOI 10.1007/978-3-540-74970-7_30

Copyright Springer-Verlag, the original publication is available at www.springerlink.com

pdf

2005

Machine Assisted Reasoning for Multi-Threaded Java Bytecode

Mikael Lagerkvist

In this thesis an operational semantics for a subset of the Java Virtual Machine (JVM) is developed and presented. The subset contains standard operations such as control flow, computation, and memory management. In addition, the subset contains a treatment of parallel threads of execution.

The operational semantics are embedded into a μ-calculus based proof assistant, called the VeriCode Proof Tool (VCPT). VCPT has been developed at the Swedish Institute of Computer Science (SICS), and has powerful features for proving inductive assertions.

Some examples of proving properties of programs using the em bedding are presented.

Master’s thesis, KTH - Royal Institute of Technology, 2005.

pdf