We introduce the dual-path fixing strategy to exploit dual algorithms for solving relaxations of mixed-integer nonlinear-optimization problems. Such dual algorithms are naturally applied in the context of branch-and-bound, and eventual impact on the success of branch-and-bound is our strong motivation. Our fixing strategy aims to be more powerful than the common strategy of fixing variables based on a single dual-feasible solution (e.g., standard reduced-cost fixing for mixed-integer linear optimization), but to be much faster than "strong fixing", essentially requiring no more time than that of the dual algorithm that we exploit. We have successfully tested our ideas on mixed-integer linear-optimization set-covering instances from the literature, in the context of the dual-simplex method applied to the continuous relaxations.

Abstract The generalized maximum-entropy sampling problem (GMESP) is to select an order- s principal submatrix from an order- n covariance matrix, to maximize the product of its t greatest eigenvalues, $$0 0 < t ≤ s < n . Introduced more than 25 years ago, GMESP is a natural generalization of two fundamental problems in statistical design theory: (i) maximum-entropy sampling problem (MESP); (ii) binary D-optimality (D-Opt). In the general case, it can be motivated by a selection problem in the context of principal component analysis (PCA). We introduce the first convex-optimization based relaxation for GMESP, study its behavior, compare it to an earlier spectral bound, and demonstrate its use in a branch-and-bound scheme. We find that such an approach is practical when $$s-t$$ s - t is very small.

We propose integer-programming formulations for an optimal safety-landing site (SLS) location problem that arises in the design of urban air-transportation networks. We first develop a set-cover based approach for the case where the candidate location set is finite and composed of points, and we link the problems to solvable cases that have been studied. We then use a mixed-integer second-order cone program to model the situation where the locations of SLSs are restricted to convex sets only. Finally, we introduce strong fixing , which we found to be very effective in reducing the size of integer programs.

The generalized maximum-entropy sampling problem (GMESP) is to select an order-s principal submatrix from an order-n covariance matrix, to maximize the product of its t greatest eigenvalues, 0 < t ≤ s < n. It is a problem that specializes to two fundamental problems in statistical design theory: (i) maximum-entropy sampling problem (MESP); (ii) binary D-optimality (D-Opt). In the general case, it is motivated by a selection problem in the context of PCA (principal component analysis). We introduce the first convex-optimization based relaxation for GMESP, study its behavior, compare it to an earlier spectral bound, and demonstrate its use in a branch-and-bound scheme. We find that such an approach is practical when s-t is very small.

We study the D-optimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NP-hard and has no constant-factor polynomial-time approximation algorithm unless P = NP. Therefore, to solve the DDF problem effectively, we propose two convex integer-programming formulations and investigate their corresponding complementary and Lagrangian-dual problems. Leveraging the concavity of the objective functions in the two proposed convex integer-programming formulations, we design an exact algorithm, aimed at solving the DDF problem to optimality. We further derive a family of submodular valid inequalities and optimality cuts, which can significantly enhance the algorithm performance. We also develop scalable randomized-sampling and local-search algorithms with provable performance guarantees. Finally, we test our algorithms using real-world data on the new phasor-measurement-units placement problem for modern power grids, considering the existing conventional sensors. Our numerical study demonstrates the efficiency of our exact algorithm and the scalability and high-quality outputs of our approximation algorithms. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: Y. Li and W. Xie were supported in part by Division of Civil, Mechanical and Manufacturing Innovation [Grant 2046414] and Division of Computing and Communication Foundations [Grant 2246417]. J. Lee was supported in part by Air Force Office of Scientific Research [Grants FA9550-19-1-0175 and FA9550-22-1-0172]. M. Fampa was supported in part by Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 305444/2019-0 and 434683/2018-3]. F. Qiu and R. Yao were supported in part by the U.S. Department of Energy Advanced Grid Modeling Program under [Grant DE-OE0000875]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.0235 .

Abstract. The investigation of combinatorial diameters of polyhedra is a classical topic in linear programming due to its connection with the possibility of an efficient pivot rule for the simplex method. We are interested in the diameters of polyhedra formed from the so-called parallel or series connection of oriented matroids. Oriented matroids are the natural way to connect representable matroid theory with the combinatorics of linear programming, and these connections are fundamental operations for the construction of more complicated matroids from elementary matroid blocks. We prove that, for polyhedra whose combinatorial diameter satisfies the Hirsch-conjecture bound regardless of the right-hand sides in a standard-form description, the diameters of their parallel or series connections remain small in the Hirsch-conjecture bound. These results are a substantial step toward devising a diameter bound for all polyhedra defined through totally unimodular matrices based on Seymour’s famous decomposition theorem. Our proof techniques and results exhibit a number of interesting features. While the parallel connection leads to a bound that adds just a constant, for the series connection one has to linearly take into account the maximal value in a specific coordinate of any vertex. Our proofs also require a careful treatment of non-revisiting edge walks in degenerate polyhedra as well as the construction of edge walks that may take a “detour" to facets that satisfy the non-revisiting conjecture when the underlying polyhedron may not.

Based on a factorization of an input covariance matrix, we define a mild generalization of an upper bound of Nikolov and of Li and Xie for the NP-hard constrained maximum-entropy sampling problem ( CMESP ). We demonstrate that this factorization bound is invariant under scaling and independent of the particular factorization chosen. We give a variable-fixing methodology that could be used in a branch-and-bound scheme based on the factorization bound for exact solution of CMESP , and we demonstrate that its ability to fix is independent of the factorization chosen. We report on successful experiments with a commercial nonlinear programming solver. We further demonstrate that the known “mixing” technique can be successfully used to combine the factorization bound with the factorization bound of the complementary CMESP and with the “linx bound” of Anstreicher. History: Andrea Lodi, area editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 305444/2019-0 and 434683/2018-3] and the Air Force Office of Scientific Research [Grant A9550-19-1-0175].

We study a class of bilevel integer programs with second-order cone constraints at the upper level and a convex quadratic objective and linear constraints at the lower level. We develop disjunctive cuts to separate bilevel infeasible points using a second-order-cone-based cut-generating procedure. To the best of our knowledge, this is the first time disjunctive cuts are studied in the context of discrete bilevel optimization. Using these disjunctive cuts, we establish a branch-and-cut algorithm for the problem class we study, and a cutting plane method for the problem variant with only binary variables. We present a preliminary computational study on instances with no second-order cone constraints at the upper level and a single linear constraint at the lower level. Our study demonstrates that both our approaches outperform a state-of-the-art generic solver for mixed-integer bilevel linear programs that is able to solve a linearized version of our test instances, where the non-linearities are linearized in a McCormick fashion.

The NP-hard maximum-entropy sampling problem (MESP) seeks a maximum (log-)determinant principal submatrix, of a given order, from a positive-semidefinite input matrix C. We give an efficient dynamic-programming algorithm for MESP when C (or its inverse) is tridiagonal. A mask M for MESP is a correlation matrix with which we pre-process C, by taking the Hadamard product M ◦C. Upper bounds on MESP with M ◦C give upper bounds on MESP with C. Most upper-bounding methods are much faster to apply, when the input matrix is tridiagonal, so we consider tridiagonal masks M (which yield tridiagonal M ◦ C). We analyze such tridiagonal masks, and develop a combinatorial local-search based upper-bounding method that takes advantage of fast computations on tridiagonal matrices.

A lower bound for a finite-scenario-based chance-constrained program is the quantile value corresponding to the sorted optimal objective values of scenario subproblems. This quantile bound can be improved by grouping subsets of scenarios at the expense of solving larger subproblems. The quality of the bound depends on how the scenarios are grouped. In this paper, we formulate a mixed-integer bilevel program that optimally groups scenarios to tighten the quantile bounds. For general chance-constrained programs, we propose a branch-and-cut algorithm to optimize the bilevel program, and for chance-constrained linear programs, a mixed-integer linear-programming reformulation is derived. We also propose several heuristics for grouping similar or dissimilar scenarios. Our computational results demonstrate that optimal grouping bounds are much tighter than heuristic bounds, resulting in smaller root-node gaps and better performance of scenario decomposition for solving chance-constrained 0-1 programs. Also, the optimal grouping bounds can be greatly strengthened using larger group size. Summary of Contribution: Chance-constrained programs are in general NP-hard but widely used in practice for lowering the risk of undesirable outcomes during decision making under uncertainty. Assuming finite scenarios of uncertain parameter, chance-constrained programs can be reformulated as mixed-integer linear programs with binary variables representing whether or not the constraints are satisfied in corresponding scenarios. A useful quantile bound for solving chance-constrained programs can be improved by grouping subsets of scenarios at the expense of solving larger subproblems. In this paper, we develop algorithms for optimally and heuristically grouping scenarios to tighten the quantile bounds. We aim to improve both the computation and solution quality of a variety of chance-constrained programs formulated for different Operations Research problems.

We consider the classical matroid matching problem. Unweighted matroid matching for linearly represented matroids was solved by Lovász, and the problem is known to be intractable for general matroids. We present a polynomial-time approximation scheme for unweighted matroid matching for general matroids. In contrast, we show that natural linear-programming relaxations that have been studied have an $\Omega(n)$ integrality gap, and, moreover, $\Omega(n)$ rounds of the Sherali--Adams hierarchy are necessary to bring the gap down to a constant. More generally, for any fixed $k \geq 2$ and $\epsilon>0$, we obtain a $(k/2+\epsilon)$-approximation for matroid matching in $k$-uniform hypergraphs, also known as the matroid $k$-parity problem. As a consequence, we obtain a $(k/2+\epsilon)$-approximation for the problem of finding the maximum-cardinality set in the intersection of $k$ matroids. We also give a $3/2$-approximation for the weighted version of a special case of matroid matching, the matchoid problem.

We consider the classical matroid matching problem. Unweighted matroid matching for linear matroids was solved by Lovasz, and the problem is known to be intractable for general matroids. We present a PTAS for unweighted matroid matching for general matroids. In contrast, we show that natural LP relaxations have an Ω(n) integrality gap and moreover, Ω(n) rounds of the Sherali-Adams hierarchy are necessary to bring the gap down to a constant. More generally, for any fixed k>=2 and ε>0, we obtain a (k/2+ε)-approximation for matroid matching in k-uniform hypergraphs, also known as the matroid k-parity problem. As a consequence, we obtain a (k/2+ε)-approximation for the problem of finding the maximum-cardinality set in the intersection of k matroids. We have also designed a 3/2-approximation for the weighted version of a special case of matroid matching, the matchoid problem.

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any nonnegative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for nonmonotone submodular functions. In particular, for any constant k, we present a $(\frac{1}{k+2+\frac{1}{k}+\epsilon})$-approximation for the submodular maximization problem under k matroid constraints, and a $(\frac{1}{5}-\epsilon)$-approximation algorithm for this problem subject to k knapsack constraints ($\epsilon>0$ is any constant). We improve the approximation guarantee of our algorithm to $\frac{1}{k+1+\frac{1}{k-1}+\epsilon}$ for $k\geq2$ partition matroid constraints. This idea also gives a $(\frac{1}{k+\epsilon})$-approximation for maximizing a monotone submodular function subject to $k\geq2$ partition matroids, which is an improvement over the previously best known guarantee of $\frac{1}{k+1}$.

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any non-negative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for non-monotone submodular functions. In particular, for any constant k, we present a (1/k+2+1/k+ε)-approximation for the submodular maximization problem under k matroid constraints, and a (1/5-ε)-approximation algorithm for this problem subject to k knapsack constraints (ε>0 is any constant). We improve the approximation guarantee of our algorithm to 1/k+1+{1/k-1}+ε for k≥2 partition matroid constraints. This idea also gives a ({1/k+ε)-approximation for maximizing a monotone submodular function subject to k≥2 partition matroids, which improves over the previously best known guarantee of 1/k+1.

We consider optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide an efficient algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r depends only on certain Frobenius numbers of the individual weights and is independent of the size of the ground set. In contrast, we show that finding an optimal (0-best) solution requires exponential time.

Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over K. In this paper, we investigate an algorithm aimed at proving combinatorial infeasibility based on the observed low degree of Hilbert's Nullstellensatz certificates for polynomial systems arising in combinatorics and on large-scale linear-algebra computations over K. We report on experiments based on the problem of proving the non-3-colorability of graphs. We successfully solved graph problem instances having thousands of nodes and tens of thousands of edges.

We study the problem of optimizing nonlinear objective functions over matroids presented by oracles or explicitly. Such functions can be interpreted as the balancing of multicriteria optimization. We provide a combinatorial polynomial time algorithm for arbitrary oracle-presented matroids, that makes repeated use of matroid intersection and an algebraic algorithm for vectorial matroids. Our work is partly motivated by applications to minimum-aberration model-fitting in experimental design in statistics, which we discuss and demonstrate in detail.

We further develop the 0/1 ILP formulation of Lee for edge coloring where colors are encoded in binary. With respect to that formulation, our main contributions are (i) an efficient separation algorithm for general block inequalities, (ii) an efficient LP-based separation algorithm for stars (i.e., the all-different polytope), (iii) an introduction of matching inequalities, (iv) an introduction of switched path inequalities and their efficient separation, (v) a complete description for paths, and (vi) the promising computational results.

The task of evaluating and ranking items with multiple-attributes appears in many guises in commerce. Examples include evaluating responses to a request for quotes (RFQ) for some item and comparison shopping for an item within one or more catalogs. This task is straightforward if the value of the item can be explicitly specified by the evaluator as a function of the attribute values. However, a typical evaluator may not be able to provide the value function in explicit form. In contrast, it is intuitive for them to compare, say, two items and pick the preferable one based on all of the relevant attributes. In this paper we present a method, Q-Eval, that queries the evaluator with selected pairs of items and uses the responses to build a preference model for the evaluator. This model is then used to rank the items in order of the inferred preference. The evaluator can then pick the winning item or items by considering only the top few items in this ranked list. This should result in significant productivity improvement for the evaluator when the number of items to choose from is large. Our algorithm is novel in the way it attempts to derive a stable preference model with only a small number of user queries. This paper describes the algorithm and presents experimental results with real-life data to validate the approach.

Abstract Motivated by the NP‐hard problem of finding a minimum‐weight balanced bipartition of an edge‐weighted complete graph, we studied the class of graphs having the same degrees as bipartite Turán graphs. In particular, we established a maximal set of linear equations satisfied by the counts of the possible incidences of 3‐ and 4‐cycles on such graphs. This leads to extremal results that we exploit in a heuristic for the partitioning problem, as well as in the computation of a Lagrangian bound. Preliminary computational results with the heuristic appear to be quite promising. Further results are established linking various adjacency concepts and measures of nonbipartiteness for such graphs. We also demonstrate the potential power of the Lagrangian bound via a family of examples. © 1994 by John Wiley & Sons, Inc.

Matroid theory provides a set of modeling tools with which many combinatorial and algebraic problems may be treated. Generic algorithms for the resulting matroid problems can be used to solve problems from a variety of application areas including engineering, scheduling, mathematics, and mathematical programming. In this paper, we give an introduction to matroid theory and algorithms, and a survey of algorithmic applications. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.