Given a graph with and , we consider the metric cone and the metric polytope defined on . These polyhedra are relaxations of several important problems in combinatorial optimization such as the max‐cut problem and the multicommodity flow problem. They are known to have non‐compact formulations via the cycle inequalities in the original space and compact (i.e., polynomial size) extended formulations via the triangle inequalities defined on the complete graph . In this article, we show that one can reduce the number of triangle inequalities to and still have extended formulations for and . This is particularly interesting for sparse graphs when , since formulations of size variables and constraints are thus obtained. Moreover, the possibility of achieving further reduction in size for special classes of sparse graphs is investigated; it is shown that for the case of series‐parallel graphs, for which the max‐cut problem can be solved in linear time (Barahona, Discr Appl Math 13 (1986), 23–26), one can refine the above reduction to obtain extended formulations for and featuring variables and constraints. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 142–150 2017

Best application paper award

Abstract Yield management techniques have been used by companies in various competitive industrial contexts in order to keep a high level of revenue. With the opening of the telecommunications markets, operators are looking for ways of including competition in their decision process. By analyzing the customers' preferences, the market can be segmented into groups of similar preferences, and offers targeted to a particular market segment. In this paper, we study a problem of revenue management for a network operator offering services on end‐to‐end markets, while facing competition. We present a natural formulation for this problem that uses bilinear bilevel programming models, similar to those used in the airline industry [Côté et al., J Revenue Pricing Manage 2 (2003), 23–36]. However, such an approach leads to optimization problems that are very difficult to solve exactly on the large scale instances found in the telecommunications industry. To address difficulties solving large problems, we introduce a new alternative formulation for the problem, give a proof of NP‐hardness, and propose solution methods related to this formulation. The first one is an exact method based on a branch‐and‐bound algorithm; then we propose two approximate methods, one based on Lagrangian relaxation, and one based on a concave approximation of the objective function to be maximized. Comparative results are given. We show that this approach is practically efficient and leads to exact solutions for instances of telecommunications networks of a size larger than previously possible. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 37–49 2007

This paper describes a new procedure for generating very large realistic benchmark circuits which are especially suited for the performance evaluation of field programmable gate array partitioning algorithms. These benchmark circuits can be generated quickly. The generation of a netlist of 100 K configurable logic blocks (500 K equivalent gates), for instance, takes only 2 min on a standard UNIX workstation. The analysis of a large number of netlists from real designs lead us to identify the following five different kinds of subblocks: regular combinational logic, irregular combinational logic, combinational and sequential logic, memory blocks, and interconnections. Therefore, our generator integrates a subgenerator for each of these types of netlist. The comparison of the partitioning results of industrial netlists with those obtained from generated netlists of the same size shows that the generated netlists behave similarly to the originals in terms of average filling rate and average pin utilization.

This paper describes a new procedure for generating very large realistic benchmark circuits which are especially suited for the performance evaluation of FPGA partitioning algorithms.These benchmark circuits can be generated quickly.The generation of a netlist of 1OOK CLBs (500K equivalent gates), for instance, takes only two minutes on a standard UNIX workstation.The analysis of a large number of netlists from real designs lead us to identify the following five different kinds of sub-blocks: Regular combinational logic, irregular combinational logic, combinational and sequential logic, memory blocks, and interconnections.Therefore, our generator integrates a sub-generator for each of these types of netlist.The comparison of the partitioning results of industrial netlists with those obtained from generated netlists of the same size shows that the generated netlists behave similarly to the originals in terms of average filling rate and average pin utilization.

Abstract We describe a new algorithm for minimum cost perfect matching problems in arbitrary (nonbipartite) graphs based on an active constraint set strategy on the whole set of constraints defining the matching polytope (the so‐called Edmonds' constraints or blossom inequalities). At each step, the resulting subproblem reduces to a minium cost network flow problem which may be solved either via classical network flow algorithms, or via primal network flow algorithms. Finite convergence of the algorithm is proved under a nondegeneracy assumption and an anticycling procedure is defined for ensuring finite termination in degenerate cases. Computer experiments using a primal code for the network flow subproblems show that this approach appears to be competitive even with respect to the most efficient general matching codes currently described in the literature.

Abstract This paper is intended as a survey in the area of network synthesis and optimum network design, which, in view of the importance and variety of the underlying applications, has attraced, since the early 1960s, much interest in the Operations Research community. Indeed, if the first models were studied in connection with telecommunication networks, the range of applications kept on getting broader and broader, including transportation networks, computer and teleprocessing networks, energy transport systems, water distribution networks, etc. However, beyond the apparent diversity of practical situations involved, most of these applications can be accounted for (modulo possibly a few minor adaptations), by a rather limited number of basic models. One of the main purposes of this paper is to provide the reader with a relevant classification of the area which will help him identify the fundamental structure of the problem (if any) he has to cope with, and relate it to already published work. In order to obtain a fairly good coverage of the matter, we have thus been led to identify three basic models aroung which the whole paper is organized: a general model using minimum cost multicommodity flows (Section 2); models in terms of tree‐like networks (Section 3); models using nonsmultaneous single‐commodity or multicommodity flows (Section 4). In each bcase the most important variants of the basic models have been surveyed with the purpose of providing as much information as possible concerning (a) the various contexts of applications from which the problem arose; (b) the main computational methods proposed in the literature for solving it, with emphasis on those techniques which appear at present, to be most efficient or promising.