This package provides a free and extensible implementation of Joint Generation Algorithms.

We chose Common Lisp as the implementation language to facilitate easy experimentation with the ad-hoc decisions in the implementation, and to make implementation of your favourite monotone boolean function oracle easy.

The canonical project home page is here, the SVN repository, file releases and bug tracking are hosted on SourceForge.

About This Package

Quick start


To make use of this package you will need
  • A Common Lisp Environment. SBCL is a good free candidate. See the ALU Wiki for a list of choices.
  • (Optionally) Emacs with SLIME installed.
  • The ASDF System definition package. If you chose SBCL above then you already have it.
  • This package, either as .zip file release, or from the SVN repository.

If you are using Debian GNU/Linux you can fetch the prerequistites by
apt-get install emacs slime sbcl
A one-step solution may be Lispbox.

If any of the above does not make sense to you, you may want to start learning more about Common Lisp by reading Peter Seibel's Practical Common Lisp, a great Lisp book suitable as online <a href="">Common Lisp tutorial</a> but also available in printed form with ISBN 978-1590592397.

Quick start

If you want to get a quick start, load the package into your lisp and evaluate
CL-USER> (asdf:operate 'asdf:load-op 'cl-jointgen)
CL-JOINTGEN> (with-open-file (s "instances/acet.lisp"
                              :direction :input)
                 (make-jg-problem/hg-oracle (read s))))
[lots of output scrolling by]   


Applications are discussed in

Haus, Klamt, Stephen: Computing Knock-Out Strategies in Metabolic Networks.

If you are serious about the mathematical background read one or more of the following papers:
  • Fredman, Khachiyan: On the Complexity of Dualization of Monotone Disjunctive Normal Forms DOI link
  • Khachiyan, Boros, Elbassioni, Gurvich: An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation DOI link


This code is released under the GNU Public License with Lisp clarfications and copyrighted by Utz-Uwe Haus and Tamon Stephen. Please see the files LICENSE.GPL and LICENSE.Lisp-GPL-Preface in the distribution for details.

Exported Symbol Index

check-duality, function
clause, class
clause, type
clause->bitlist/lsb, function
clause->bitlist/msb, function
clause->bitvec/lsb, function
clause->bitvec/msb, function
clause-clear-bit, function
clause-ref, function
clause-set-bit, function
clutter, class
clutter, type
get-num-oracle-calls, function
hypergraph-edge-oracle, class
hypergraph-edge-oracle, type
joint-generation, function
make-jg-problem, function
make-monotone-ieq-oracle, function
make-permutation-oracle, function
make-sperner-hypergraph-oracle, function
make-t-frequent-set-oracle, function
maximize-clause, function
mbf-oracle, class
mbf-oracle, type
minimize-clause, function
monotone-ieq-oracle, class
monotone-ieq-oracle, type
permutation-oracle, class
permutation-oracle, type
query-oracle, function
t-frequent-set-oracle, class
t-frequent-set-oracle, type