libdynet.so: No such file or directory

Today I tried to run a simple dynet program (that I ran several months ago with no problems), and got the following error:

Traceback (most recent call last):
File "test_dynet.py", line 1, in
import dynet
File "/usr/local/lib/python3.5/dist-packages/dyNET-0.0.0-py3.5-linux-x86_64.egg/dynet.py", line 17, in
from _dynet import *
ImportError: libdynet.so: cannot open shared object file: No such file or directory

I get the same error even with a minimal program that only contains the single line:

import dynet

I tried to re-install dynet in several ways:

$ sudo pip3 install dynet
Requirement already satisfied: dynet in /usr/local/lib/python3.5/dist-packages/dyNET-0.0.0-py3.5-linux-x86_64.egg (0.0.0)
Requirement already satisfied: cython in /usr/local/lib/python3.5/dist-packages (from dynet) (0.25.2)
Requirement already satisfied: numpy in /usr/local/lib/python3.5/dist-packages (from dynet) (1.12.1)

and also:

$ sudo -H pip3 install git+https://github.com/clab/dynet#egg=dynet
Requirement already satisfied: dynet from git+https://github.com/clab/dynet#egg=dynet in /usr/local/lib/python3.5/dist-packages/dyNET-0.0.0-py3.5-linux-x86_64.egg (0.0.0)
Requirement already satisfied: cython in /usr/local/lib/python3.5/dist-packages (from dynet) (0.25.2)
Requirement already satisfied: numpy in /usr/local/lib/python3.5/dist-packages (from dynet) (1.12.1)

But the program still does not work.

I have Ubuntu 16.04. Here is my python version:

```
$ python3
Python 3.5.2 (default, Nov 12 2018, 13:43:14)
[GCC 5.4.0 20160609] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> print(sys.path)
['', '/usr/lib/python35.zip', '/usr/lib/python3.5', '/usr/lib/python3.5/plat-x86_64-linux-gnu', '/usr/lib/python3.5/lib-dynload', '/home/erelsgl/.local/lib/python3.5/site-packages', '/usr/local/lib/python3.5/dist-packages', '/home/erelsgl/git/PrefLib-Tools/preflibtools', '/usr/local/lib/python3.5/dist-packages/xgboost-0.6-py3.5.egg', '/usr/local/lib/python3.5/dist-packages/dyNET-0.0.0-py3.5-linux-x86_64.egg', '/usr/lib/python3/dist-packages']
```

Start by reproducing the minimal `import dynet` case from `test_dynet.py` and inspect the import chain in `dynet.py`, including `_dynet` and the missing `libdynet.so`. Check how the installed package and shared library are built and located on Ubuntu 16.04. Done means the reported Python import succeeds after a documented installation or packaging fix.

Written by the indexing model from the issue text.