Search

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 FROM AUTHOR]

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 […]

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. [ABSTRACT FROM AUTHOR]

De Loera, Jesus A., Raymond Hemmecke, Matthias Koppe. 2013. Algebraic and Geometric Ideas in the Theory of Discrete Optimization. SIAM. This is a very timely book, in light of the [...]