While mixed-integer linear programming and convex programming solvers have advanced significantly over the past several decades, solution technologies for general mixed-integer nonlinear programs (MINLPs) have yet to reach the same level of maturity.  Various problem structures across different application domains remain challenging to model and solve using modern global solvers, primarily due to the lack of efficient parsers and convexification routines for their complex algebraic representations. In this paper, we introduce a novel graphical framework for globally solving MINLPs based on decision diagrams (DDs), which enable the modeling of complex problem structures that are intractable for conventional solution techniques. We describe the core components of this framework, including a graphical reformulation of MINLP constraints, convexification techniques derived from the constructed graphs, efficient cutting plane methods to generate linear outer approximations, and a spatial branch-and-bound scheme with convergence guarantees.  In addition to providing a global solution method for tackling challenging MINLPs, our framework addresses a longstanding gap in the DD literature by developing a general-purpose DD-based approach for solving general MINLPs. To demonstrate its capabilities, we apply our framework to solve instances from one of the most difficult classes of unsolved test problems in the MINLP Library, which are otherwise inadmissible for state-of-the-art global solvers.

Bilinear constraints in conjunction with network models appear in various mixed-integer and nonlinear programming applications, including the fixed-charge network flow problems, network interdiction problems, and network models with complementarity constraints, such as transportation problems with conflicts. The standard method to convexify these bilinear terms is to linear them using McCormick bounds over a box domain. While these relaxations provide the convex hull of the bilinear constraint over a box domain, they often lead to weak relaxations when the variables domain becomes more complicated as in general polyhedra. In this work, we propose a systematic procedure to convexify these bilinear terms over the entire network constraints, which leads to stronger relaxations that those obtained from classical linearization methods. We present computational experiments to evaluate the performance of the developed framework in terms of both solution quality and time compared to the alternative approaches. 

Despite successful performance of Decision Diagrams (DDs) in solving discrete optimization problems, their extension to directly model mixed integer programs (MIPs) has been lacking in the literature. In this paper, we propose a geometric decomposition technique based on rectangular formations that provide necessary and sufficient conditions for a general MIP to be DD-representable. We develop a specialized Benders decomposition technique through which any bounded mixed integer linear program can be represented by DDs. Such DDs contain layers for both integer and continuous variables. As an evidence of practicality, we apply this framework to design a novel solution methodology for unit commitment problems in energy applications. Promising computational experiments show the potential of this framework in solving a variety of MIPs appearing in the electric grid market.

Decision Diagrams (DDs) have arisen as a powerful tool to solve discrete optimization problems. The extension of this emerging concept to continuous problems, however, has remained a challenge, posing a limitation on its applicability scope. In this paper, we introduce a novel framework that utilizes DDs to model continuous nonlinear programs. This framework, when combined with the array of techniques available for discrete problems, illuminates a new pathway to solving mixed integer nonlinear programs with the help of DDs.

As an alternative to the traditional solution techniques, Decision Diagrams represent discrete optimization problems in the form of a graph. Exploiting graphical structures and properties of such a representation leads to a new paradigm to solve certain integer programs more efficiently. We expand on the strength of this approach by presenting a systematic framework that applies to nonlinear discrete optimization problems with general structure. This framework generates cutting planes that can be used in an outer approximation scheme. Computational experiments show that our algorithms outperform state-of-the-art global solvers in both solution time and gap reduction.

Bilinear expressions formed by the product of two variables appear in various applications including network interdiction. Convex relaxations of bilinear terms play an important role in the effectiveness of solution approaches. In this paper, we develop a constructive convexification technique for bipartite bilinear functions over polyhedral structures. This framework generalizes various techniques in the literature. When applied to the network interdiction application, our method yields a convexification algorithm based on the characterization of paths and cycles of the underlying network. Computational experiments show that such algorithm reduces the solution time by orders of magnitude when compared to the state-of-art solvers.

Optimization problems with norm-bounding constraints arise in a variety of applications, including portfolio optimization, machine learning, and feature selection. A common approach to these problems involves relaxing the norm constraint via Lagrangian relaxation, transforming it into a regularization term in the objective function. A particularly challenging class includes the zero-norm function, which promotes sparsity in statistical parameter estimation. Most existing exact methods for solving these problems introduce binary variables and artificial bounds to reformulate them as higher-dimensional mixed-integer programs, solvable by standard solvers. Other exact approaches exploit specific structural properties of the objective, making them difficult to generalize across different problem types. Alternative methods employ nonconvex penalties with favorable statistical characteristics, but these are typically addressed using heuristic or local optimization techniques due to their structural complexity. In this paper, we propose a novel graph-based method to globally solve optimization problems involving generalized norm-bounding constraints. Our approach encompasses standard $\ell_p$-norms for $p \in [0, \infty)$ and nonconvex penalties such as SCAD and MCP. We leverage decision diagrams to construct strong convex relaxations directly in the original variable space, eliminating the need for auxiliary variables or artificial bounds. Integrated into a spatial branch-and-cut framework, our method guarantees convergence to the global optimum. We demonstrate its effectiveness through preliminary computational experiments on benchmark sparse linear regression problems involving complex nonconvex penalties, which are not tractable using existing global optimization techniques. 

Solving cut-generating linear programs (CGLPs) at each node of the branch-and-bound tree can be computationally prohibitive. We propose a novel function approximation technique based on machine learning to find an estimate for the optimal value of the CGLP, which is the determinant of whether or not a cut can be produced. We establish a systematic framework to efficiently generate train data and use data classification to approximate the indicator function of the CGLP. Computational experiments show a high accuracy rate with a significantly smaller running time for the proposed framework compared to traditional approaches. 

Consider a Bayesian stochastic program where uncertain elements appear in the objective function with a given likelihood distribution and a prior distribution for some parameters of the likelihood. Two natural approaches to solve such a problem are proposed. (i) A Bayesian estimator for the unknown parameters are used independently of the optimization problem, and then the optimization problem is solved separately. (ii) The estimation and optimization problems are solved simultaneously by taking double expectations for both the likelihood and prior distributions. We study the strengths and weaknesses of each of these two methods. We show computational experiments for applications in finance, geometric, piecewise linear and neural network problems.

In 1956, Charles Stein stunned the Statistics world by showing that the sample mean with all its desirable properties is not an admissible estimator of the mean parameter of a normal distribution when it comes to the quality of the risk under the quadratic loss. This phenomenon, later referred to as Stein's paradox, states that one can shrink the sample mean toward any arbitrary vector and yet uniformly dominate the risk associated with the sample mean. We adapt this phenomenon for stochastic optimization problems where the goal is to find an estimator for the solution of the stochastic program with uncertain elements in the objective function. We show that an interesting paradox can also be observed in quadratic stochastic programs of different forms.

Unsplittable network flow problems appear in railroad applications where the flow of the incoming and outgoing arcs at certain nodes of the network cannot be split or merged. This requirement is often modeled through a set of combinatorial constraints that make the underlying network problem challenging for modern solvers. We introduce a novel framework based on the concept of decision diagrams to model the unsplittable flow requirement through a graphical structure that allows for application of a specialized decomposition method. We show, both theoretically and computationally, that the resulting framework yields an optimal solution in a much shorter time compared to the existing methods and state-of-the-art solvers.

We develop the concept of consistency for integer programs through the lens of cutting planes. We emphasize on the complementary role of cutting planes in reducing backtracking in the branch-and-bound search, rather than its primary role of tightening relaxations to improve dual bounds. We show various properties of such a perspective and illustrate connections between consistency and fundamental integer programming notions such as convex hull. We design algorithms to achieve different forms of consistency and show their potential through preliminary computational experiments.

In unit train scheduling problem, some stations do not have necessary equipment or man power to split or merge incoming train formations. In other words, each incoming flow must be routed through an outgoing flow without being altered. This combinatorial requirement makes the typical network formulation of the train scheduling NP-hard. We derive convex hull description for single-node relaxations of the problem and develop cutting plane techniques that can be separated efficiently. Computational experiments suggest that these cutting planes can reduce the optimality gap significantly as compared to the existing solvers.

In constraint programming, consistency plays a crucial role in reducing the size of the search tree by eliminating backtracking. While the concept of consistency is well-studied in constraint programming community, a dedicated development for integer programming is lacking. We undertake this task by adapting consistency for integer programs, in particular, 0-1 programs. In this work, we establish fundamental definitions and properties of such an adaptation.