Skip to content

Latest commit

 

History

History
204 lines (155 loc) · 5.83 KB

README.md

File metadata and controls

204 lines (155 loc) · 5.83 KB
Raw

LearnieCP

LearnieCP350x350 Logo

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.

JuliaCP Components Graph

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:

Domain Components Representation

  • 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.

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.

NQueens 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:

QAP Objective Value Progress

Objective value progress for the above problem:

QAP Objective Value Interactive Progess

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

Sample Table From Table CT Constraint

A 3x3 Magic Square Problem solution

Sample 3x3 MagicSquare Solution

TSP Distance update progress

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

Sample TSP 15x15 distance progress update

TAs with Courses assignment (Example from UBC lecture)

Entire Assignment DataFrame

TAs with course and block details dataframe:

TA with Course And Block DataFrame

Courses with respective TAs dataframe:

Course with TAs DataFrame

Capacitated Facility Assignment progress plot

Capacitated Facility Assignment 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.