Contributed Session Tue.3.H 3012

Tuesday, 15:15 - 16:45 h, Room: H 3012

Cluster 2: Combinatorial optimization [...]

LP relaxations


Chair: Dorit S. Hochbaum



Tuesday, 15:15 - 15:40 h, Room: H 3012, Talk 1

Maria Teresa Godinho
On a time-dependent formulation for the travelling salesman problem

Coauthors: Luís Gouveia, Pierre Pesneau


In the past, several papers have produced a classification of formulations for the ATSP, in terms of the associated linear programming relaxations. Among others, we may consider the papers by Gouveia and Voss (1995), Langevin et al (1990), Gouveia and Pires (1999), Orman and Williams (2007) and Oncan et al (2009). These papers fall among two classes. Either they produce new results between formulations known from the literature, or they use the fact that new formulations are also being presented in the paper in order to upgrade a classification already known from the literature.
Our talks falls in the second category in the sense that we present an updated classification of formulations for the asymmetric travelling salesman problem (ATSP)where we contextualize, in terms of the ATSP, a new time-dependent formulation presented in Godinho et al (2010).
The main feature of this formulation is that it uses, for each node, a stronger subproblem, namely a n-circuit subproblem with the additional constraint that the corresponding node is not repeated in the circuit.



Tuesday, 15:45 - 16:10 h, Room: H 3012, Talk 2

Dorit S. Hochbaum
Flow-based algorithms that solve clustering problems related to graph expander, normalized cut and conductance better than the spectral method


We address challenging problems in clustering, partitioning and imaging including the normalized cut
problem, graph expander, Cheeger constant problem and conductance problem. These have traditionally
been solved using the "spectral technique''. These problems are formulated here as a quadratic
ratio (Rayleigh) with discrete constraints and a single sum constraint. The spectral method solves
a relaxation that omits the discreteness constraints. A new relaxation, that omits the sum
constraint, is shown to be solvable in strongly polynomial time. It is shown, via an experimental
study, that the bipartition achieved by the combinatorial algorithm often improve dramatically in
terms of the objective value of the respective NP-hard problem, as well as in terms of the visual
quality of the segmentation, compared to the spectral method in image segmentation and image
denoising instances.



Tuesday, 16:15 - 16:40 h, Room: H 3012, Talk 3

Yong-Hong Kuo
On the mixed set covering, partitioning and packing problem

Coauthor: Janny M. Y. Leung


Set covering, set partitioning and set packing problems have already been studied for more than 40 years. However, researchers usually consider the problems individually and very few literatures have mentioned the mixed set covering, partitioning and packing problem, where the three kinds of constraints are present simultaneously in the formulation. The problems with such kind of structures play an important role in the real-life applications, e.g., staff scheduling problems. In this talk, we will discuss the polyhedral structure of the problem and present a way, which we call "implicit edges generation'' approach, to further tighten the feasible region and, as a result, makes the LP optimal closer to the IP optimal. We will also present some classes of facet-defining inequalities produced by this approach. Computational results show that, using our proposed methodology, a tighter formulation can be obtained and, consequently significant reductions of computational efforts are made.


  Do you need Missouri Payday Loans as soon as possible? What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.