We study robust versions of the uncapacitated lot sizing problem, where the demand is subject to uncertainty. The robust models are guided by three parameters, namely, the total scaled uncertainty budget, the minimum number of periods in which one would like the demand to be protected against uncertainty, and the minimum scaled protection level per … Read more
This paper presents an extensive computational study of simple, but prominent matheuristics (i.e., heuristics that rely on mathematical programming models) to fi nd high quality ship schedules and inventory policies for a class of maritime inventory routing problems. Our computational experiments are performed on a set of the publicly available MIRPLib instances. This class of inventory … Read more
In this paper we present two mixed-integer programming formulations for the curriculum based course timetabling problem (CTT). We show that the formulations contain underlying network structures by dividing the CTT into two separate models and then connect the two models using flow formulation techniques. The first mixed-integer programming formulation is based on an underlying minimum … Read more
Jeroslow and Lowe gave an exact geometric characterization of subsets of $\mathbb{R}^n$ that are projections of mixed-integer linear sets, also known as MILP-representable or MILP-R sets. We give an alternate algebraic characterization by showing that a set is MILP-R {\em if and only if} the set can be described as the intersection of finitely many … Read more
The infinite models in integer programming can be described as the convex hull of some points or as the intersection of half-spaces derived from valid functions. In this paper we study the relationships between these two descriptions. Our results have implications for finite dimensional corner polyhedra. One consequence is that nonnegative continuous functions suffice to … Read more
Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite it’s simplicity portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple … Read more
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of … Read more
SAP’s decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this … Read more
The analysis of infeasible subproblems plays an import role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications obtained by domain propagation that led to infeasibility. The … Read more
We investigate three competing notions that generalize the notion of a facet of finite-dimensional polyhedra to the infinite-dimensional Gomory–Johnson model. These notions were known to coincide for continuous piecewise linear functions with rational breakpoints. We show that two of the notions, extreme functions and facets, coincide for the case of continuous piecewise linear functions, removing … Read more