8
$\begingroup$

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?

$\endgroup$
9
  • 2
    $\begingroup$ Hi Naveen, welcome! Would you please let us know a little more about the kind of optimization problems you are solving? A specific application, or general linear/integer/non-linear/... programs? Thanks! $\endgroup$ – Marco Lübbecke Nov 25 '19 at 15:01
  • 1
    $\begingroup$ Hi Naveen, welcome to OR.SE, as @Marco also mentioned, your designing strategy is highly dependent on the type of problem that you use the solver for and also how frequently your data (parameters of the model) are changing? this is another important factor for your design that affects the necessity of separating model and data. $\endgroup$ – Oguz Toragay Nov 25 '19 at 17:00
  • $\begingroup$ This question is cross-posted on the CPLEX forum of IBM developerWorks. $\endgroup$ – prubin Nov 25 '19 at 18:45
  • 3
    $\begingroup$ OOP is not necessarily the best paradigm for algorithm-intense code. You should at least be familiar with functional programming well enough to make educated design choices. And even if you stick with procedural programming, nothing in this paradigm prevents you from writing clean code split into multiple files. $\endgroup$ – IMil Nov 26 '19 at 2:15
  • $\begingroup$ @IMil I'll add to this that I find object oriented algorithm-intense code extremely hard to maintain compared to procedural or functional paradigms. Often the result of someone writing an object-oriented solver is a set of classes with a bunch of methods that are unrelated to one another and don't modify the properties of the class at all, if there are any. These classes tend to make very limited use of inheritance and are usually only instantiated once. $\endgroup$ – zaen Nov 26 '19 at 17:21
10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thank you for your answer. I will try your suggestion out. $\endgroup$ – naveen divakaran Nov 27 '19 at 1:48
6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I am interested in learning the design aspects you're talking about (I mean how to take memory complexity into account, what is the cache efficiency, etc.). Do yo have any resource to learn more about them ? $\endgroup$ – Antarctica Nov 27 '19 at 21:05
  • $\begingroup$ Unfortunately not, it's all stuff we learnt in practice. For us, computational graphs (to represent nonlinear functions) and linear functions turned out to be two of the most fundamental data structures. What is important really depends on what the solver is designed to solve, so it's hard to give transferable suggestions. For cache efficiency however, this is something that can be measured in VTUNE quite easily :) In general it's a good idea to have as few members as possible for the fundamental data structures and to make sure they can fit into the average cache line. $\endgroup$ – Nikos Kazazakis Nov 30 '19 at 0:52
  • $\begingroup$ Unfortunately not, it's all stuff we learnt in practice. For us, computational graphs (to represent nonlinear functions) and linear functions turned out to be two of the most fundamental data structures. What is important really depends on what the solver is designed to solve, so it's hard to give transferable suggestions. For cache efficiency however, this is something that can be measured in VTUNE quite easily :) In general it's a good idea to have as few members as possible for the fundamental data structures and to make sure they can fit into the average cache line. $\endgroup$ – Nikos Kazazakis Nov 30 '19 at 0:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.