We investigate some generalized graph coloring problems which arise
in the context of operating large radio link telecommunication
networks, or cellular radio communication networks. When only feasible
solutions are looked for, such problems may be formulated in the
framework of constraint satisfaction, a generalization of the so-called
SAT problem. When, due to the number and/or tightness of the
constraints, no feasible solution is likely to exist, a 'least
infeasible' solution has to be looked for, which leads to a formulation
in terms of 'Maximun Constraint Satisfaction' (a generalization of
the MAX-SAT problem). Several alternate formulations of these basic
problems will be presented, e.g. using integer programming, quadratic
0-1 pseudoboolean programming, etc. A variety of exact and
approximate solution algorithms will be discussed, including local search
simulated annealing, genetic search, and exact and approximate
tree-search methods. Recent computational work on how to get good
lower bounds for the Max-CSP version of the problem will also be
presented.
Minimum cost multicommodity flows are basic models frequently arising
in the context of topological network optimization, optimal network
design and dimensioning. The computational difficulty in solving such
problems greatly depends on the structure of the cost function
to be optimized . For instance, if the cost function is separable and
linear (with nonnegative cost per unit flow) on each link, then the
problem is easily shown to reduce to shortest path computations.
In this talk, we will concentrate on two hard versions of the problem,
namely (i) the case of discontinuous step increasing separable cost
functions , and (ii) the case of separable continuously differentiable
concave cost functions. For version (i) we discuss linear
programming relaxations for computing lower bounds, together with
various efficient heuristics for computing upper bounds. Also,
experiments with a Benders- based constraint generation approach,
using a novel constraint-generation procedure will be presented.
We also investigate possible connections between version (i) and
version (ii) of the problem by showing possible reformulation of the
latter (a continuously differentiable concave minimization problem)
as a 0-1 mixed integer program.
Return to the LSDO tutorial topics page