skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks
Bayesian Networks (BNs) represent conditional probability relations among a set of random variables (nodes) in the form of a directed acyclic graph (DAG), and have found diverse applications in knowledge discovery. We study the problem of learning the sparse DAG structure of a BN from continuous observational data. The central problem can be modeled as a mixed-integer program with an objective function composed of a convex quadratic loss function and a regularization penalty subject to linear constraints. The optimal solution to this mathematical program is known to have desirable statistical properties under certain conditions. However, the state-of-the-art optimization solvers are not able to obtain provably optimal solutions to the existing mathematical formulations for medium-size problems within reasonable computational times. To address this difficulty, we tackle the problem from both computational and statistical perspectives. On the one hand, we propose a concrete early stopping criterion to terminate the branch-and-bound process in order to obtain a near-optimal solution to the mixed-integer program, and establish the consistency of this approximate solution. On the other hand, we improve the existing formulations by replacing the linear “big-M " constraints that represent the relationship between the continuous and binary indicator variables with second-order conic constraints. Our numerical results demonstrate the effectiveness of the proposed approaches.  more » « less
Award ID(s):
2007814
PAR ID:
10522714
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
JMLR
Date Published:
Journal Name:
Journal of machine learning research
Volume:
24
Issue:
322
ISSN:
1532-4435
Page Range / eLocation ID:
1−38
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, IEEE Transactions on Automation Science and Engineering)
    null (Ed.)
    Job shops are an important production environment for low-volume high-variety manufacturing. Its scheduling has recently been formulated as an Integer Linear Programming (ILP) problem to take advantages of popular Mixed-Integer Linear Programming (MILP) methods, e.g., branch-and-cut. When considering a large number of parts, MILP methods may combinatorial difficulties. To address this, a critical but much overlooked issue is formulation tightening. The idea is that if problem constraints can be transformed to directly delineate the problem convex hull in the data preprocessing stage, then a solution can be obtained by using linear programming methods without combinatorial difficulties. The tightening process, however, is fundamentally challenging because of the existence of integer variables. In this paper, an innovative and systematic approach is established for the first time to tighten the formulations of individual parts, each with multiple operations, in the data preprocessing stage. It is a major advancement of our previous work on problems with binary and continuous variables to integer variables. The idea is to first link integer variables to binary variables by innovatively combining constraints so that the integer variables are uniquely determined by the binary variables. With binary and continuous variables only, it is proved that the vertices of the convex hull can be obtained based on vertices of the linear problem after relaxing binary requirements. These vertices are then converted to tightened constraints for general use. This approach significantly improves our previous results on tightening individual operations. Numerical results demonstrate significant benefits on solution quality and computational efficiency. This approach also applies to other ILP problems with similar characteristics and fundamentally changes the way how such problems are formulated and solved. 
    more » « less
  2. ; ; (, The Astronomical Journal)
    Abstract We propose a novel exact method to solve the probabilistic catalog matching problem faster than previously possible. Our new approach uses mixed integer programming and introduces quadratic constraints to shrink the problem by multiple orders of magnitude. We also provide a method to use a feasible solution to dramatically speed up our algorithm. This gain in performance is dependent on how close to optimal the feasible solution is. Also, we are able to provide good solutions by stopping our mixed integer programming solver early. Using simulated catalogs, we empirically show that our new mixed integer program with quadratic constraints is able to be set up and solved much faster than previous large linear formulations. We also demonstrate our new approach on real-world data from the Hubble Source Catalog. This paper is accompanied by publicly available software to demonstrate the proposed method. 
    more » « less
  3. ; (, IEEE Transactions on Power Systems)
    This letter introduces a novel graph convolutional neural network (GCN) architecture for solving the optimal switching problem in distribution networks while integrating the underlying power flow equations in the learning process. The switching problem is formulated as a mixed-integer second-order cone program (MISOCP), recognized for its computational intensity making it impossible to solve in many real-world cases. Transforming the existing literature, the proposed learning algorithm is augmented with mathematical model information representing physical system constraints both during and post training stages to ensure the feasibility of the rendered decisions. The findings highlight the significant potential of applying predictions from a linearized model to the MISOCP form. 
    more » « less
  4. ; ; ; (, Proceedings of 2021 60th IEEE Conference on Decision and Control (CDC))
    In this paper, we propose a convex optimization approach to chance-constrained drift counteraction optimal control (DCOC) problems for linear systems with additive stochastic disturbances. Chance-constrained DCOC aims to compute an optimal control law to maximize the time duration before the probability of violating a prescribed set of constraints can no longer be maintained to be below a specified risk level. While conventional approaches to this problem involve solving a mixed-integer programming problem, we show that an optimal solution to the problem can also be found by solving a convex second-order cone programming problem without integer variables. We illustrate the application of chance-constrained DCOC to an automotive adaptive cruise control example. 
    more » « less
  5. ; ; ; (, American Control Conference)
    The dynamic response of power grids to small transient events or persistent stochastic disturbances influences their stable operation. This paper studies the effect of topology on the linear time-invariant dynamics of power networks. For a variety of stability metrics, a unified framework based on the H2 -norm of the system is presented. The proposed framework assesses the robustness of power grids to small disturbances and is used to study the optimal placement of new lines on existing networks as well as the design of radial (tree) and meshed (loopy) topologies for new networks. Although the design task can be posed as a mixed-integer semidefinite program (MI-SDP), its performance does not scale well with network size. Using McCormick relaxation, the topology design problem can be reformulated as a mixed-integer linear program (MILP). To improve the computation time, graphical properties are exploited to provide tighter bounds on the continuous optimization variables. Numerical tests on the IEEE 39-bus feeder demonstrate the efficacy of the optimal topology in minimizing disturbances. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email