Friday, May 7, 1999: Generalized graph coloring and the frequency assignment problem (With slide Show!)

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.

---

Thursday, May 13, 1999: Some Combinatorial problems in optimal telecommunication network design (With slide Show!)

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