Skip to content

Latest commit

 

History

History
139 lines (126 loc) · 6.06 KB

README.org

File metadata and controls

139 lines (126 loc) · 6.06 KB

CODD

CODD is a C++ library that implements the DDOpt framework. It has:

  • restricted / exact / relax diagrams
  • state definition, initial, terminal and state merging functions separated
  • equivalence predicate for sink.
  • restricted construction is truly bounded now (not truncation based).

Dependencies

You need graphviz (The dot binary) to create graph images. It happens automatically when the display method is called. Temporary files are created in /tmp and then macOS open command is used (via fork/execlp) to open the generated PDF. The same functionality needs to be added on Linux (different API to pop up a viewer).

C++ Standard

You need a C++-20 capable compiler. gcc and clang should both work. I work on macOS, and I use the mainline clang coming with Xcode.

The implementation uses templates and concepts to factor the code.

Build system

This is cmake. Simply do the following

mkdir build
cd build
cmake ..
make -j4

And it will compile the whole thing. To compile in optimized mode, simply change the variable CMAKE_BUILD_TYPE from Debug to Release as shown below:

cmake .. -DCMAKE_BUILD_TYPE=Release

Examples

To be found in the examples folder

  • coloringtoy tiny coloring bench (same as in python)
  • foo maximum independent set (toy size)
  • tsp TSP solver (same as in python)
  • gruler golomb ruler (usage <size> <ubOnLabels>)
  • knapsack Binary knapsack
  • MISP for the Maximum independent set

Each benchmark may have several variants that are incresingly faster (because they use local bounds, dominance, better state representation, etc…). For instance, tsp_test4 is one of the variant for TSP. Most executable do take an input for the filename containing the instance as well as the width. For instance running tsp_test4 can be done as follows:

./tsp_test4 ../data/atsp/br17.atsp 32

from the build folder to run on the br17 instance with a width of 32. The output would look like this:

ities:{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}
sz(LightHashtable):200191
B&B searching...
sz(LightHashtable):200191
sz(LightHashtable):200191
B&B Nodes          Dual	Primal	Gap(%)
----------------------------------------------
TIME:80
P TIGHTEN: <P:42, INC:(17)[12 10 1 2 13 9 16 7 8 14 5 6 3 4 15 11 0 ]>
B&B(    1)	      6	     42	 85.71%	time:  0.08s
TIME:2203
P TIGHTEN: <P:41, INC:(17)[11 2 13 12 9 10 1 8 16 7 14 5 6 3 4 15 0 ]>
B&B(   48)	     11	     41	 73.17%	time: 2.203s
TIME:2242
P TIGHTEN: <P:40, INC:(17)[11 9 12 1 2 13 10 8 16 7 3 4 6 15 5 14 0 ]>
B&B(   49)	     11	     40	  72.5%	time: 2.242s
TIME:3063
P TIGHTEN: <P:39, INC:(17)[11 13 2 1 10 12 9 6 14 5 15 3 4 8 16 7 0 ]>
B&B(   69)	     11	     39	 71.79%	time: 3.063s
B&B(  294)	     13	     39	 66.67%	time: 8.067s
B&B(  758)	     13	     39	 66.67%	time: 13.08s
B&B( 1348)	     17	     39	 56.41%	time: 18.09s
B&B( 3418)	     19	     39	 51.28%	time:  23.1s
B&B( 6569)	     24	     39	 38.46%	time:  28.1s
Done(32):39	#nodes:13912/13912	P/D:0/0	Time:3.063/31.995s	LIM?:0

Every 5 seconds, the branch and bound reports the number of nodes, current node value, incumbent value, duality gap and the time since the start. The last line (with the Done) says that the optimal was 39, that it took 13912 nodes to close the optimality proof, that no nodes where discarded because of a dominance and that the optimum was found after 3.063s and the proof took 31.995s (if there was a limit, it was not reached).

Unit test

In the test folder

Library

All of it in the src folder

Brief documentation

A small site with some documentation in HTML is available too.

Tasks

Decent set of integer implementation

On my own heap. With template overload that is size dependent (up to label 64, all ops should be O(1)) After that, it should be O(label/64). Unless we start using the 128 bit registers ;-)

Check and fix leaks (the cache should be deallocated, not _an)

Implement instance reader for tsp to do bigger instances

Done for coloring.

Implement instance reader for MISP

Rename MISP (foo) to misptoy ;-)

Profile and pick up the low hanging fruits

Fix calls to find in order to remove from _an

  • Those should be O(1) via locators.
  • Implement the trick to O(1) removal (affects mergeLayer / truncate)
  • I now directly link the ANode with each other. It avoids the needs for location. Removal can still be O(1).

Fix calls to find before updateKey in heaps

  • Heap is already location aware
  • We need to track the location (by node id, we have those)
  • Then use the location to have an O(1) operation (affects computeBest & computeBestBackward)

Change the makeNode / duplicate so that hash is computed only once (not twice).

  • Use opaque ADT in Hashtable to support that (HTAt is the opaque type)

Experiment with permanent state cache

segregate Edge allocator

keep the node cache (at least for relaxed) so that they get reused

This did not work. It creates and keeps far too many nodes. Collision lists were getting too long. It’s far easier to clear and rebuild as many DDs are quite small.

clear the edge allocator since those must be rebuild

runs the risk of runaway node cache. Maybe clear periodically? (Every 10K B&B node)

Implement a label generator

Cleanup the edge transfer (no more allocating, just moving)

Change relax to merge as we go

Command to create a GCM for an import

Like

import iostream;

You need

g++-13 -std=c++20 -fmodules-ts -xc++-system-header iostream

Haven’t found a way to automate in cmake yet. Though there should be