We investigate (0,1)-matrices that are convex, which means that the ones are consecutive in every row and column. These matrices occur in discrete tomography. The notion of ranked essential sets, known for permutation matrices, is extended to convex sets. We show a number of results for the class C(R,S) of convex matrices with given row and column sum vectors R and S. Also, it is shown that the ranked essential set uniquely determines a matrix in C(R,S).

Abstract In this article we analyze certain matching problems that arise in ground delay program planning. Ground delay programs are air traffic flow management initiatives put in place when airport arrival demand is expected to exceed arrival capacity for an extended length of time, e.g. 4 h. Most of the problems we study can be modeled as assignment problems, where flights are assigned to arrival slots. In the context we analyze, however, these problems have important special structure, which allows us to develop special solution properties. In particular, solutions are measured both in terms of efficiency (delay minimization) and equity (delay distribution). We show that the theory of majorization provides a powerful tool in addressing solution equity. We consider problems with flight deletions and develop special solution properties and parametric methods. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract We investigate distance vectors in trees and introduce a new center concept based on the notion of majorization and discuss relations to location theory. For a tree T and a vertex v ∈ T, we define the distance vector d(v,·) = (d(v,w) w ∈ T), where d(v,w) denotes the distance between v and a vertex w. We characterize whenever d(u,·) is weakly majorized by d(v,·) for adjacent vertices u and v. Moreover, we introduce a new center concept in trees, the majorization‐center, and relate this to known centers and the set of balance vertices. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(4), 251–257 2007

Abstract Given a graph with nonnegative edge weights and a set D of node pairs, the 2‐ path network problem requires a minimum weight set of edges such that the induced subgraph contains a path with one or two edges connecting each pair in D . The problem is NP ‐hard. We present two integer programming models for the problem and study properties of associated polytopes, including cutting planes. Two approximation algorithms are suggested and analyzed. Some computational experience is reported. © 2004 Wiley Periodicals, Inc.

We study the cardinality-constrained shortest path problem in acyclic graphs and, in particular, in the class of 2-graphs where we show that the problem may be solved by linear programming. A combinatorial algorithm is introduced based on some adjacency results for associated polytopes. An application in curve approximation is discussed and computational results are given where the mentioned algorithms are compared to Lagrangian relaxation and dynamic programming algorithms. © 2000 John Wiley & Sons, Inc.

Finding maximum a posteriori (MAP) solutions from noisy images based on a prior Markov random field (MRF) model is a huge computational task. In this paper, we transform the computational problem into an integer linear programming (ILP) problem. We explore the use of Lagrange relaxation (LR) methods for solving the MAP problem. In particular, three different algorithms based on LR are presented. All the methods are competitive alternatives to the commonly used simulation-based algorithms based on Markov Chain Monte Carlo techniques. In all the examples (including both simulated and real images) that have been tested, the best method essentially finds a MAP solution in a small number of iterations. In addition, LR methods provide lower and upper bounds for the posterior, which makes it possible to evaluate the quality of solutions and to construct a stopping criterion for the algorithm. Although additive Gaussian noise models have been applied, any additive noise model fits into the framework.

We present a cutting plane algorithm for solving the following telecommunications network design problem: given point-to-point traffic demands in a network, specified survivability requirements and a discrete cost/capacity function for each link, find minimum cost capacity expansions satisfying the given demands. This algorithm is based on the polyhedral study described in [19]. In this article we describe the underlying problem, the model and the main ingredients in our algorithm. This includes: initial formulation, feasibility test, separation for strong cutting planes, and primal heuristics. Computational results for a set of real-world problems are reported.