We prove that any mixed-integer linear extended formulation for the matching polytope of the complete graph on $n$ vertices, with a polynomial number of constraints, requires $\Omega(\sqrt{\sfrac{n}{\log n}})$ many integer variables. By known reductions, this result extends to the traveling salesman polytope. This lower bound has various implications regarding the existence of small mixed-integer mathematical … Read more
We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization problem. We extend our prior work on disjunctive conic cuts, which has thus far been restricted to the case in which the intersection of the hyperplanes and … Read more
We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the … Read more
We propose a decomposition based method for solving mixed-integer nonlinear optimization problems with “black-box” nonlinearities, where the latter, e.g., may arise due to differential equations or expensive simulation runs. The method alternatingly solves a mixed-integer linear master problem and a separation problem for iteratively refining the mixed-integer linear relaxation of the nonlinearity. We prove that … Read more
The essential structure of the mixed–integer programming formulation for chance–constrained program (CCP) is the intersection of multiple mixing sets with a $0-1$ knapsack. To improve our computational capacity on CCP, an underlying substructure, the (single) mixing set with a $0-1$ knapsack, has received substantial attentions recently. In this study, we consider a CCP problem with … Read more
Aircraft Landing Problem is to assign an airport’s runways to the arrival aircraft as well as to schedule the landing time of these aircraft. In this paper, due to the complexity of the problem, which is NP-hard, we develop an iterative-based heuristic by exploiting special characteristics of the problem. Computational results show the developed approach … Read more
We present an approach to parallelize generation of feasible solutions of mixed integer linear programs in distributed memory high performance computing environments. The approach combines a parallel framework with feasibility pump (FP) as the rounding heuristic. The proposed approach runs multiple FP instances with different starting so- lutions concurrently, while allowing them to share information. … Read more
Facial reduction heuristics are developed in the interest of added performance and reliability in methods for mixed-integer conic optimization. Specifically, the process of branch-and-bound is shown to spawn subproblems for which the conic relaxations are difficult to solve, and the objective bounds of linear relaxations are arbitrarily weak. While facial reduction algorithms already exist to … Read more
In this paper we address the problem of visualizing the proportions and the similarities attached to a set of individuals. We represent this information using a rectangular map, i.e., a subdivision of a rectangle into rectangular portions so that each portion is associated with one individual, their areas reflect the proportions, and the closeness between … Read more
Emergency care necessitates adequate and timely treatment, which has unfortunately been compromised by crowding in many emergency departments (EDs). To address this issue, we study patient scheduling in EDs so that mandatory targets imposed on each patient’s door-to-provider time and length of stay can be collectively met with the largest probability. Exploiting patient flow data … Read more