Abstract In this paper we consider the covering problem on a network G = ( V , E ) with edge demands. The task is to cover a subset J ⊆ E of the edges with a minimum number of facilities within a predefined coverage radius. We focus on both the nodal and the absolute version of this problem. In the latter, facilities may be placed everywhere in the network. While there already exist polynomial time algorithms to solve the problem on trees, we establish a finite dominating set (i.e., a finite subset of points provably containing an optimal solution) for the absolute version in general graphs. Complexity and approximability results are given and a greedy strategy is proved to be a (1 + ln(| J |))‐approximate algorithm. Finally, the different approaches are compared in a computational study.

Maximum likelihood (ML) decoding is the optimal decoding algorithm for arbitrary linear block codes and can be written as an integer programming (IP) problem. Feldman relaxed this IP problem and presented linear programming (LP) based decoding. In this paper, we propose a new separation algorithm to improve the error-correcting performance of LP decoding for binary linear block codes. We use an IP formulation with indicator variables that help in detecting the violated parity checks. We derive Gomory cuts from the IP and use them in our separation algorithm. An efficient method of finding cuts induced by redundant parity checks (RPC) is also proposed. Under certain circumstances we can guarantee that these RPC cuts are valid and cut off the fractional optimal solutions of LP decoding. It is demonstrated on three LDPC codes and two BCH codes that our separation algorithm performs significantly better than LP decoding and belief propagation (BP) decoding.

We study an integer programming (IP) based separation approach to find the maximum likelihood (ML) codeword for binary linear codes. An algorithm introduced in Tanatmis et al. is extended and improved with respect to decoding performance without increasing the worst case complexity. This is demonstrated on the LDPC and the BCH code classes. Moreover, we propose an integer programming formulation to calculate the minimum distance of a binary linear code. We exemplarily compute the minimum distance of the (204, 102) LDPC code and the (576, 288) WIMAX code. Using the minimum distance of a code, a new class of valid inequalities is introduced.

Finding a delivery plan for cancer radiation treatment using multileaf collimators operating in “step-and-shoot” mode can be formulated mathematically as a problem of decomposing an integer matrix into a weighted sum of binary matrices having the consecutive-ones property and sometimes other properties related to the collimator technology. The efficiency of the delivery plan is measured by both the sum of the weights in the decomposition, known as the total beam-on time, and the number of different binary matrices appearing in it, referred to as the cardinality, the latter being closely related to the setup time of the treatment. In practice, the total beam-on time is usually restricted to its minimum possible value (which is easy to find), and a decomposition that minimizes cardinality (subject to this restriction) is sought. This decomposition problem is known to be NP-hard, and the best available exact solution methods cannot solve, in reasonable time, problems with dimensions large enough to be of use in actual medical applications. In this paper, we propose a new heuristic. To ensure that the heuristic is computationally efficient, we make use of exact bounds that apply to the decomposition and prove that these bounds can be computed efficiently. We demonstrate that the heuristic performs very well numerically against the best previously published heuristic (that of Kalinowski), reducing the average gap between the cardinality of the solution found and the optimal value by 37% on the largest problems tested (for which optimal solutions could be found). Importantly, this new heuristic performs well on those instances that are problematical for Kalinowski's heuristic. A “best-of” algorithm, combining heuristics, produces a decomposition with cardinality within one of optimal in about 98.7% of instances tested (for which an optimal solution is available). It reduces the cardinality of solutions produced by about 5% on average. On instances for which optimal solutions can be found, it more than halves the optimality gap and finds an optimal solution in about 28% more cases than Kalinowski's heuristic.

Abstract In this article, we study the modulation of intensity matrices arising in cancer radiation therapy using multileaf collimators. This problem can be formulated by decomposing a given m × n integer matrix into a positive linear combination of (0, 1) matrices with the strict consecutive 1's property in rows. We consider a special case in which no technical constraints have to be taken into account. In this situation, the rows of the intensity matrix are independent of each other and the problem is equivalent to decomposing m intensity rows—independent of each other—into positive linear combinations of (0, 1) rows with the consecutive 1's property. We demonstrate that this problem can be transformed into a minimum cost flow problem in a directed network that has the following special structures: (1) the network is acyclic; (2) it is a complete graph (that is, there is an arc ( i , j ) whenever i < j ); (3) each arc cost is 1; and (4) each arc is uncapacitated (that is, it has infinite capacity). We show that using this special structure, the minimum cost flow problem can be solved in O( n ) time. Because we need to solve m such problems, the total running time of our algorithm is O( nm ), which is an optimal algorithm to decompose a given m × n integer matrix into a positive linear combination of (0, 1) matrices. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 36–41 2005

Abstract In this article the modulation of intensity matrices arising in cancer radiation therapy using multileaf collimators (MLC) is investigated. It is shown that the problem is equivalent to decomposing a given integer matrix into a positive linear combination of (0, 1) matrices. These matrices, called shape matrices, must have the strict consecutive‐1‐property, together with another property derived from the technological restrictions of the MLC equipment. Various decompositions can be evaluated by their beam‐on time (time during which radiation is applied to the patient) or the treatment time (beam‐on time plus time for setups). We focus on the former, and develop a nonlinear mixed‐integer programming formulation of the problem. This formulation can be decomposed to yield a column generation formulation: a linear program with a large number of variables that can be priced by solving a subproblem. We then develop a network model in which paths in the network correspond to feasible shape matrices. As a consequence, we deduce that the column generation subproblem can be solved as a shortest path problem. Furthermore, we are able to develop two alternative models of the problem as side‐constrained network flow formulations, and so obtain our main theoretical result that the problem is solvable in polynomial time. Finally, a numerical comparison of our exact solutions with those of well‐known heuristic methods shows that the beam‐on time can be reduced by a considerable margin. © 2004 Wiley Periodicals, Inc.

In this paper, network location problems with several objectives are discussed, where every single objective is a classical median objective function. We will look at the problem of finding Pareto optimal locations and lexicographically optimal locations. It is shown that for Pareto optimal locations in undirected networks no node dominance result can be shown. Structural results as well as efficient algorithms for these multicriteria problems are developed. In the special case of a tree network, a generalization of Goldman's dominance algorithm for finding Pareto locations is presented. © 1999 John Wiley & Sons, Inc. Networks 33: 79–92, 1999

Abstract We consider the k‐CARD TREE problem, i.e., the problem of finding in a given undirected graph G a subtree with k edges, having minimum weight. Applications of this problem arise in oil‐field leasing and facility layout. Although the general problem is shown to be strongly NP hard, it can be solved in polynomial time if G is itself a tree. We give an integer programming formulation of k‐CARD TREE and an efficient exact separation routine for a set of generalized subtour elimination constraints. The polyhedral structure of the convex hull of the integer solutions is studied. © 1994 by John Wiley & Sons, Inc.

Given two matroids $M_1 = (E,\mathcal{J}_1 )$ and, $M_2 = (E,\mathcal{J}_2 )$, three algorithms for finding K best intersections $I_1 ,I_2 , \cdots ,I_K $ are presented. The first version is a straightforward application of a general procedure due to Murty and Lawler. The complexity for finding $I_2 , \cdots ,I_k $ is $O(Km^2 R(R + c(m) + \log m))$ where m is the number of elements in $E, R = \min \{ r_1 (E),r_2 (E)\} $, and $c(m)$ is the complexity of an independence oracle. By using maximum weighted border paths to compute second best intersections of modified matroids, this bound is reduced to $O(K(m^3 + mRc(m))$. Finally, a condensed version of the border graph is proposed to further improve the bound to $O(KmRc(m))$. The latter idea can also be used to find the optimal intersection $I_1 $ in $O(mR^2 c(m))$ time, which is competitive with recent matroid intersection algorithms by Frank [J. Algorithms, 2 (1981), pp. 328–336] and Brezovec, Cornuejols, and Glover [Math. Programming, 36 (1986), pp. 39–53].