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 .

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].

Abstract A graph G is a grid intersection graph if G is the intersection graph of ℋ︁ ∪ ℐ, where ℋ︁ and ℐ are, respectively, finite families of horizontal and vertical linear segments in the plane such that no two parallel segments intersect. (This definition implies that every grid intersection graph is bipartite.) The family ℋ︁ ∪ ℐ is a representation of G. As a consequence of a characterization of grid intersection graphs by Kratochvíl, we observe that when a bipartite graph G = (U ∪ W, E) with minimum degree at least two is a grid intersection graph, then there exists a normalized representation of G on the (r × s)‐grid for r = |U| and s = |W|, that is, a representation in which all end points of segments have integer‐valued coordinates belonging to {(x, y) ∈ N × N | 1 ≤ y ≤ r, 1 ≤ x ≤ s} and the representative segment of each vertex lies on a distinct horizontal or vertical line. A natural problem, with potential applications to circuit layout, is the following: among all the possible normalized representations of G, find a representation ℛ such that the sum of the lengths of the segments in ℛ is minimum. In this work we introduce this problem and present a mixed integer programming formulation to solve it. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 187–193 2004