The last several years have seen an increasing interest in combining the
models and methods of constraint programming with those of optimisation.
The main objective for integrating Constraint Logic Programming (CLP) and
Mixed Integer Programming (MIP) is to take advantage of both the inference
through Constraint Propagation (CP) and the (continuous) relaxations through
Linear Programming (LP).  Integration of the two was initially impeded by
their different cultural origins.  The advantages of a merger, however, are
rapidly overcoming this barrier.

The key decisions to be made for integrating CLP and MIP are (a) the
model(s), (b) the inference, (c) the relaxations, and, (d) the search and
branching strategies to use.  In this thesis it is advocated to model
specifically for a hybrid solver, having part of the model operated on by CP
inference and part of the model constituting an LP relaxation, building on
the framework of Mixed Logical/Linear Programming (MLLP).

We propose mixed global constraints, spanning both the discrete and
continuous variables, to bridge the gap between CLP and MIP, providing
inference as well as information for search strategies.  Inference is in the
form of domain reductions and cutting planes for CLP and MIP, respectively.

The main focus will be on modelling and how a rethinking of our modelling
traditions is necessary to achieve the greatest benefit of such an
integration, but we also develop several important algorithmic techniques to
improve the communication between the CLP and MIP parts of a model, and to
better integrate classical OR techniques into the hybrid framework.

In addition to a general framework for integration, specific constraints and
structures are studied, including variable subscripts and piecewise linear
functions.

We also examine a hybrid CLP--MIP Benders Decomposition scheme whose main
differences from classical Benders are that the subproblem is handled by
constraint satisfaction techniques and the Benders cuts are generated in the
process of solving the master problem once.

Computational experiments show the benefit and potential of hybrid schemes.