Parsers and Coding Tips


This page presents some sample code to be used as an example to help you write your own solver. Note however that this code sometimes uses a number of assumptions which may be invalid in your own implementation. It is your responsability to adapt the code to your own implementation !

Sample parsers

Here are a few simple parsers for the input format used in this evaluation. Note that these parsers have minimal features, are not optimized and should not be used as such in an industrial strength solver. Furthermore, they have not been intensively tested yet. You may therefore expect some updated version one day or another.

Simple Parser (C language) (version 2.9.4: has support for reading non linear constraints and linearization inside the parser)
Simple Parser (C++ language) (version 2.9.4: has support for reading non linear constraints and linearization inside the parser)
Simple Parser (Java language) (version 2.9.0: has preliminary support for reading non linear constraints but doesn't perform linearization inside the parser)
A sample Makefile
A tiny linear test file
A tiny non linear test file
A tiny factorization problem (non linear)

Reading the TMPDIR environment variable

/**
 * Return the path to the only directory where solvers are allowed to read or write files
 *
 * will return "/tmp" if this information is not available (e.g. outside the evaluation environment)
 */
char *getTmpDir() 
{
  char *s=getenv("TMPDIR");

  if (s==NULL)
    s="/tmp";

  return s;
}

Reading the TIMELIMIT or MEMLIMIT environment variables

/**
 * Return the limit corresponding to name
 *   or 0 if no limit is imposed (e.g. outside the evaluation environment)
 *
 * To be used with name="TIMELIMIT" or name="MEMLIMIT"
 */
int getLimit(char *name) 
{
  char *value = getenv(name);

  if (value == NULL) 
    return 0;

  return atoi(value);
}

Storing the best model found so far

Whenever an optimizing solver finds a model with a better value of the objective function, it must store that model in case no better model would be found later. However, storing the model is a critical section of the program because the solver might receive a SIGTERM while it is recording the new solution. The C++ class below is an example of what can be done. The critical section is limited to one single affectation of pointers, which is a reasonable solution on most architectures (note however that this may fail on architectures where a pointer assignment is not atomic).

When a solver finds a better solution, it calls beginSolution() once and then calls in a loop appendToSolution() to record each literal of the model. Then, endSolution() is called to actually validate that model. getSolution() returns the last validated model.

/**
 * a class to record a solution
 *
 * while a new solution is recorded, the previous solution is preserved
 * to be able to return it when we receive a signal
 *
 * It is assumed that a negated atom is represented by a negative integer
 * and that an atom is represented by a positive integer. 0 should not be used.
 */
class SolutionList
{
private:
  typedef vector<int> Solution; // a self expandable array of integers

  Solution *tmp,*preserved;

public:
  SolutionList()
  {
    tmp=NULL;
    preserved=NULL;
  }

  /**
   * to be called when a new solution will be entered
   */
  void beginSolution()
  {
    tmp=new Solution;
  }

  /**
   * append a literal to the new solution being entered
   */
  void appendToSolution(int lit)
  {
    assert(lit!=0);
    tmp->push_back(lit); // append a literal to the array
  }

  /**
   * to be called once a solution is completely entered
   */
  void endSolution()
  {
    Solution *del=preserved;
    // begin critical section
    preserved=tmp;
    // end critical section
    tmp=NULL;
    if (del)
      delete del;
  }

  /**
   * return true is a solution was recorded
   */
  bool hasSolution()
  {
    return preserved!=NULL;
  }

  /**
   * return the latest stable solution
   *
   * even in case of an interrupt, the returned solution is coherent as long
   * as endSolution() is not called in between
   */
  const vector<int> &getSolution() const
  {
    if (!preserved)
      throw runtime_error("no solution recorded");

    return *preserved;
  }
};

Outputing the solver answer

The functions below (C++ code) may be used as a guide to output the solver answer.

/**
 * To be used when the solver has found a model.
 *
 * The model is recorded in parameter sol. optimum must be set to true
 * if and only if this model gives the optimum value of the objective function
 */
void outputSatisfiable(const SolutionList &sol, bool optimum)
{
  if (optimum)
    cout << "s OPTIMUM FOUND" << endl;
  else
    cout << "s SATISFIABLE" << endl;

  const vector<int> &s=sol.getSolution();

  cout << "v " << flush;

  for(int i=0;i<s.size();++i)
  {
    if (s[i]<0)
      cout << "-x" << -s[i] << ' ';
    else
      cout << 'x' << s[i] << ' ';
  }

  cout << endl; // write '\n' and flush the output stream

  exit(0);
}

/**
 * To be used when the instance is unsatisfiable
 */
void outputUnsatisfiable()
{
  cout << "s UNSATISFIABLE" << endl;
  exit(0);
}

/**
 * To be used when it is unknown if the instance is satisfiable or not
 */
void outputUnknown()
{
  cout << "s UNKNOWN" << endl;
  exit(0);
}

When you output the model, don't forget to write a line feed character ('\n') and to flush your output stream !
Note than the C++ endl automatically outputs a '\n' and flushes the stream.

Intercepting the SIGTERM signal

Intercepting the SIGTERM signal is just a matter of calling signal(). When the solver is interrupted, it should answer "s SATISFIABLE" if it found a solution or "s UNKNOWN" otherwise.

#include <signal.h>

SolutionList solution; // global variable that records the best model found so far

/**
 * give the best answer we can when we receive a signal
 */
void interrupt(int sig)
{
  if (solution.hasSolution())
    outputSatisfiable(solution,false);
  else
    outputUnknown();
}

int main()
{ 
  signal(SIGTERM,interrupt);

  ...
}

From a strict point of view, using I/O operations in a signal handler is generally discouraged because there's no guarantee that I/O functions are reentrant. However, in this particular case, the signal handler is called only once to end the program and there's probably little risk to get into trouble.

Yet, you may prefer a cleaner way to handle the signal. The signal handler (interrupt()) should simply set a boolean variable abortASAP which is tested in your solver inner loop to stop the program when it becomes true. The downside is that it adds a test to your inner loop. Besides, you must be sure that little time ellapses between two iterations of that loop since you have only one second after the SIGTERM to output your solution before the solver actually gets killed.

bool abortASAP=false; // global variable

void interrupt(int sig)
{
   abortASAP=true;
}

int main()
{ 
  signal(SIGTERM,interrupt);

  ...

  while(...) // inner loop of your program
  {
     if (abortASAP)
     {
        if (solution.hasSolution())
          outputSatisfiable(solution,false); // these functions never return
        else
          outputUnknown();
     }

     // your solver core...
     ....
  }
}