Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
An Exact Algorithm for the Steiner Forest Problem
Full text linkThe Steiner forest problem asks for a minimum weight forest that spans a given number of terminal sets. The problem has famous linear programming based 2-approximations [Agrawal et al., 1995; Goemans and Williamson, 1995; Jain, 2001] whose bottleneck is the fact that the most natural formulation of the problem as an integer linear program (ILP) has an integrality gap of 2. We propose new cut-based ILP formulations for the problem along with exact branch-and-bound based algorithms. While our new formulations cannot improve the integrality gap, we can prove that one of them yields stronger linear programming bounds than the two previous strongest formulations: The directed cut formulation [Balakrishnan et al., 1989; Chopra and Rao, 1994] and the advanced flow-based formulation by Magnanti and Raghavan [Magnanti and Raghavan, 2005]. In an experimental evaluation, we show that the linear programming bounds of the new formulations are indeed strong on practical instances and that our new branch-and-bound algorithms outperform branch-and-bound algorithms based on the previous formulations. Our formulations can be seen as a cut-based analogon to [Magnanti and Raghavan, 2005], whose existence was an open problem
Linear Ordering Based MIP Formulations for the Vertex Separation or Pathwidth Problem
No full textWe consider the task to compute the pathwidth of a graph which is known to be equivalent to solving the vertex separation problem. The latter is naturally modeled as a linear ordering problem with respect to the vertices of the graph. Present mixed-integer programs for the vertex separation problem express linear orders using either position or set assignment variables. However, as we show, the lower bound on the pathwidth obtained when solving their linear programming relaxations is zero for any directed graph. This is one reason for their limited utility in solving larger instances to optimality. We then present a new formulation that is based on conventional linear ordering variables and a slightly different perspective on the problem. Its relaxation provably delivers non-zero lower bounds for any graph whose pathwidth is non-zero. Further structural results for and extensions to this formulation are discussed. Finally, an experimental evaluation of three mixed-integer programs, each representing one of the different yet existing modeling approaches, displays their potentials and limitations when used to solve the problem to optimality in practice
A Local-Search Algorithm for Steiner Forest
No full textIn the Steiner Forest problem, we are given a graph and a collection of source-sink pairs, and the goal is to find a subgraph of minimum total length such that all pairs are connected. The problem is APX-Hard and can be 2-approximated by, e.g., the elegant primal-dual algorithm of Agrawal, Klein, and Ravi from 1995.
We give a local-search-based constant-factor approximation for the problem. Local search brings in new techniques to an area that has for long not seen any improvements and might be a step towards a combinatorial algorithm for the more general survivable network design problem. Moreover, local search was an essential tool to tackle the dynamic MST/Steiner Tree problem, whereas dynamic Steiner Forest is still wide open.
It is easy to see that any constant factor local search algorithm requires steps that add/drop many edges together. We propose natural local moves which, at each step, either (a) add a shortest path in the current graph and then drop a bunch of inessential edges, or (b) add a set of edges to the current solution. This second type of moves is motivated by the potential function we use to measure progress, combining the cost of the solution with a penalty for each connected component. Our carefully-chosen local moves and potential function work in tandem to eliminate bad local minima that arise when using more traditional local moves.
Our analysis first considers the case where the local optimum is a single tree, and shows optimality w.r.t. moves that add a single edge (and drop a set of edges) is enough to bound the locality gap. For the general case, we show how to "project" the optimal solution onto the different trees of the local optimum without incurring too much cost (and this argument uses optimality w.r.t. both kinds of moves), followed by a tree-by-tree argument. We hope both the potential function, and our analysis techniques will be useful to develop and analyze local-search algorithms in other contexts
Compact Hierarchical Graph Drawings via Quadratic Layer Assignment
Full text linkWe propose a new mixed-integer programming formulation that very naturally expresses the layout restrictions of a layered (hierarchical) graph drawing and several associated objectives, such as a minimum total arc length, number of reversed arcs, and width, or the adaptation to a specific drawing area, as a special quadratic assignment problem. Our experiments show that it is competitive to another formulation that we slightly simplify as well
Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays
No full textWe revise existing and introduce new mixed-integer programming models for the Multiprocessor scheduling problem with communication delays. The basis for both is the identification of two major modeling strategies one of which can be considered ordering-based, and the other assignment-based. We first reveal redundancies in the encoding of feasible solutions found in present formulations and discuss how they can be avoided. For the assignment-based approach, we propose new inequalities that lead to provably stronger continuous relaxations and better performance in practice. Moreover, we derive a third, novel modeling strategy and show how to more compactly linearize assignment formulations with quadratic constraints. In a comprehensive experimental comparison of representative models that reflect the state-of-the-art in terms of strength and size, we evaluate not only running times but also the obtained lower and upper bounds on the makespan for the harder instances of a large scale benchmark set
Compact Linearization for Binary Quadratic Problems subject to Linear Equations
No full textIn this paper it is shown that the compact linearization approach, that has been previously proposed only for binary quadratic problems with assignment constraints, can be generalized to arbitrary linear equations with positive coefficients which considerably enlarges its applicability. We discuss special cases of prominent quadratic combinatorial optimization problems where the obtained compact linearization yields a continuous relaxation that is provably as least as strong as the one obtained with an ordinary linearization
Linear Ordering Based MIP Formulations for the Vertex Separation or Pathwidth Problem
No full textWe consider the vertex separation problem in directed graphs G=(V,A) that has been shown to be equivalent to the pathwidth problem. Naturally, it is modeled as finding a linear order (permutation) of the vertices V such that its induced maximum vertex separation is minimum. Mixed-integer programs proposed so far construct linear orders using either position or set assignment variables. We prove that, for any directed graph, solving their linear programming relaxations yields a lower bound of zero on the true vertex separation number. We then present a new and compact mixed-integer program that sustains stronger lower bounds. It is based on true linear ordering variables and a slightly different perspective on the problem. An experimental evaluation of three formulations in total, each representing a different modeling scheme, displays their potentials and limitations when used to solve the problem to optimality
MIP Formulations for the Steiner Forest Problem
No full textThe Steiner Forest problem is among the fundamental network design problems. Finding tight linear programming bounds for the problem is the key for both fast Branch-and-Bound algorithms and good primal-dual approximations. On the theoretical side, the best known bound can be obtained from an integer program [KLSv08]. It guarantees a value that is a (2-eps)-approximation of the integer optimum. On the practical side, bounds from a mixed integer program by Magnanti and Raghavan [MR05] are very close to the integer optimum in computational experiments, but the size of the model limits its practical usefulness. We compare a number of known integer programming formulations for the problem and propose three new formulations. We can show that the bounds from our two new cut-based formulations for the problem are within a factor of 2 of the integer optimum. In our experiments, the formulations prove to be both tractable and provide better bounds than all other tractable formulations. In particular, the factor to the integer optimum is much better than 2 in the experiments
Compact linearization for binary quadratic problems subject to assignment constraints
No full textWe introduce and prove new necessary and sufficient conditions to carry out a compact linearization approach for a general class of binary quadratic problems subject to assignment constraints that has been proposed by Liberti (4OR 5(3):231–245, 2007, https://doi.org/10.1007/s10288-006-0015-3). The new conditions resolve inconsistencies that can occur when the original method is used. We also present a mixed-integer linear program to compute a minimally sized linearization. When all the assignment constraints have non-overlapping variable support, this program is shown to have a totally unimodular constraint matrix. Finally, we give a polynomial-time combinatorial algorithm that is exact in this case and can be used as a heuristic otherwise
Crossing Minimization in Storyline Visualization
Full text linkA storyline visualization is a layout that represents the temporal dynamics of social interactions along time by the convergence of chronological lines. Among the criteria oriented at improving aesthetics and legibility of a representation of this type, a small number of line crossings is the hardest to achieve. We model the crossing minimization in the storyline visualization problem as a multi-layer crossing minimization problem with tree constraints. Our algorithm can compute a layout with the minimum number of crossings of the chronological lines. Computational results demonstrate that it can solve instances with more than 100 interactions and with more than 100 chronological lines to optimality