This may mean that you are installing the wrong pre-build binary
since my CPU on Ubuntu 18.04 my download url was: https://github.com/lakshayg/tensorflow-build/releases/download/tf1.12.0-ubuntu18.04-py2-py3/tensorflow-1.12.0-cp36-cp36m-linux_x86_64.whl
as it can be found on this github page: https://github.com/lakshayg/tensorflow-build
pip install --ignore-installed --upgrade <LOCAL PATH / BINARY-URL>
resolved the issue for me.