PuLP not working with Travis CI?

I use PuLP in my project and all tests pass on my local machine. But when Travis CI runs the test suite all the tests involving PuLP fail. Here's the summary (all the tests containing exact use PuLP):

============================= test session starts ==============================
platform linux -- Python 3.4.6, pytest-3.0.7, py-1.4.33, pluggy-0.4.0
rootdir: /home/travis/build/yogabonito/region, inifile: pytest.ini
collected 134 items 
region/csgraph_utils.py ...
region/objective_function.py ..
region/util.py .............
region/max_p_regions/tests/test_exact.py FFFFFFFFFFFF
region/max_p_regions/tests/test_heu.py ............
region/p_regions/tests/test_azp.py ............
region/p_regions/tests/test_azp_basic_tabu.py ............
region/p_regions/tests/test_azp_reactive_tabu.py ............
region/p_regions/tests/test_azp_simulated_annealing.py ............
region/p_regions/tests/test_exact.py FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
region/tests/test_util.py .......
region/tests/util.py .

Here's an example failure:

=================================== FAILURES ===================================
___________________________ test_scipy_sparse_matrix ___________________________
    def test_scipy_sparse_matrix():
        cluster_object = MaxPRegionsExact()
        cluster_object.fit_from_scipy_sparse_matrix(adj, attr,
                                                    spatially_extensive_attr,
>                                                   threshold=threshold)
region/max_p_regions/tests/test_exact.py:23: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
region/max_p_regions/exact.py:153: in fit_from_scipy_sparse_matrix
    prob.solve(solver)
../../../virtualenv/python3.4.6/lib/python3.4/site-packages/pulp/pulp.py:1664: in solve
    status = solver.actualSolve(self, **kwargs)
../../../virtualenv/python3.4.6/lib/python3.4/site-packages/pulp/solvers.py:1362: in actualSolve
    return self.solve_CBC(lp, **kwargs)
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
self = <pulp.solvers.COIN_CMD object at 0x7ff3e76ba9b0>
lp = Max-p-Regions:
MINIMIZE
50.29999999999968*t_(0,_1) + 80.59999999999991*t_(0,_2) + 140.19999999999993*t_(0,_3) + 60.699... <= x_(8,_8,_5) <= 1 Integer
0 <= x_(8,_8,_6) <= 1 Integer
0 <= x_(8,_8,_7) <= 1 Integer
0 <= x_(8,_8,_8) <= 1 Integer
use_mps = True
    def solve_CBC(self, lp, use_mps=True):
        """Solve a MIP problem using CBC"""
        if not self.executable(self.path):
            raise PulpSolverError("Pulp: cannot execute %s cwd: %s"%(self.path,
>                                  os.getcwd()))
E           pulp.solvers.PulpSolverError: Pulp: cannot execute cbc cwd: /home/travis/build/yogabonito/region
../../../virtualenv/python3.4.6/lib/python3.4/site-packages/pulp/solvers.py:1372: PulpSolverError
----------------------------- Captured stdout call -----------------------------
start solving with <pulp.solvers.COIN_CMD object at 0x7ff3e76ba9b0>

It looks like Travis cannot find the CBC CMD solver although according to the PuLP-docs it is "included" / "bundled with pulp". (On my local machine I did not have to install the CBC CMD solver. It was installed automatically with PuLP.)

My question is: How can I make Travis CI find the solver? Also interesting: Why did my problems using Travis CI occur?