ModRef 2022

The 21st workshop on Constraint Modelling and Reformulation

July 31st, 2022; Part of FLoC 2022

Contact the chairs: modref@a4cp.org

ModRef 2022 is the 21st in a series of workshops on Constraint Modelling and Reformulation organized as part of FLoC 2022, the Federated Logic Conference. It will be held on July 31st, preceding CP 2022, the 28th International Conference on Principles and Practice of Constraint Programming.

Recent years have witnessed significant research devoted to modelling and solving problems with constraints. The importance of modelling and model reformulation is widely recognized. There have been developments in systematic and automated ways of improving aspects of modelling and model reformulation. Tools and techniques which provide the ability to target multiple kinds of solvers were also developed.

The key goals of this workshop are to extend the understanding of constraint modelling and to automate aspects of modelling or model reformulation to extend the reach of constraint solvers on difficult problems and ease the task of modelling. We solicit original papers that contribute to either or both of these goals. Workshop topics include:

Program

The detailed program can also be found on EasyChair

Time Event
Session 1: 9:00 - 10:30 Invited Talk: Constraint modelling and solving: Learning from observing people – Ruth Hoffmann (slides)
  Paper: Solving XCSP3 constraint problems using tools from software verification – Martin Mariusz Lester (paper) (slides)
  Paper: Constraint-based Part-of-Speech Tagging – Neng-Fa Zhou (paper) (slides)
Break: 10:30 - 11:00  
Session 2: 11:00 - 12:30 Paper: A portfolio-based analysis method for competition results – Nguyen Dang (paper) (slides)
  Paper: Efficiently Explaining CSPs with Unsatisfiable Subset Optimization – Emilio Gamba, Bart Bogaerts and Tias Guns (paper) (slides)
  Paper: Automatic Generation of Dominance Breaking Nogoods for Constraint Optimization – Jimmy H. M. Lee and Allen Z. Zhong (paper) (slides)
Lunch: 12:30 - 14:00  
Session 3: 14:00 - 15:30 Invited Talk: A Constraint-Based Tool for Generating Benchmark Instances – Nguyen Dang (slides)
  Modelling competition
Break: 15:30 - 16:00  
Session 4: 16:00 - 17:15 Modelling competition
  17:00: Competition results

Invited Talks

dr. Ruth Hoffmann (University of St Andrews, Scotland) - Constraint modelling and solving: Learning from observing people

Research in constraint programming typically focuses on problem-solving efficiency. However, the way users conceptualise problems and communicate with constraint programming tools is often sidelined. How humans think about constraint problems can be important for the development of efficient tools and representations that are useful to a broader audience. Although many visual programming languages exist, as an alternate for textual representation, for procedural languages, visual encoding of problem specifications has not received much attention. Thus, visualization could provide an alternative way to model and understand such problems. We present an initial step towards better understanding of the human side of the constraint modelling and solving process. We executed a study that catalogs how people approach three parts of constraint programming (1) the problem representation, (2) the problem-solving, and (3) the programming of a solver. To our knowledge, this is the first human-centred study addressing how people approach constraint modelling and solving. We studied three groups with different expertise: non-computer scientists, computer scientists and constraint programmers and analyzed their marks on paper (e.g., arrows), gestures (e.g., pointing), the mappings to problem concepts (e.g., containers, sets) and any strategies and explanations that they provided. We will discuss results and future research this study will hopefully inspire.

(slides)

dr. Nguyen Dang (University of St Andrews, Scotland) - A Constraint-Based Tool for Generating Benchmark Instances

Benchmarking is fundamental for assessing the relative performance of alternative solving approaches. For an informative benchmark we often need a sufficient quantity of instances with different levels of difficulty and the ability to explore subsets of the instance space to detect performance discrimination among solvers. In this talk, I will present AutoIG, an automated tool for generating benchmark instances for constraint solvers. AutoIG supports generating two types of instances: graded instances (i.e., solvable at a certain difficult level by a solver), and discriminating instances (i.e., favouring a solver over another). The usefulness of the tool in benchmarking is demonstrated via an application on five problems taken from the MiniZinc Challenges. Our experiments show that the large number of instances found by AutoIG can provide more detailed insights into the performance of the solvers rather than just a ranking. Cases where a solver is weak or even faulty can be detected, providing valuable information to solver developers. Moreover, discriminating instances can reveal parts of the instance space where a generally weak solver actually performs well relative to others, and therefore could be useful as part of an algorithm portfolio.

(slides)

Modelling Competition

This year, ModRef will host a modelling competition. Teams of up to three members will compete to be the quickest to find the best solutions for different instances of described problems. Teams can compete either on location at FLoC 2022 or remotely. We will organize a chat server to communicate with the teams competing remotely. The problem descriptions will be available from circa 14:45 (UTC+3) and solutions can be submitted until 17:00 (UTC+3), after which the winners will be directly announced.

The official Rules of the competition can be found here

Registration: Google Form, or in-person at FLoC 2022

Competition Results

Rank Score Team Name Members
1 203 Zayenz Mikael Zayenz Lagerkvist
2 166 Picat undisclosed
3 138 Crispy undisclosed
4 102 Helmut Helmut Simonis
5 62 University of Reading undisclosed
6 18 Quokka undisclosed

Important Dates

Paper Abstract Submission May 3rd, 2022
Paper Full Submission May 10th, 2022
Notification of acceptance/rejection June 15th, 2022
Camera ready version July 1st, 2022
Workshop day July 31st, 2022

For questions about the workshop, please contact the chairs dr. Jip J. Dekker and dr. Guido Tack: modref@a4cp.org

Call for Papers

This year ModRef will again paper submissions. In addition to the presentation of research results, we especially welcome submissions of novel (ongoing) work, recent breakthroughs, future directions, and descriptions of interesting aspects of existing systems.

There are two types of paper submissions: extended abstracts (at most two pages) and full papers (at most fifteen pages). References are not part of the page limit. Papers are submitted through EasyChair, as a PDF file following LIPIcs guidelines.

We also accept (and encourage) non-traditional electronic submissions, such as interactive works/tool demonstrations. In this case, please contact the chairs to discuss the suitability of your submission for ModRef.

All submissions will be reviewed and those that are well-written and make a worthwhile contribution to the topic of the workshop will be accepted for publication in the workshop proceedings. The proceedings will be available electronically at CP 2022. Accepted contributions will be allowed a time slot for a presentation at the workshop. At least one author of each accepted paper must attend and present at the workshop. Please note that every workshop participant needs to be registered for the workshop.

Program Committee

Jip J. Dekker (Chair) Monash University
Guido Tack (Chair) Monash University
Emir Demirović TU Delft
María Andreína Francisco Rodríguez Uppsala University
Jimmy H.M. Lee Chinese University of Hong Kong
Kevin Leo Monash University

Previous ModRef Workshops

The ModRef workshop has been running for 21 years and has hosted many interesting presentations.