Given an undirected graph, the Vertex Coloring Problem (VCP) consists of assigning a color to each vertex of the graph in such a way that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR based Branch and Bound (DSATUR) is an effective exact algorithm for the … Read more
This paper considers the risk-constrained stochastic traveling salesman problem with random arc costs. In the context of stochastic arc costs, the deterministic traveling salesman problem’s optimal solutions would be ineffective because the selected route might be exposed to a greater risk where the actual cost can exceed the resource limit in extreme scenarios. We present … Read more
In this paper, we prove that the sequential pairing cut-generating procedure of Guan et al. (2007) generalizes a special case of the mingled continuous multi-mixing cut-generating procedure. CitationTechnical Report – MB2, Northwestern University, 10/2015
As the modern transmission control and relay technologies evolve, transmission line switching has become an important option in power system operators’ toolkits to reduce operational cost and improve system reliability. Most recent research has relied on the DC approximation of the power flow model in the optimal transmission switching problem. However, it is known that … Read more
The vertex cover polytopes of graphs do not admit polynomial-size extended formulations. This motivates the search for polyhedral analogues to approximation algorithms and fixed-parameter tractable (FPT) algorithms. While the polyhedral approximability of vertex cover has been studied, we know of no extended formulations parameterized by the size of the vertex cover. To this end, we … Read more
We consider the problem of identifying the solution(s) to an optimization problem whose domain is a subset of the integer lattice, and whose objective and constraint functions can only be observed using a stochastic simulation. Such problems seem particularly prevalent (see www.simopt.org) within service systems having capacity or service-level constraints. We present cgR-SPLINE — a … Read more
In this paper, we analyze the strength of split cuts in a lift-and-project framework. We first observe that the Lovasz-Schrijver and Sherali-Adams lift-and-project operator hierarchies can be viewed as applying specific 0-1 split cuts to an appropriate extended formulation and demonstrate how to strengthen these hierarchies using additional split cuts. More precisely, we define a … Read more
Scheduling elective surgeries is a complicated task due to the coupled effect of multiple sources of uncertainty and the impact of the proposed schedule on the downstream units. In this paper, we propose an adaptive robust optimization model to address the existing uncertainty in surgery duration and length-of-stay in the surgical intensive care unit. The … Read more
We study the polyhedron of the unit commitment problem, and consider a relaxation involving the ramping constraints. We study the three-period ramp-up polytope, and describe the convex-hull using a new class of inequalities. Citation[1] J. Ostrowski, M. F. Anjos, and A. Vannelli, \Tight mixed integer linear programming formulations for the unit commitment problem,” Power Systems, … Read more
We study two-stage stochastic mixed integer programs (TSS-MIPs) with integer variables in the second stage. We show that under suitable conditions, the second stage MIPs can be convexified by adding parametric cuts a priori. As special cases, we extend the results of Miller and Wolsey (Math Program 98(1):73-88, 2003) to TSS-MIPs. Furthermore, we consider second … Read more