Golomb Ruler Solver

This is an example application for producing Golomb Rulers using constraint programming (CP) via IBM CPLEX. Producing rulers is a fun way to learn CP (even if it isn't the most efficient method of producing them). IBM uses it as a training exercise in their documentation as well. It includes a web frontend that displays real time metrics of the solve process (see below).

NOTE: This repository is not actively maintained.

From the Wikipedia page

In mathematics, a Golomb ruler is a set of marks at integer positions along an imaginary ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is its length. Translation and reflection of a Golomb ruler are considered trivial, so the smallest mark is customarily put at 0 and the next mark at the smaller of its two possible values.

Here's an example of a Golomb Ruler of order 4 and length 6.

Requirements

• CPLEX 12.9. The Community Edition will work.
• Scala, Sbt
• Node, NPM

The backend is written in Scala. The frontend is a single page application which uses React 16, and listens over a web socket for solver events.

Demo

Below is an example of running the app with an order of 7. It displays the current best found ruler, along with real time metrics like the current objective value, NumberOfChoicePoints, NumberOfBranches, MemoryUsage etc.

Directory structure

root
│   README.md       <- You are here!
│
└───server          <- Web server & solver
│   │   README.md
|   |   .
|   |   .
│   
└───client          <- Web client
    │   README.md
    |   |   .
    |   |   .

The core of the solver logic is in GolombRuler.scala. That is where we model the problem and kick off the CPLEX solve process. The Server.scala sets up a web server to take solve requests, and sets up a web socket to send search process updates out to the client. The client directory contains the React front-end which subscribes to this web socket, and provides a UI to send solution requests to the server.

Development

First, ensure that you have CPLEX 12.9 installed.

Setup the backend

$ cd server
$ sbt clean compile stage
$ sbt run

Setup the client

$ cd client
$ # see client/README.md
$ yarn install
$ yarn start

Navigate to the url provided by yarn start.

Misc

To include images in the READMEs we do this little hack of uploading the images to this github issue and then copying the url of the resource hosted by github.