about
About
about
Research
about
Publications
teaching
Teaching
about
Software

Software

I'm an open source enthusiast. Below there is a list of software which I developed or contributed to the development. You can use it to any purpose as long as you cite the source. *Use at your own risk*.

NPSep

NPSep is a set of routines to create dense conflict graphs and to generate cuts derived from these graphs. It currently separetes the following valid inequalities:

  • cliques;
  • odd-holes;
  • wheels.

Some features of NPSep are:

  • separates virtually all violated clique inequalities: a smart implementation of the Bron-Kerbosch (BK) algorithm with specially tuned pivoting rules allows the generation of all violated clique inequalities even for large instances (e.g. the larger ones in MIPLIB 2010 benchmark set), for even larger instance a greedy randomized heuristic is automatically selected;
  • lifting: larger cliques are generated by the inclusion of additional variables which do not appear as active (>0) in the current fractional solution, so that less cuts are necessary to improve the lower bound;
  • solver independent: most of the code, including all cut separation code, is completely solver independent, with the exception of the code which builds the conflict graph;
  • portable: the code was entirely wrote in ANSI C, with some small parts in ANSI C++.
The following papers describe successful applications of NPSep:

NPSep is developed primarily by me and Samuel. Contributors include Artur, Eduardo and Poggi.

The project has a git based version control system hosted here.

School Timetabling Solver In 2011 the Third International Timetabling Competition (ITC 2011) happened. Our solver (GOAL Solver) was the winner of the competition. You can download the source code of this solver here. A descriptions of our solver can be found in the following paper:
Fonseca2014 Fonseca, George H.G.; Santos, Haroldo G.; Toffolo, Túlio A.M.; Brito, Samuel S. and Souza, Marcone J.F.. GOAL solver: a hybrid local search based solver for high school timetabling. Annals of Operations Research, DOI 10.1007/s10479-014-1685-4. 2014.  bibtex