7
$\begingroup$

In many articles that use metaheuristics to solve optimization problems, the programming language of choice is C++. For example, the following two articles present state-of-the-art metaheuristics to solve the Capacitated Vehicle Routing Problem and are implemented in C++: Accorsi and Vigo (2021) and Vidal (2022).

I have yet to find a paper that uses Python to implement a metaheuristic for routing or scheduling problems. As I recently started my PhD in this field and I only have experience with programming in Python, I'm wondering whether it's even acceptable to use Python for my research.

Assuming that the algorithmic aspects of my code are efficient (e.g., implementing local search methods in the best-known time complexity, using efficient data structures), would it hurt my chances to publish in top quality journals if I use Python in my research instead of C++ or another compiled language?

Although I have not read a lot of literature on exact methods, I believe this issue is less prevalent because most people make use of commercial solvers such as CPLEX and Gurobi. But if my question also applies in this case, please feel free to share your thoughts on this as well.

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ What is the scientific contribution of your work? Do you want to beat a benchmark of an existing problem or do you come up with a new problem? $\endgroup$
    – PeterD
    Commented Jun 14, 2022 at 15:40
  • $\begingroup$ @PeterD The main scientific contribution of my work is solving real-world optimization problems. For example, solving a rich vehicle routing problem with 5+ attributes or scheduling problems such as hybrid flexible flow shop with again lots of constraints. $\endgroup$
    – Leon Lan
    Commented Jun 14, 2022 at 17:37
  • 2
    $\begingroup$ You could also learn Cython if performance is your main concern. $\endgroup$
    – joni
    Commented Jun 15, 2022 at 7:14
  • 5
    $\begingroup$ You should seriously consider Julia. If you know Python, Julia you'll find close enough (for starters). And if you need C-grade efficiency, default Julia comes close. And, in the hands of experts, often betters C. $\endgroup$
    – Rusi
    Commented Jun 15, 2022 at 11:05
  • 1
    $\begingroup$ An eg why Julia in OR makes sense juliacomputing.com/case-studies/alpha-route $\endgroup$
    – Rusi
    Commented Jun 15, 2022 at 13:19

4 Answers 4

Reset to default
16
$\begingroup$

Speaking as an occasional reviewer for journals, when I read a paper proposing a new heuristic or metaheuristic my first question is "does it work?", which is independent of the programming language used. My second question is "does it work better than existing methods?", which can be interpreted in one of two ways: it gets better results than currently accepted methods in the same amount of time; or it gets comparable results faster. Depending on the underlying type of problem being solved, "accepted methods" might include running a commercial optimization solver in a heuristic way (set a time limit, tweak a few settings and see how good the incumbent solution is).

So this ties into the question @PeterD put in his comment. If this is a new, previously unsolved, problem and it does not fit into a category (LP, MILP, ...) for which solvers exist, just producing "reasonable" results in "reasonable" time is grounds for publication. If there are no commonly used heuristics for the problem, getting a solution that is fairly good in a reasonable time may be enough for publication, even if commercial solvers do better, because not everyone can afford commercial solvers. If, say, the problem is frequently solved (by practitioners and/or in the research literature) using the horny snail metaheuristic, than I would expect you as author to demonstrate that your metaheuristic is faster than horny snail, either by running both of them on the same examples using the same hardware or by citing published times for horny snail on publicly available test problems and then beating those times with your heuristic (on hardware comparable to what was used for the published times).

Now, can you accomplish any of that in Python. Quite possibly. The published times for other heuristics might have been generated using Python code, or code in languages "slower" than C/C++. There is also the question of coding skill: your "tight" Python code might run faster than someone else's sloppy C++ code. Also, libraries play a role. The bulk of the computing time spent by your heuristic might occur in a Python library, written in C/C++ by someone who worked to optimize their code.

If nothing else, you could start by coding in Python and see if your heuristic works (valid results, reasonably close to optimal in reasonable time and memory). If you think it has merit but is not yet publishable, maybe you could bring on a coauthor with C/C++ programming chops (or hire someone to recode it).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ A well written C++17 program has very different and often more readable architecture that is not easily reproducible in Python. As a result, "Python first" may not be the best approach for a complex algorithm. $\endgroup$
    – h22
    Commented Jun 16, 2022 at 17:50
7
$\begingroup$

I think this is a false dichotomy.

Surely, C++ is the classical language for fast programs (besides FORTRAN, maybe).

But nowadays, Java is very fast as well. Julia is also an option, fast and aimed for scientific programming.

So you do not necessarily go down into the depth of memory management in C++, there are alternatives.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ I agree with you and to be fair, discussions on languages are always a bit biased. But I still couldn't resist mentioning that memory management in C++ isn't this much of an issue in modern C++ thanks to RAII, smart pointers and the STL containers. $\endgroup$
    – joni
    Commented Jun 15, 2022 at 11:02
  • $\begingroup$ @joni This is a fair point. C++ has become much simpler in this respect. $\endgroup$
    – J Fabian Meier
    Commented Jun 15, 2022 at 11:10
3
$\begingroup$

Python has something named the GIL (Global Interpreter Lock) which prevents any kind of shared memory parallelism and even sometimes message based parallelism. In theory, it is possible to serialize objects if they are small but most Python bindings don’t and won’t implement what is required for bringing parallelism capacity.
As a result, many Python programs with huge amount of work to bring serialization support across all dependencies/subdependencies are finding themselves having to rely on single-thread CPU performance with running during weeks on a specific problem still in 2022!

And unlike languages like Java, Python uses reference counting instead of garbage collection in a separate thread which adds work in an already single-thread-bound language.

On the other hand, languages like C++ or Fortran don’t suffer from the warm up time of JIT languages like Java or JavaScript nor the slow execution speed of language like Python or/along the Cythonized version.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Perhaps worth noting that removing the GIL is an active discussion once again. There are proof-of-concept forks of Python which implement this already. $\endgroup$
    – tripleee
    Commented Jun 16, 2022 at 6:27
  • 1
    $\begingroup$ @tripleee many proofs of concepts during all over the last decade but nothing which can be used with existing software besides Jython which is still Python 2. Even the new Microsoft implementation starting this year took the design choice to say it’s up to each Python module to implement proper serialization for allowing parallelism which of course won’t happen. A proper way to do this would be to simply require C extensions along generated Cython code to no longer assume thread‐safety which obviously would be more difficult than Python 2 to Python 3. $\endgroup$
    – user2284570
    Commented Jun 16, 2022 at 17:56
  • 1
    $\begingroup$ More seriously, if you need at least message‐based parallelism without having to reinvent the wheel by writing your own flavour of most Python packages, just use C/C++/Fortran but don’t expect anything before 2040 with Python… $\endgroup$
    – user2284570
    Commented Jun 16, 2022 at 17:59
1
$\begingroup$

The most convincible way to compare the performance of the different algorithms is by implementing them in the same language and profiling on the same hardware. If one runs Python on mainframe and another C++ on your toaster, the results are largely unpredictable.

Obviously you can also use other ways to convince like proving the O(n) complexity of the algorithm.

Improve this answer
$\endgroup$
2
  • $\begingroup$ How is this perceived by reviewers when I implement an algorithm in Python that was originally published/implemented using C/C++? For example, let's say the current state-of-the-art is algorithm A and I propose a new algorithm B. Even if I would re-implement A in Python and compare it against my metaheuristic B - both sharing many data structures and local search operators - then my Python implemention of A is still at a disadvantage vs. the C/C++ implemented A. @prubin what are your thoughts on this given your previous answer? $\endgroup$
    – Leon Lan
    Commented Jun 16, 2022 at 20:24
  • 2
    $\begingroup$ A good reviewer won't accept this. It's too easy to do a bad implementation. If you re-implement the algorithm you're comparing with, you need to get equivalent performances as the original version $\endgroup$
    – fontanf
    Commented Jun 17, 2022 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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