coin-or / coin-or/python-mip

optimize n-queens: Performance of pre-compiled cbc vs source build

Open
#393 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Linear Programming
Stars
600
Forks
108
PR merge metrics
No merged PRs in 30d

Description

**Describe the bug**
I find that build-from-source instructions result in a binary that is nearly twice as slow as the checked-in [cbc-c-linux-x86-64.so](https://github.com/coin-or/python-mip/blob/master/mip/libraries/cbc-c-linux-x86-64.so).

My motivation in compiling form source is so that I can run on aarch64 host (Graviton3: aws c7g instance). The pre-compiled .so for cbc doesn't include aarch64 binaries. Testing showed I was getting poor performance, but when I take the same steps on x86 I find that none of the variations of flags or compilers I tried are able to match the pre-compiled binary, so this isn't so much a "slow on arm" problem as much as it is a "slow when I build from source" problem.

The test my customer pointed me to is the n-queens test. However they have modified it from your queens.py to include an `optimize()` call, which adds significant time. Does this make sense as a benchmark since solutions are either valid or not (but not "optimizable")?

**To Reproduce**
I have tried two approaches:
- Follow the instructions on https://python-mip.readthedocs.io/en/latest/install.html and use coinbrew from `master`. I've tried this with clang, various gcc versions (from v9.4.0 to v14.1.0), and various CXXFLAGS and CFLAGS (`-march=native -mtune=native -O3 -flto`)
- Run the scripts in `scripts/` namely [buildCBCLinux.sh](https://github.com/coin-or/python-mip/blob/master/scripts/buildCBCLinux.sh) and [downloadCBC.sh](https://github.com/coin-or/python-mip/blob/master/scripts/downloadCBC.sh). This took some modification to the last g++ line to include `-lnauty -lcholmod -lreadline -lbz2` and adjust some include and lib paths, but the runtime was the same as the coinbrew approach (and it crashed at the end...but that could have been a mismatch in .so and python-mip version -- I didn't investigate)

I find that after including `optimize` in queens.py: for n=200, it takes about 60 seconds when I build from source on c6i (Intel(R) Xeon(R) Platinum 8375C CPU @ 2.90GHz) and about 20 seconds when I use the provided .so.

I found also https://github.com/coin-or/python-mip/issues/215#issuecomment-955792305 however I don't know which versions or flags I can use to reproduce the binary. It seems it was last updated 3 years ago, is it possible Cbc itself had a regression in that time or that I need to use particular versions? I see references in [Benchmarks](https://python-mip.readthedocs.io/en/latest/bench.html) about " we implemented an automatic buffering/flushing mechanism in the CBC C Interface". Is this included in Cbc master now?

**Expected behavior**
- Compile-from-source binary should be as fast as [cbc-c-linux-x86-64.so](https://github.com/coin-or/python-mip/blob/master/mip/libraries/cbc-c-linux-x86-64.so).
- Instructions to reproduce [cbc-c-linux-x86-64.so](https://github.com/coin-or/python-mip/blob/master/mip/libraries/cbc-c-linux-x86-64.so).

**Desktop (please complete the following information):**
- Operating System, version: Ubuntu 20.04 and AL2023
- Python version: 3.8.10
- Python-MIP version (we recommend you to test with the latest version): 1.15.0 from pip.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.