conjure-cp / vip Goto Github PK

The rust native interface for chuffed has not been fully completed. A new project could aim to complete this by either implementing a representation of the Problem class from Chuffed in Rust or by representing Chuffed’s global state called FlatZincSpace.

Additionally, this project could also create the solver adaptor layer for chuffed. A solver adaptor
layer translates a model into solver-specific data structures and runs the solver.

Relevant issues and pull requests from last semester's work on this project:

• Chuffed: initial commit

• Add wrappers for basic chuffed functions and example program using these wrappers

• Turn example main program into rust test

• Issues with creating XYZ problem in cpp

• Chuffed Bindings

• Chuffed: linking errors on Alma Linux and Fedora

A small project for any vim users that pass by :)

Background
I quickly hacked together a few essence language detection plugins and the Conjure LSP server to create a neovim plugin for writing Conjure models. This detects the essence filetype, provides basic highlighting, and runs the LSP server for us.

https://github.com/niklasdewally/conjure.nvim

It is a bit hacky still, so:

1. It needs documentation hover support.
2. It supports the conjure vscode snippets, but I just manually copied them into the repo - these could be refactored out into their own repo so that multiple language extensions (including this one and #12) can use it.
3. Proper docs and testing are not there yet.
4. This plugin amalgamates various random "essence in vim" plugins I found in Github search. Having a properly defined vim "user workflow" in the official documentation would be helpful.
5. Not sure if this is possible, but adding Conjure to nvim-lspconfig and Mason and so on would be good.

As conjure.nvim mainly uses the LSP server and VSCode snippets, it should not require much maintenance in itself - the main challenge is working out how to keep the LSP and snippets up to date across multiple editor plugins.

Related work

#12 suggests a similar extension for IntelliJ.

Further to discussion in the meeting last week, I've looked a little into block, "scratch" editors. blockly seems promising, with the ability to write plugins in JS.

This will be reasonably straightforward and would allow conjure-oxide to reach full feature coverage very quickly. We output textual essence prime and call savilerow for solving.

The main aim of this sub-project is development of real-world / functional parametric files to represent Travelling Salesman Problem or Capacitating Vehicle Routing Problems.

Current problems within the solved CSPLib repository concerning either TSP or CVRP do not have visualisable parametric files as the values are purely fictitious and do not represent 2D or even 3D distances between nodes. The generation of data sets which can be visualised in the 2D space would allow better testing of the Essence files provided, and visualisation programs developed from this would then be generalisable across all nodal graphs.

Introduction

Quite a few puzzle games, such as sokoban, ricochet robots, rubik’s cube, etc .. can be described as planning problems. That is, an initial state of the board, a set of actions that can be taken and a goal state that has to be reached.

These kind of problems are usually modelled in constraints by using a planning as satisfiability approach. That is, given a problem instance (the initial state, a set of actions, a goal) and a horizon length, a formula is generated so that the formula is satisfiable if and only if there is a plan (a sequence of actions) with the given horizon length. A plan can be found by testing the satisfiability of the formulas for different horizon lengths. The simplest way of doing this is to go through horizon lengths sequentially, 0, 1, 2, and so on.

Proposal

This project builds on the "software engineering" strand of the VIP and proposes to first understand and then gradually extend and improve a current project named PyPMT

More concretely, once understood how planning as satisfiability works, a few things that can be done:

• pySMT can be integrated to test different SMT solvers
• Instead of going through horizon lengths sequentially, more intelligent methods can be used
• New encodings from literature can be implemented
• Understanding and visualising how the search is being done
• Hardening the library and ensuring its correctness
• Building a website and set of visualisations of various benchmarks and showing how they are solved
• and much more!

Resources

• Z3 and some of its documentation
• “Artificial Intelligence: A Modern Approach” is a classic book that has a full chapter on “Classical Planning”. The link from the library is this one

Migrate some conjure extension functions from Vscode to intelli J, And it is also updated in sync with Vscode.

Haskell has a property based testing library called quickcheck, that was later reimplemented in many languages.

These libraries are (among other things) able to generate random members of algebraic datatypes. This is very useful for property based testing.

One shortcoming is the ==> operator. It's a great idea (i.e. only use values that pass a given precondition as test cases) however it's implementation is generate-and-test. We can do better.

Project is to use CP to replace the generators and the ==> operator.

Not necessarily a conjure-oxide project in the first instance. Can be implemented in Haskell/Python/Idris/Rust/whatever as a proof of concept. Integrating into mainstream langugaes would be ideal, but not it's not the first challenge.

We currently use/abuse conjure's parser - at some point we need to implement a parser in Rust.

This needs to be tested thoroughly against the existing parser. Both for well-formed input and for error messages. To be clear: the error messages do not have to be identical, but shouldn't be worse than those of the existing parser.

This project has clear boundries and can be achieved by one student. Could also be an SH project.

For future VIP candidates curious to explore the visualisation side of constraint programming problems, an accessible way to start and contribute to the existing library would be to tackle the following CSPLib problems:

• Problem 012: Nonograms

• Problem 015: Schur’s Lemma

• Van Der Waerden Numbers (similar to Langford)

These are all well-defined and easy theory, with some obvious visualisations available. They would also be a good way for new VIP students to explore Conjure.

The backend for the demos (https://conjure-cp.github.io/demos/) runs on a VM in CS at the moment.

This VM has a fixed number of cores and memory. This is not ideal since the machine sits idle most of the time, but could use 32 cores when multiple requests arrive at the same time.

The backend code is fairly simple and is hosted here: https://github.com/conjure-cp/conjure-aas

The project is to explore flexible / elastic solutions which would allocate more resources on demand and scale up/down as required.

This can be done within the CS resources and network (using something like Kubernetes) or on a cloud provider (using something like Amazon lambda).

• Build automatic error checks into documentation edits.

• check for spelling and grammar errors, and incorrect URLs.

• Check all the cells in a notebook run (possible manual overrride option?)

• Warning for out of date notebook extension versions.

There are quite a lot of 'grid based puzzle' (sudoku and it's 400 variants, star battle, I can go find a list).

It would be nice (I would like!) a visualiser for all these different types of puzzles, and also Essence models for them (Essence models already exist for some of them, but they aren't organised and aren't in CSP lib).

There already exists work from St Andrews related to this at https://github.com/stacs-cp/Demystify-Visualiser . However, this is a full web app, I personally would like something it was easy to use stand-alone, which could make SVGs? I'm happy to talk further about this.

Conjure tries to cache models when they are generated. However, this code has some significant limitations:

• Not thread/process safe
• If you solve a different problem, it over-writes the first problem's cache.

It would be great to have a more general caching framework. This could cache:

• Generated Essence'
• Generated SAT / minion / etc models
• Answers to problems

These caches should be designed from the start to be process and thread safe. I suggest (but open to suggestions!) this cache runs as a seperate program, maybe using sqlite (or similar), where programs can query for cache values, store them, and read them back out.

basically conjure-cp/conjure#633. Investigate how the VSCode extension works, so that each of the bits documentation is found when the keywords is highlighted.

One of the big challenges with creating an interface for Chuffed was that the C++ features it uses make translating it to Rust very difficult to do. Additionally, rust-specific bindings did not exist for it like they did for something like SAT. A new project could implement support for a new solver that works well with rust and that ideally already has rust bindings.

Google’s ORTools is an open-source tool suite for solving combinatorial optimization. It contains two constraint programming solvers CP* and CP-SAT which already have rust bindings. ORTools is very powerful and quite popular so we would realistically support it sooner or later. From my brief look over the solvers, it seems like it could be much easier to implement than Chuffed and there already seem to be rust bindings created for ORTools.

Relevant links:

• ORTools GitHub page
• ORTools Google developer page

conjure-oxide needs an exhaustive testing infrastructure. This is mainly for correctness and performance testing in comparison to conjure. Tests should be run through Github actions, can make use of hosted VMs (by github or by CS) and should produce a dashboard on github pages for each run.