Motivated by mixed-integer, nonlinear optimization problems, we derive linear inequality characterizations for sets of the form conv{(x, q ) \in R^d × R : q \in Q(x), x \in R^d – int(P )} where Q is convex and differentiable and P \subset R^d . We show that in several cases our characterization leads to polynomial-time … Read more
Research on due date oriented objectives in the parallel machine environment is at best scarce compared to objectives such as minimizing the makespan or the completion time related performance measures. Moreover, almost all existing work in this area is focused on the identical parallel machine environment. In this study, we leverage on our previous work … Read more
This research presents a very efficient method of solving a broad class of large-scale capacitated resource management problems by introducing a new formulation and decomposition. A heuristic called Likelihood of Assignment is utilized not only to find high quality initial integer feasible solutions, but also to guide the Branch-and-Price (B&P) Algorithm towards stabilization. Although Column … Read more
The $pq$-relaxation for the pooling problem can be constructed by applying McCormick envelopes for each of the bilinear terms appearing in the so-called $pq$-formulation of the pooling problem. This relaxation can be strengthened by using piecewise-linear functions that over- and under-estimate each bilinear term. The resulting relaxation can be written as a mixed integer linear … Read more
We consider models of two-stage stochastic programming with a quantile second stage criterion and optimization models with a chance constraint on the second stage objective function values. Such models allow to formalize requirements to reliability and safety of the system under consideration, and to optimize the system in extreme conditions. We suggest a method of … Read more
In this paper, we consider mixed integer linear programming (MIP) formulations for piecewise linear functions (PLFs) that are evaluated when an indicator variable is turned on. We describe modifications to standard MIP formulations for PLFs with desirable theoretical properties and superior computational performance in this context. Citation Technical Report #1788, Computer Sciences Department, University of … Read more
We suggest a method for equivalent transformation of a quantile optimization problem with discrete distribution of random parameters to mixed integer programming problems. The number of additional integer (in fact boolean) variables in the equivalent problems equals to the number of possible scenarios for random data. The obtained mixed integer problems are solved by standard … Read more
We study a variant of the classical transportation problem in which suppliers with limited capacities have a choice of which demands (markets) to satisfy. We refer to this problem as the transportation problem with market choice (TPMC). While the classical transportation problem is known to be strongly polynomial-time solvable, we show that its market choice … Read more
The standard way to represent a choice between n alternatives in Mixed Integer Programming is through n binary variables that add up to one. Unfortunately, this approach commonly leads to unbalanced branch-and-bound trees and diminished solver performance. In this paper, we present an encoding formulation framework that encompasses and expands existing approaches to mitigate this … Read more
We compare the relative strength of valid inequalities for the integer hull of the feasible region of mixed integer linear programs with two equality constraints, two unrestricted integer variables and any number of nonnegative continuous variables. In particular, we prove that the closure of Type~2 triangle (resp. Type~3 triangle; quadrilateral) inequalities, are all within a … Read more