Sequence Independent Lifting in Mixed Integer Programming

We investigate lifting, i.e., the process of taking a valid inequality for a polyhedron and extending it to a valid inequality in a higher dimensional space. Lifting is usually applied sequentially, that is, variables in a set are lifted one after the other. This may be computationally unattractive since it involves the solution of an optimization problem to compute a lifting coefficient for each variable. To relieve this computational burden, we study sequence independent lifting, which only involves the solution of one optimization problem. We show that if a certain lifting function is superadditive, then the lifting coefficients are independent of the lifting sequence. We introduce the idea of valid superadditive lifting functions to obtain good aproximations to maximum lifting. We apply these results to strengthen Balas' lifting theorem for cover inequalities and to produce lifted flow cover inequalities for a single node flow problem.     

Facets of an Assignment Problem with 0–1 Side Constraint

We show that the problem of finding a perfect matching satisfying a single equality constraint with a 0–1 coefficients in an n × n incomplete bipartite graph, polynomially reduces to a special case of the same peoblem called the partitioned case. Finding a solution matching for the partitioned case in the incomlpete bipartite graph, is equivalent to minimizing a partial sum of the variables over = the convex hull of incidence vectors of solution matchings for the partitioned case in the complete bipartite graph. An important strategy to solve this minimization problem is to develop a polyhedral characterization of . Towards this effort, we present two large classes of valid inequalities for , which are proved to be facet inducing using a facet lifting scheme.     

Robotic-Cell Scheduling: Special Polynomially Solvable Cases of the Traveling Salesman Problem on Permuted Monge Matrices

In this paper, we introduce the 1 − K robotic-cell scheduling problem, whose solution can be reduced to solving a TSP on specially structured permuted Monge matrices, we call b-decomposable matrices. We also review a number of other scheduling problems which all reduce to solving TSP-s on permuted Monge matrices. We present the important insight that the TSP on b-decomposable matrices can be solved in polynomial time by a special adaptation of the well-known subtour-patching technique. We discuss efficient implementations of this algorithm on newly defined subclasses of permuted Monge matrices.     

The 2-Edge-Connected Subgraph Polyhedron

We study the polyhedron P(G) defined by the convex hull of 2-edge-connected subgraphs of G where multiple copies of edges may be chosen. We show that each vertex of P(G) is also a vertex of the LP relaxation. Given the close relationship with the Graphical Traveling Salesman problem (GTSP), we examine how polyhedral results for GTSP can be modified and applied to P(G). We characterize graphs for which P(G) is integral and study how this relates to a similar result for GTSP. In addition, we show how one can modify some classes of valid inequalities for GTSP and produce new valid inequalities and facets for P(G).     

Exact and heuristic algorithms for solving the generalized minimum filter placement problem

We consider a problem of placing route-based filters in a communication network to limit the number of forged address attacks to a prescribed level. Nodes in the network communicate by exchanging packets along arcs, and the originating node embeds the origin and destination addresses within each packet that it sends. In the absence of a validation mechanism, one node can send packets to another node using a forged origin address to launch an attack against that node. Route-based filters can be established at various nodes on the communication network to protect against these attacks. A route-based filter examines each packet arriving at a node, and determines whether or not the origin address could be legitimate, based on the arc on which the packet arrives, the routing information, and possibly the destination. The problem we consider seeks to find a minimum cardinality subset of nodes to filter so that the prescribed level of security is achieved. We formulate a mixed-integer programming model for the problem and derive valid inequalities for this model by identifying polynomially-solvable subgraphs of the communication network. We also present three heuristics for solving the filter placement problem and evaluate their performance against the optimal solution provided by the mixed-integer programming model. The authors gratefully acknowledge the comments of two anonymous referees, whose input led to an improved version of this paper. Dr. Smith gratefully acknowledges the support of the Office of Naval Research under Grant #N00014-03-1-0510 and the Defense Advanced Research Projects Agency under Grant #N66001-01-1-8925.     

b-Tree Facets for the Simple Graph Partitioning Polytope

The simple graph partitioning problem is to partition an edge-weighted graph into mutually disjoint subgraphs, each consisting of no more than b nodes, such that the sum of the weights of all edges in the subgraphs is maximal. In this paper we introduce a large class of facet defining inequalities for the simple graph partitioning polytopes _n (b), b 3, associated with the complete graph on n nodes. These inequalities are induced by a graph configuration which is built upon trees of cardinality b. We provide a closed-form theorem that states all necessary and sufficient conditions for the facet defining property of the inequalities.     

The Wheels of the Orthogonal Latin Squares Polytope: Classification and Valid Inequalities

A wheel in a graph G(V,E) is an induced subgraph consisting of an odd hole and an additional node connected to all nodes of the hole. In this paper, we study the wheels of the intersection graph of the Orthogonal Latin Squares polytope (P_I). Our work builds on structural properties of wheels which are used to categorise them into a number of collectively exhaustive classes. These classes give rise to families of inequalities that are valid for P_I and facet-defining for its set-packing relaxation. The classification introduced allows us to establish the cardinality of the whole wheel class and determine the range of the coefficients of any variable included in a lifted wheel inequality. Finally, based on this classification, a constant-time recognition algorithm for wheel-inducing circulant matrices, is introduced.     

The min-up/min-down unit commitment polytope

The min-up/min-down unit commitment problem (MUCP) is to find a minimum-cost production plan on a discrete time horizon for a set of fossil-fuel units for electricity production. At each time period, the total production has to meet a forecast demand. Each unit must satisfy minimum up-time and down-time constraints besides featuring production and start-up costs. A full polyhedral characterization of the MUCP with only one production unit is provided by Rajan and Takriti (Minimum up/down polytopes of the unit commitment problem with start-up costs. IBM Research Report, 2005). In this article, we analyze polyhedral aspects of the MUCP with n production units. We first translate the classical extended cover inequalities of the knapsack polytope to obtain the so-called up-set inequalities for the MUCP polytope. We introduce the interval up-set inequalities as a new class of valid inequalities, which generalizes both up-set inequalities and minimum up-time inequalities. We provide a characterization of the cases when interval up-set inequalities are valid and not dominated by other inequalities. We devise an efficient Branch and Cut algorithm, using up-set and interval up-set inequalities.     

Requiring Connectivity in the Set Covering Problem

Given a bipartite graph with bipartition V and W, a cover is a subset C V such that each node of W is adjacent to at least one node in C. The set covering problem seeks a minimum cardinality cover. Set covering has many practical applications. In the context of reserve selection for conservation of species, V is a set of candidate sites from a reserve network, W is the set of species to be protected, and the edges describe which species are represented in each site. Some covers however may assume spatial configurations which are not adequate for conservational purposes. Indeed, for sustainability reasons the fragmentation of existing natural habitats should be avoided, since this is recognized as being disruptive to the species adapted to the habitats. Thus, connectivity appears to be an important issue for protection of biological diversity. We therefore consider along with the bipartite graph, a graph G with node set V, describing the adjacencies of the elements of V, and we look for those covers C V for which the subgraph of G induced by C is connected. We call such covers connected covers. In this paper we introduce and study some valid inequalities for the convex hull of the set of incidence vectors of connected covers.MSC2000: 90C10, 90C57This authors research was financially supported by the Portuguese Foundation for Science and Technology (FCT).This paper is part of this authors Ph.D. research.     

Geometry of Semidefinite Max-Cut Relaxations via Matrix Ranks

Semidefinite programming (SDP) relaxations are proving to be a powerful tool for finding tight bounds for hard discrete optimization problems. This is especially true for one of the easier NP-hard problems, the Max-Cut problem (MC). The well-known SDP relaxation for Max-Cut, here denoted SDP1, can be derived by a first lifting into matrix space and has been shown to be excellent both in theory and in practice.Recently the present authors have derived a new relaxation using a second lifting. This new relaxation, denoted SDP2, is strictly tighter than the relaxation obtained by adding all the triangle inequalities to the well-known relaxation. In this paper we present new results that further describe the remarkable tightness of this new relaxation. Let denote the feasible set of SDP2 for the complete graph with n nodes, let F _n denote the appropriately defined projection of into , the space of real symmetric n × n matrices, and let C _n denote the cut polytope in . Further let be the matrix variable of the SDP2 relaxation and X F _n be its projection. Then for the complete graph on 3 nodes, F ₃ = C ₃ holds. We prove that the rank of the matrix variable of SDP2 completely characterizes the dimension of the face of the cut polytope in which the corresponding matrix X lies. This shows explicitly the connection between the rank of the variable Y of the second lifting and the possible locations of the projected matrix X within C ₃. The results we prove for n = 3 cast further light on how SDP2 captures all the structure of C ₃, and furthermore they are stepping stones for studying the general case n 4. For this case, we show that the characterization of the vertices of the cut polytope via rank Y = 1 extends to all n 4. More interestingly, we show that the characterization of the one-dimensional faces via rank Y = 2 also holds for n 4. Furthermore, we prove that if rank Y = 2 for n 3, then a simple algorithm exhibits the two rank-one matrices (corresponding to cuts) which are the vertices of the one-dimensional face of the cut polytope where X lies.     

Bootstrap Inference in Partially Identified Models Defined by Moment Inequalities: Coverage of the Identified Set

This paper introduces a novel bootstrap procedure to perform inference in a wide class of partially identified econometric models. We consider econometric models defined by finitely many weak moment inequalities, ² We can also admit models defined by moment equalities by combining pairs of weak moment inequalities.
which encompass many applications of economic interest. The objective of our inferential procedure is to cover the identified set with a prespecified probability. ³ We deal with the objective of covering each element of the identified set with a prespecified probability in Bugni (2010a).
We compare our bootstrap procedure, a competing asymptotic approximation, and subsampling procedures in terms of the rate at which they achieve the desired coverage level, also known as the error in the coverage probability. Under certain conditions, we show that our bootstrap procedure and the asymptotic approximation have the same order of error in the coverage probability, which is smaller than that obtained by using subsampling. This implies that inference based on our bootstrap and asymptotic approximation should eventually be more precise than inference based on subsampling. A Monte Carlo study confirms this finding in a small sample simulation.     

Inference Based on Conditional Moment Inequalities

In this paper, we propose an instrumental variable approach to constructing confidence sets (CS's) for the true parameter in models defined by conditional moment inequalities/equalities. We show that by properly choosing instrument functions, one can transform conditional moment inequalities/equalities into unconditional ones without losing identification power. Based on the unconditional moment inequalities/equalities, we construct CS's by inverting Cramér–von Mises‐type or Kolmogorov–Smirnov‐type tests. Critical values are obtained using generalized moment selection (GMS) procedures. We show that the proposed CS's have correct uniform asymptotic coverage probabilities. New methods are required to establish these results because an infinite‐dimensional nuisance parameter affects the asymptotic distributions. We show that the tests considered are consistent against all fixed alternatives and typically have power against n^−1/2‐local alternatives to some, but not all, sequences of distributions in the null hypothesis. Monte Carlo simulations for five different models show that the methods perform well in finite samples.     

On Disjunctive Cuts for Combinatorial Optimization

In the successful branch-and-cut approach to combinatorial optimization, linear inequalities are used as cutting planes within a branch-and-bound framework. Although researchers often prefer to use facet-inducing inequalities as cutting planes, good computational results have recently been obtained using disjunctive cuts, which are not guaranteed to be facet-inducing in general.A partial explanation for the success of the disjunctive cuts is given in this paper. It is shown that, for six important combinatorial optimization problems (the clique partitioning, max-cut, acyclic subdigraph, linear ordering, asymmetric travelling salesman and set covering problems), certain facet-inducing inequalities can be obtained by simple disjunctive techniques. New polynomial-time separation algorithms are obtained for these inequalities as a by-product.The disjunctive approach is then compared and contrasted with some other general-purpose frameworks for generating cutting planes and some conclusions are made with respect to the potential and limitations of the disjunctive approach.     

Online tree node assignment with resource augmentation

Given a complete binary tree of height h, the online tree node assignment problem is to serve a sequence of assignment/release requests, where an assignment request, with an integer parameter 0≤i≤h, is served by assigning a (tree) node of level (or height) i and a release request is served by releasing a specified assigned node. The node assignments have to guarantee that no node is assigned to two assignment requests unreleased, and every leaf-to-root path of the tree contains at most one assigned node. With assigned node reassignments allowed, the target of the problem is to minimize the number of assignments/reassignments, i.e., the cost, to serve the whole sequence of requests. This online tree node assignment problem is fundamental to many applications, including OVSF code assignment in WCDMA networks, buddy memory allocation and hypercube subcube allocation.     

Inference for Parameters Defined by Moment Inequalities: A Recommended Moment Selection Procedure

This paper is concerned with tests and confidence intervals for parameters that are not necessarily point identified and are defined by moment inequalities. In the literature, different test statistics, critical‐value methods, and implementation methods (i.e., the asymptotic distribution versus the bootstrap) have been proposed. In this paper, we compare these methods. We provide a recommended test statistic, moment selection critical value, and implementation method. We provide data‐dependent procedures for choosing the key moment selection tuning parameter κ and a size‐correction factor η.     

Inference for Parameters Defined by Moment Inequalities Using Generalized Moment Selection

The topic of this paper is inference in models in which parameters are defined by moment inequalities and/or equalities. The parameters may or may not be identified. This paper introduces a new class of confidence sets and tests based on generalized moment selection (GMS). GMS procedures are shown to have correct asymptotic size in a uniform sense and are shown not to be asymptotically conservative. The power of GMS tests is compared to that of subsampling, m out of n bootstrap, and “plug‐in asymptotic” (PA) tests. The latter three procedures are the only general procedures in the literature that have been shown to have correct asymptotic size (in a uniform sense) for the moment inequality/equality model. GMS tests are shown to have asymptotic power that dominates that of subsampling, m out of n bootstrap, and PA tests. Subsampling and m out of n bootstrap tests are shown to have asymptotic power that dominates that of PA tests.     

Best Nonparametric Bounds on Demand Responses

This paper uses revealed preference inequalities to provide the tightest possible (best) nonparametric bounds on predicted consumer responses to price changes using consumer‐level data over a finite set of relative price changes. These responses are allowed to vary nonparametrically across the income distribution. This is achieved by combining the theory of revealed preference with the semiparametric estimation of consumer expansion paths (Engel curves). We label these expansion path based bounds on demand responses as E‐bounds. Deviations from revealed preference restrictions are measured by preference perturbations which are shown to usefully characterize taste change and to provide a stochastic environment within which violations of revealed preference inequalities can be assessed.     

Implicit cover inequalities

In this paper we consider combinatorial optimization problems whose feasible sets are simultaneously restricted by a binary knapsack constraint and a cardinality constraint imposing the exact number of selected variables. In particular, such sets arise when the feasible set corresponds to the bases of a matroid with a side knapsack constraint, for instance the weighted spanning tree problem and the multiple choice knapsack problem. We introduce the family of implicit cover inequalities which generalize the well-known cover inequalities for such feasible sets and discuss the lifting of the implicit cover inequalities. A computational study for the weighted spanning tree problem is reported.     

The QAP-polytope and the graph isomorphism problem

In this paper we propose a geometric approach to solve the Graph Isomorphism (GI in short) problem. Given two graphs \(G_1, G_2\), the GI problem is to decide if the given graphs are isomorphic i.e., there exists an edge preserving bijection between the vertices of the two graphs. We propose an Integer Linear Program (ILP) that has a non-empty solution if and only if the given graphs are isomorphic. The convex hull of all possible solutions of the ILP has been studied in literature as the Quadratic Assignment Problem (QAP) polytope. We study the feasible region of the linear programming relaxation of the ILP and show that the given graphs are isomorphic if and only if this region intersects with the QAP-polytope. As a consequence, if the graphs are not isomorphic, the feasible region must lie entirely outside the QAP-polytope. We study the facial structure of the QAP-polytope with the intention of using the facet defining inequalities to eliminate the feasible region outside the polytope. We determine two new families of facet defining inequalities of the QAP-polytope and show that all the known facet defining inequalities are special instances of a general inequality. Further we define a partial ordering on each exponential sized family of facet defining inequalities and show that if there exists a common minimal violated inequality for all points in the feasible region outside the QAP-polytope, then we can solve the GI problem in polynomial time. We also study the general case when there are k such inequalities and give an algorithm for the GI problem that runs in time exponential in k.     

Lexicographically minimizing axial motions for the Euclidean TSP

A variant of the Euclidean traveling salesman problem (TSP) is defined and studied. In the three-dimensional space, the objective function is to lexicographically minimize the x-moves, then the y-moves and finally the z-moves. The 2D and 3D cases are first studied and solved as a shortest path problem. Then the approach is generalized to the d-dimensional case.