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
competition input format. 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...
....
}
}