Implementing solvers with Object Oriented Programming

Question

I would like to know what are some best practices in designing a solver implementation with Object Oriented Programming. We have implemented a solver with procedural programming paradigm, using python, and therefore we have data structures and functions written all in one python file. The solver works and is adding value to the organization. But now that we have to maintain and scale the code, (as always developing is just 20% of work load, maintenance is where 80% is) we are stumbling upon the need to design the solution with clear separation of model, data, algorithm, and reporting.

Can anyone help shed some light on how to do this the best way?

Answer 1

I'm not sure there is any "best way", but I can speak to personal practice (using Java, which is inherently object oriented). I will typically have one class that represents the "problem" (including data). If the data for the problem instance is drawn from an XML file, a text file, a database connection or whatever, I'll use a separate class for the data import. Next, I'll have a model class, whose constructor receives the problem class as an argument. The model class has the various CPLEX constructs (CPLEX model, variables, constraints, objective, ...) as fields, along with any structures that facilitate accessing them. (For instance, I might have two maps, one mapping model objects to CPLEX variables and the other doing the reverse mapping.) If the model involves callbacks, I'll usually make them subclasses of the model class.

If the algorithm just consists of calling the solve() method for the CPLEX object in the model class, I'll make solving a method in the model class. If it is more complicated (initial heuristics, looping through modifications of the model, ...), I'll create a separate solver class that accesses the model class and does all that stuff.

If the problem is sufficiently complicated, or if I want to be able to seed the algorithm with starting solutions from other runs, I'll create a separate solution class, which holds the solution (typically in terms understandable by the problem class, so storing "number of vehicles = ..." rather than "IloNumVar nveh = ..."). If solutions need to be read from and/or written to files of a particular type (XML, JSON, CSV) or a database, I'll use a separate class for that I/O.

If the user gets to set algorithm parameters (including CPLEX parameters), I typically put those in a class of their own, along with a mechanism to import and export them. That helps with reproducibility and cuts user time if the user wants to reuse parameter settings repeatedly.

If there is a GUI, that will, of course, be a class of its own.

Finally, I adhere to a couple of general practices. If anything (problem data, solutions, parameters) is read from or written to external sources, I try to make the relevant field names (column headings in a CSV file, database field names, ...) text data, either static string values in the relevant class or text resources read from a text file that is part of the source code. That way, if someone mucks with one of the names, I can tweak one line of source code or one line in a text resource file, and not run around looking for every place in the code where that name is used (inevitably missing one).

Also, when specifying the APIs for each class, I try to be as minimalist/vague/general as possible. So the problem class provides accessors to give the model class what it needs to know, but only what it really needs, and at more or less the most general level possible. As one example of that last point, if the model class needs to know the arcs in a network model, the problem class (which is where the network details are stored) will ideally return a Collection of arcs, not a HashSet or ArrayList. (In Java, both HashSet and ArrayList are subclasses of Collection.) That way, if something changes and I find myself needing to alter how the arcs are stored in the problem class, I don't have to worry about breaking any code in the model class.

Answer 2

The abstractions necessary to describe the components are fairly straightforward in optimisation, i.e., problem, function, variable, constraint, linear function, nonlinear function, Jacobian, Hessian of Lagrangian, and so on. A great open source example of how this can be modelled is the MINOTAUR solver.

I can tell you from experience (this is my job) that in an OOP design you will struggle with two things, especially if your solver is parallel: (i) keeping track of the states/exit conditions of the solver, and (ii) global variables. The latter is unfortunately an integral part of achieving high performance (by caching and taking shortcuts), and requires masterful design to get rid of. As a rule of thumb, it took one of our developers about 5 months of full time work to get rid of all global variables in our solver (C++) by redesigning a bunch of components.

My recommendation on this would be to identify the performance critical data structures in your solver in advance, by taking into account memory complexity, cache efficiency, and insertion/lookup operations, so that your OOP design incorporates how to handle them well from the very first design. Otherwise, you will enter a long vicious cycle of micro-optimisations that interfere with good design practices and code readability.