This paper focuses on the cluster description problem where, given a dataset and its partition into clusters, the task is to explain the clusters. We introduce a new approach to explain clusters by constructing a polyhedron around each cluster while minimizing either the complexity of the resulting polyhedra or the number of features used in the description. We formulate the cluster description problem as an integer program and present a column generation approach to search over an exponential number of candidate half-spaces that can be used to build the polyhedra. To deal with large datasets, we introduce a novel grouping scheme that first forms smaller groups of data points and then builds the polyhedra around the grouped data, a strategy which out-performs the common approach of sub-sampling data. Compared to state of the art cluster description algorithms, our approach is able to achieve competitive interpretability with improved description accuracy.

This paper considers the learning of Boolean rules in disjunctive normal form (DNF, OR-of-ANDs, equivalent to decision rule sets) as an interpretable model for classification. An integer program is formulated to optimally trade classification accuracy for rule simplicity. We also consider the fairness setting and extend the formulation to include explicit constraints on two different measures of classification parity: equality of opportunity and equalized odds. Column generation (CG) is used to efficiently search over an exponential number of candidate rules without the need for heuristic rule mining. To handle large data sets, we propose an approximate CG algorithm using randomization. Compared to three recently proposed alternatives, the CG algorithm dominates the accuracy-simplicity trade-off in 8 out of 16 data sets. When maximized for accuracy, CG is competitive with rule learners designed for this purpose, sometimes finding significantly simpler solutions that are no less accurate. Compared to other fair and interpretable classifiers, our method is able to find rule sets that meet stricter notions of fairness with a modest trade-off in accuracy.

We consider the problem of mapping a logical quantum circuit onto a given hardware with limited 2-qubit connectivity. We model this problem as an integer linear program, using a network flow formulation with binary variables that includes the initial allocation of qubits and their routing. We consider several cost functions: an approximation of the fidelity of the circuit, its total depth, and a measure of cross-talk, all of which can be incorporated in the model. Numerical experiments on synthetic data and different hardware topologies indicate that the error rate and depth can be optimized simultaneously without significant loss. We test our algorithm on a large number of quantum volume circuits, optimizing for error rate and depth; our algorithm significantly reduces the number of CNOTs compared to Qiskit’s default transpiler SABRE [ 19 ] and produces circuits that, when executed on hardware, exhibit higher fidelity.

Identifying discrete patterns in binary data is an important dimensionality reduction tool in machine learning and data mining. In this paper, we consider the problem of low-rank binary matrix factorisation (BMF) under Boolean arithmetic. Due to the hardness of this problem, most previous attempts rely on heuristic techniques. We formulate the problem as a mixed integer linear program and use a large scale optimisation technique of column generation to solve it without the need of heuristic pattern mining. Our approach focuses on accuracy and on the provision of optimality guarantees. Experimental results on real world datasets demonstrate that our proposed method is effective at producing highly accurate factorisations and improves on the previously available best known results for 15 out of 24 problem instances.

In modern multilabel classification problems, each data instance belongs to a small number of classes among a large set of classes. In other words, these problems involve learning very sparse binary label vectors. Moreover, in the large-scale problems, the labels typically have certain (unknown) hierarchy. In this paper we exploit the sparsity of label vectors and the hierarchical structure to embed them in low-dimensional space using label groupings. Consequently, we solve the classification problem in a much lower dimensional space and then obtain labels in the original space using an appropriately defined lifting. Our method builds on the work of (Ubaru & Mazumdar, 2017), where the idea of group testing was also explored for multilabel classification. We first present a novel data-dependent grouping approach, where we use a group construction based on a low-rank Nonnegative Matrix Factorization (NMF) of the label matrix of training instances. The construction also allows us, using recent results, to develop a fast prediction algorithm that has a \emph{logarithmic runtime in the number of labels}. We then present a hierarchical partitioning approach that exploits the label hierarchy in large-scale problems to divide the large label space into smaller sub-problems, which can then be solved independently via the grouping approach. Numerical results on many benchmark datasets illustrate that, compared to other popular methods, our proposed methods achieve comparable accuracy with significantly lower computational costs.

This paper considers generalized linear models using rule-based features, also referred to as rule ensembles, for regression and probabilistic classification. Rules facilitate model interpretation while also capturing nonlinear dependences and interactions. Our problem formulation accordingly trades off rule set complexity and prediction accuracy. Column generation is used to optimize over an exponentially large space of rules without pre-generating a large subset of candidates or greedily boosting rules one by one. The column generation subproblem is solved using either integer programming or a heuristic optimizing the same objective. In experiments involving logistic and linear regression, the proposed methods obtain better accuracy-complexity trade-offs than existing rule ensemble algorithms. At one end of the trade-off, the methods are competitive with less interpretable benchmark models.

This paper considers the learning of Boolean rules in either disjunctive normal form (DNF, OR-of-ANDs, equivalent to decision rule sets) or conjunctive normal form (CNF, AND-of-ORs) as an interpretable model for classification. An integer program is formulated to optimally trade classification accuracy for rule simplicity. Column generation (CG) is used to efficiently search over an exponential number of candidate clauses (conjunctions or disjunctions) without the need for heuristic rule mining. This approach also bounds the gap between the selected rule set and the best possible rule set on the training data. To handle large datasets, we propose an approximate CG algorithm using randomization. Compared to three recently proposed alternatives, the CG algorithm dominates the accuracy-simplicity trade-off in 8 out of 16 datasets. When maximized for accuracy, CG is competitive with rule learners designed for this purpose, sometimes finding significantly simpler solutions that are no less accurate.

With stochastic integer programming as the motivating application, we investigate techniques to use integrality constraints to obtain improved cuts within a Benders decomposition algorithm. We compare the effect of using cuts in two ways: (i) cut-and-project, where integrality constraints are used to derive cuts in the extended variable space, and Benders cuts are then used to project the resulting improved relaxation, and (ii) project-and-cut, where integrality constraints are used to derive cuts directly in the Benders reformulation. For the case of split cuts, we demonstrate that although these approaches yield equivalent relaxations when considering a single split disjunction, cut-and-project yields stronger relaxations in general when using multiple split disjunctions. Computational results illustrate that the difference can be very large, and demonstrate that using split cuts within the cut-and-project framework can significantly improve the performance of Benders decomposition.

Federated coalition networks are formed by interconnected nodes belonging to different friendly-but-curious parties cooperating for common objectives. Each party has its policy regarding what information may be accessed by which other parties. Data delivery in coalition networks must provide both confidentiality and robustness. First, data should remain confidential when passing through intermediate nodes belonging to parties not authorized to see its content. Second, data delivery has to be robust against dynamic topology changes caused by frequent node churn and failures. We utilize the technique of linear network coding to transform the original data into multiple coded packets and send them along different paths in a way such that no other party can reconstruct the data. This lightweight approach provides confidentiality and robustness for friendly-but-curious coalitions with much less complexity than cryptography methods. In addition, we formulate an optimization problem to find minimum-cost paths, and use column generation framework to address the huge number of variables. Based on the proposed algorithms, we develop a Robust Confidentiality Preserving (R-CP) data delivery protocol. Our evaluation demonstrates that the proposed method can find the optimum solution in several seconds for networks of a few thousands nodes, and deliver data at a high success rate.

In this paper, we study whether cuts obtained from two simplex tableau rows at a time can strengthen the bounds obtained by Gomory mixed-integer (GMI) cuts based on single tableau rows. We also study whether cross and crooked cross cuts, which generalize split cuts, can be separated in an effective manner for practical mixed-integer programs (MIPs) and can yield a nontrivial improvement over the bounds obtained by split cuts. We give positive answers to both these questions for MIPLIB 3.0 problems. Cross cuts are a special case of the t-branch split cuts studied by Li and Richard [Li Y, Richard J-PP (2008) Cook, Kannan and Schrijvers's example revisited. Discrete Optim. 5:724–734]. Split cuts are 1-branch split cuts, and cross cuts are 2-branch split cuts. Crooked cross cuts were introduced by Dash, Günlük, and Lodi [Dash S, Günlük O, Lodi A (2010) MIR closures of polyhedral sets. Math Programming 121:33–60] and were shown to dominate cross cuts by Dash, Günlük, and Molinaro [Dash S, Günlük O, Molinaro M (2012b) On the relative strength of different generalizations of split cuts. IBM Technical Report RC25326, IBM, Yorktown Heights, NY].

The traveling salesman problem with time windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a given time window. We present an extended formulation for the problem based on partitioning the time windows into subwindows that we call buckets. We present cutting planes for this formulation that are computationally more effective than the ones known in the literature because they exploit the division of the time windows into buckets. To obtain a good partition of the time windows, we propose an iterative linear programming (LP)-based procedure that may produce buckets of different sizes. The LP relaxation of this formulation yields strong lower bounds for the TSPTW and provides a good starting point for our branch-and-cut algorithm. We also present encouraging computational results on hard test problems from the literature, namely, asymmetric instances arising from a practical scheduling application, as well as randomly generated symmetric instances. In particular, we solve a number of previously unsolved benchmark instances.

Loop fusion has been studied extensively, but in a manner isolated from other transformations. This was mainly due to the lack of a powerful intermediate representation for application of compositions of high-level transformations. Fusion presents strong interactions with parallelism and locality. Currently, there exist no models to determine good fusion structures integrated with all components of an auto-parallelizing compiler. This is also one of the reasons why all the benefits of optimization and automatic parallelization of long sequences of loop nests spanning hundreds of lines of code have never been explored.

Two-step mixed integer rounding (MIR) inequalities are valid inequalities derived from a facet of a simple mixed integer set with three variables and one constraint. In this paper we investigate how to effectively use these inequalities as cutting planes for general mixed integer problems. We study the separation problem for single-constraint sets and show that it can be solved in polynomial time when the resulting inequality is required to be sufficiently different from the associated MIR inequalities. We discuss computational issues and present numerical results based on a number of data sets.

Abstract In this paper we study the network design arc set with variable upper bounds. This set appears as a common substructure of many network design problems and is a relaxation of several fundamental mixed‐integer sets studied earlier independently. In particular, the splittable flow arc set, the unsplittable flow arc set, the single node fixed‐charge flow set, and the binary knapsack set are facial restrictions of the network design arc set with variable upper bounds. Here we describe families of strong valid inequalities that cut off all fractional extreme points of the continuous relaxation of the network design arc set with variable upper bounds. Interestingly, some of these inequalities are also new even for the aforementioned restrictions studied earlier. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 17–28 2007

In this paper we present a new bound on the min‐cut max‐flow ratio for multicommodity flow problems with specified demands. For multicommodity flows, this is a generalization of the well‐known relationship between the capacity of a minimum cut and the value of the maximum flow of a single commodity flow problem. For multicommodity flows, capacity of a cut is scaled by the demand that has to cross the cut to obtain the numerator of this ratio. In the denominator, the maximum concurrent flow value is used. Currently, the best known bound for this ratio is proportional to $\log(k)$, where k is the number of origin‐destination pairs with positive demand. Our new bound is proportional to $\log(k^*)$, where $k^*$ is the cardinality of the minimum cardinality vertex cover of the demand graph. To obtain this bound, we start with a so‐called aggregated commodity formulation of the maximum concurrent flow problem with $k^*$ commodities. We also show a similar bound for the maximum multicommodity flow problem. The new bound is proportional to $\min\{\log(k^*), k^{**}\}$, where $k^{**}$ denotes the size of the of the demand graph.

This paper presents algorithms, heuristics and lower bounds for an optimal sharing of network resources among several multicast groups that coexist in the network. Group (i.e., many-to-many) multicasting is a demanding service since any member can become a sender independently from the others. We consider a shared tree as the backbone of a group multicasting session. Considering each multicast session in isolation and independently may cause congestion on some links and reduce network utilization. Thus, we define the multicast packing problem in which the network tries to accommodate simultaneously all the multicast groups while trying to avoid bottlenecks on the links for higher throughput (i.e., minimize the maximum link sharing among multicast groups). Minimization of maximum congestion is achieved at the expense of increasing the size of some multicast trees which in turn impacts the delay. This trade-off is addressed by adding a penalty term to the objective function of the optimal packing formulation. The penalty term is a function of the amount of dilation from the size of the optimal tree obtained for each group multicast independently from the others (i.e., in isolation). Since the mathematical programming formulation for the optimization problem is computationally intractable, we resort to suboptimal solutions with heuristics. Our heuristic method aims to reduce the sharing of a link while ensuring that the size of multicast trees will never exceed /spl alpha/OPT/sup k/ where OPT/sup k/ is the size of the optimum tree for multicast group k in isolation. Optimum multicast tree for each group (in isolation) is computed by using cutting-plane inequalities and the branch-and-cut algorithm. In order to evaluate the performance of our approximation, we derive lower bounds on the problem. Our first lower bound on the maximum congestion is a theoretical one and puts a cap on the following two constructive lower bounds. The lower bounds and the heuristic method are implemented and it is shown that the maximum congestion obtained by the heuristic method is quite close to the constructive lower bounds.

This paper presents algorithms, heuristics and lower bounds addressing optimization issues in many-to-many multicasting. Two main problems are addressed: (1) a precise combinatorial comparison of optimal multicast trees with optimal multicast rings, (2) an optimized sharing of network resources (i.e., nodes and links) among multiple multicast groups that coexist. The former is central to the choice of multicast protocols and their performance, while the latter is crucial for network utilization. The first problem is treated as a comparison of Steiner tree and traveling salesman problems on the same input set. The underlying integer programming problems are solved to optimum by using cutting-plane inequalities and the branch-and-cut algorithm. In addition to these exact solutions, fast heuristics are presented for approximate solutions. The second problem is formulated as a packing problem in which the network tries to accommodate all the multicast groups by optimizing the utilization of resources. Precise mathematical programming formulations, lower bounds and a heuristic for the underlying optimization problem are presented. The heuristic aims to accommodate multiple multicast groups while avoiding bottlenecks on the links for higher throughput. The heuristics and exact algorithms are implemented on various networks and multicast groups. The simulations show that multicast trees can be built by using 25% fewer links than the rings, both for optimal and suboptimal constructions. The packing heuristic is also implemented and its performance is compared to the constructive lower bound.

We study a capacity expansion problem that arises in telecommunication network design. Given a capacitated network and a traffic demand matrix, the objective is to add capacity to the edges, in multiples of various modularities, and route traffic, so that the overall cost is minimized. We study the polyhedral structure of a mixed-integer formulation of the problem and develop a cutting-plane algorithm using facet defining inequalities. The algorithm produces an extended formulation providing both a vary good lower bound and a starting point for branch and bound. The overall algorithm appears effective when applied to problem instances using real-life data.

Abstract We consider a combinatorial problem arising in the design and operation of lightwave networks. Nodes in such networks are equipped with tunable transmitters and receivers and communication occurs when the frequency of some transmitter is the same as that of a receiver. This technology enables us to update the network topology to respond to changes in traffic patterns. There are two main optimization problems related to this network structure, one being the design of a target graph more suitable to (future) traffic conditions, and the other being the problem of transforming the current network to this target network. This paper discusses the second problem, i.e., the transition phase when the modifications on the current graph are made through a sequence of intermediate connection networks. In particular, we move from one graph to another by swapping two independent edges in the current graph for two other independent edges not in the current graph, so that the union forms a four‐cycle. We characterize the sequence requiring the minimum number of intermediate graphs together with the necessary and sufficient conditions for the existence of such a sequence. We also develop upper and lower bounds on the length of a shortest sequence by formulating an integer program and solving its continuous relaxation to optimality. We also give an efficient algorithm for the case when the intermediate graphs are required to be connected. © 1994 by John Wiley & Sons, Inc.