News

30th June 2017 - Savile Row 1.6.5 Released

This release has just a few changes compared to 1.6.4, despite the fact that more than a year has passed. It is a maintenance release of the 1.6 branch, probably the last one, while most development has been on another branch that will be released as 1.7.0. The main changes in 1.6.5 are improvements to the implied sum constraints generated from AllDifferent and GCC, and speeding up domain filtering by improving the interface between Savile Row and Minion.

We are continuing to bundle Minion 1.8 to be used for the domain filtering feature and as the default backend solver. Java 7 or later is required. Assuming Java is installed, the release should be usable out of the box without downloading any other software. However, any backend solvers other than Minion will need to be downloaded separately.

This release corresponds to an upcoming journal paper.

Peter Nightingale

2nd February 2016 - Savile Row 1.6.4 Released

This new release introduces one new feature that tightens the domains of auxiliary variables (i.e. variables created by Savile Row during tailoring). Also, some minor bugs have been fixed and the documentation has been slightly improved.

We are continuing to bundle Minion 1.8 to be used for the domain filtering feature and as the default backend solver. Java 7 or later is required. Assuming Java is installed, the release should be usable out of the box without downloading any other software.

Peter Nightingale

20th July 2015 - Savile Row 1.6.3 Released

One of the main changes in this release is that Minion is now bundled with Savile Row, and so there are three archives for Linux, Mac and Windows. Each archive includes a static build of Minion 1.8 for the OS. Minion is used for the domain filtering feature and as the default backend solver, so Savile Row can now be used out of the box without downloading any other software.

The SAT backend has been improved since 1.6.2, with better handling of sum constraints. The default SAT solver has been changed to Lingeling because it seems to perform better overall than MiniSat.

The 1.6.3 release corresponds to the CP 2015 paper, Automatically Improving SAT Encoding of Constraint Problems through Common Subexpression Elimination in Savile Row.

Peter Nightingale

28th February 2015 - Savile Row 1.6.2 Released

The main change in 1.6.2 is the addition of the SAT backend. The first iteration of this feature was written by Patrick Spracklen as a summer student project. All constraints in the language have a SAT encoding. MiniSat and Lingeling are fully supported as backend solvers: 1.6.2 can run them, parse the solution and collect some statistics from the solver.

In addition 1.6.2 fixes a few bugs. The most serious is a bug in Active CSE that could cause a negated global constraint to be deleted. Since Active CSE is switched on by default, I would recommend that all users of Savile Row should upgrade to 1.6.2. There are some efficiency improvements particularly in matrix operations.

Finally, the documentation has had some minor improvements, particularly the Essence' tutorial.

Peter Nightingale

13th October 2014 - Savile Row 1.6.1 Released

1.6.1 is a minor release to fix a few bugs, and tidy up and add to the benchmarks included with Savile Row. There are a few new features, possibly the most interesting is the addition (as an optional optimisation) of Active AC-CSE for sums. This type of CSE can match two subexpressions when one is the negation of the other. For example, x-y can be extracted from the expressions x-y+z and y+z-x. This has the potential to improve propagation in the same way as AC-CSE. In this release Active AC-CSE is identical to AC-CSE for And, Or and Product, so it differs only for sums.

This release corresponds very closely to the tutorial at CP 2014 on the topic of automated reformulation. It should be possible to reproduce experimental results in the tutorial using this release of Savile Row and Minion 1.7.

There are some other new features and improvements, see the release notes for details.

Peter Nightingale

1st July 2014 - Savile Row 1.6 Released

There have been many improvements to Savile Row since 1.5. Savile Row now includes Associative-Commutative Common Subexpression Elimination (AC-CSE) as described in a paper at CP 2014 (Automatically Improving Constraint Models in Savile Row through Associative-Commutative Common Subexpression Elimination, Peter Nightingale, Ozgur Akgun, Ian P. Gent, Christopher Jefferson, and Ian Miguel). AC-CSE extracts common parts of associative-commutative expressions such as sums and products. For some problems it can reduce solving time by orders of magnitude by strengthening communication between different parts of the model.

In addition to AC-CSE, Active CSE (by Andrea Rendl et al) has been implemented and is enabled by default. Active CSE performs simple transformations (for example, negating a boolean expression then applying De Morgans law) to reveal common subexpressions and thus reduce the number of auxiliary variables.

Another newly implemented reformulation is collection of simple constraints into global constraints. In this release AllDifferent constraints are created by collecting not-equal, less-than or other shorter AllDifferent constraints, as in CGRASS (Frisch, Miguel and Walsh). This reformulation can be applied whether the simple constraints directly contain decision variables or contain expressions.

Simplifiers of some constraint types have been improved since the last release, for example And, Or, Table and Negative Table.

Output to Gecode (in the FlatZinc language for the fzn-gecode tool) has been improved, and is now much better tested. Savile Row now parses the solution(s) produced by Gecode so it can be used as a drop-in alternative to Minion for solving (however the preprocessing step of applying SAC-Bounds to filter variable domains can only be done with Minion). Other solvers that read FlatZinc should follow.

There are a number of other bugfixes and enhancements, including fixing a bug that affected the gcc constraint, and allowing min and max functions to accept a matrix.

Peter Nightingale

15th January 2014 - Savile Row 1.5 Released

Savile Row has been improved in many ways. The input language is more expressive. New options have been added to remove decision variables that are not needed and filter the domains of decision variables. Savile Row is now able to simplify constraints more effectively. Several bugs have been fixed and the general quality of the code is improved.

A new backend has been added that produces an almost-flat, instance-level subset of MiniZinc, allowing access to more solvers.

Version 1.5 is the first to be open-sourced (under GPL v3). As yet there is no documentation for hacking the internals, but anyone interested in doing so is very welcome to contact me for help on the email address below.

The documentation for users is much improved (and much longer) and has been split into two documents, the Essence' tutorial and the Savile Row tutorial.