LearnieCP

A constraint solver written completely in Julia. It is heavily inspired by MiniCP. The intent of this project is for pedagogical purposes. However, as development has continued, it seems like in time, it shall be released for use in development & production systems.

---

High Level Architectural View

This is a very very high level view of the components that make up the Engine. The problems the solver aims to provide a means to solve are Discrete and Deterministic. So far, there's only support for Integer variables - though not or long - rich variables will be introduced in time.

This work will be accompanies with an online book describing everything in it.

The current implementation includes:

The Core

• Domains
  • AbstractDomain functions
  • Domain Listener implementation
  • StateBitSet
  • StateSparseSet
  • SparseSetDomain

Here's an overview of the domain representaion:

• Variables
  • AbstractVariable functions
  • IntVar implementation
  • IntVarArray implementation
  • Variable views:
    • IntVarMultView
    • IntVarOffsetView
• Constraint shell definition
  • AbstractConstraint functions
  • ConstraintClosure
• A set of shared interfaces
  • AbstractConstraint
  • AbstractDomain{T}
  • AbstractDomainListener
  • AbstractVariable{T}
  • AbstractSolver
  • AbstractObjective
• Objectives
  • Minimize
• Solver
  • LearnieCP the core solver
• InnerCore - module that export the core functions & objects

Exceptions

• AbstractSolverException

  • InconsistencyException
  • NotImplementedException
  • EmptyBackUpException

• Exceptions are still experimental. The aim is to put them in distinct categories & sub-categories that will be handled in precise ways by the solver while also providing exact messages, where necessary, to the user.

Reification

• Refined Constraints

Search

• DFSearch
• SearchStatistics
  • Think through adding more features

Constraints

• ConstNotEqual
• ConstEqual
• NotEqual
• Equal
• Global Constraints
  • Sum
  • Element2D
  • Element1D
  • Element1DVar
  • Table Constraint
  • AllDifferentDC constraint
    • Tested
  • Circuit Constraint
    • Tested
  • Scheduling constraint
    • Cumulative Constraint
      • Tested
    • Disjunctive Constraint
      • Tested

Branching Scheme

• SelectMin
• FirstFail
• And

State

• BackUp representation
• StateManagers
  • AbstractStateManager
    • Copier
    • Trailer
• AbstractState
  • Copy
  • Trail
• StateEntry (used as entries into the backup store)
• StateStack (for constraints in the domain listener)
• StateInt

A sample representation of the copier state manager.

A Book on JuliaCP

• The Book Repo is here

Examples

• backtracking
  • NQueens

Other examples using learnie CP

• SEND + MORE = MONEY
  • Oughts to change based on the changes to the sum constraint interface
• Sudoku
• Sum Test (testing the sum constraint)
• NQueens
• Quadratic Assignment Problem
• Stable Matching Problem
• Eternity Puzzle
• TSP

Here's a small implementation of the NQueens problem implementation in LearnieCP.

Some of these examples are accompanied by plots, especially the ones that have an objective value to be minimized. All these plots will be included in the book. A sample plot can be seen here:

Objective value progress for the above problem:

A sample table display of a table present in the TableCT constraint:

A 3x3 Magic Square Problem solution

TSP Distance update progress

This Ciruit constraint was used here on a 15x15 grid. However, these results are from an exact search algorithm.

TAs with Courses assignment (Example from UBC lecture)

TAs with course and block details dataframe:

Courses with respective TAs dataframe:

Capacitated Facility Assignment progress plot

---

RoadMap

• Constraints
  • More localized constraints
• Branching Schema
  • Using ML
• Large Neighbourhood search
• Local Search Heuristics
  • Simulated Annaeling
  • Random Search
  • Tabu Search
• More examples
  • VRP
• A Book on this approach
• Comparison with JuMP solvers.
• Continuous Variables
• Simplex or methods alike
• A smoother interface - probably link with JuMP
• Return the objective value of an optimization problem using objectiveValue function
• Solver state of constraints, variables and the objective
  • Printing of solver state to show the model.

---

Contributions are welcome.