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.

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.