We derive a closed form description of the convex hull of mixed-integer bilinear covering set with bounds on the integer variables. This convex hull description is determined by considering some orthogonal disjunctive sets defined in a certain way. This description does not introduce any new variables, but consists of exponentially many inequalities. An extended formulation … Read more
“Interior point algorithms are a good choice for solving pure LPs or QPs, but when you solve MIPs, all you need is a dual simplex.” This is the common conception which disregards that an interior point solution provides some unique structural insight into the problem at hand. In this paper, we will discuss some of … Read more
Many mixed-integer optimization problems are constrained by nonlinear functions that do not possess desirable analytical properties like convexity or factorability or cannot even be evaluated exactly. This is, e.g., the case for problems constrained by differential equations or for models that rely on black-box simulation runs. For these problem classes, we present, analyze, and test … Read more
The multiple Checkpoint Ordering Problem (mCOP) aims to find an optimal arrangement of n one-dimensional departments with given lengths such that the total weighted sum of their distances to m given checkpoints is minimized. In this paper we suggest an integer linear programming (ILP) approach and a dynamic programming (DP) algorithm, which is only exact … Read more
We study disruptions at a major airport. Disruptions could be caused by bad weather, for example. Our study is from the perspective of the airport, the air services provider (such as air traffic control) and the travelling public, rather than from the perspective of a single airline. Disruptions cause flights to be subjected to ground … Read more
The minimum $k$-enclosing ball problem seeks the ball with smallest radius that contains at least $k$ of $m$ given points in a general $n$-dimensional Euclidean space. This problem is NP-hard. We present a branch-and-bound algorithm on the tree of the subsets of $k$ points to solve this problem. The nodes on the tree are ordered … Read more
Christofides and Hadjiconstantinou introduced a dynamic programming state space relaxation for obtaining upper bounds for the Constrained Two-dimensional Guillotine Cutting Problem. The quality of those bounds depend on the chosen item weights, they are adjusted using a subgradient-like algorithm. This paper proposes Algorithm X, a new weight adjusting algorithm based on integer programming that provably … Read more
We present sufficient conditions under which thermal generators can be aggregated in mixed-integer linear programming (MILP) formulations of the unit commitment (UC) problem, while maintaining feasibility and optimality for the original disaggregated problem. Aggregating thermal generators with identical characteristics (e.g., minimum/maximum power output, minimum up/down-time, and cost curves) into a single unit reduces redundancy in … Read more
We propose a nested decomposition scheme for infinite-horizon stochastic linear programs. Our approach can be seen as a provably convergent extension of stochastic dual dynamic programming to the infinite-horizon setting: we explore a sequence of finite-horizon problems of increasing length until we can prove convergence with a given confidence level. The methodology alternates between a … Read more
Demand for healthcare services is growing rapidly in Australia and across the world, and rising healthcare expenditure is increasing pressure on sustainability of government-funded healthcare systems. In Australia, elective surgery waiting lists are growing and hospitals are struggling with a capacity shortage. To keep up with the rising demand, we need to be more efficient … Read more