Thomas Kalinowski We study cyclic binary strings with bounds on the lengths of the intervals of consecutive ones and zeros. This is motivated by scheduling problems where such binary strings can be used to represent the state (on/off) of a machine. In this context the bounds correspond to minimum and maximum lengths of on- or off-intervals, and … Read more
We consider the problem of characterizing the convex hull of the graph of a bilinear function $f$ on the $n$-dimensional unit cube $[0,1]^n$. Extended formulations for this convex hull are obtained by taking subsets of the facets of the Boolean Quadric Polytope (BQP). Extending existing results, we propose the systematic study of properties of $f$ … Read more
Answering a question of Haugland, we show that the pooling problem with one pool and a bounded number of inputs can be solved in polynomial time by solving a polynomial number of linear programs of polynomial size. We also give an overview of known complexity results and remaining open problems to further characterize the border … Read more
The pooling problem is a nonconvex nonlinear programming problem (NLP) with applications in the refining and petrochemical industries, but also the coal mining industry. The problem can be stated as follows: given a set of raw material suppliers (inputs) and qualities of the supplies, find a cost-minimising way of blending these raw materials in intermediate … Read more
Iron ore and coal are substantial contributors to Australia’s export economy. Both are blended products that are made-to-order according to customers’ desired product qualities. Mining companies have a great interest in meeting these target qualities since deviations generally result in contractually agreed penalties. This paper studies a variation of the generalized pooling problem (GPP) arising … Read more
The pooling problem is a nonconvex nonlinear programming problem with numerous applications. The nonlinearities of the problem arise from bilinear constraints that capture the blending of raw materials. Bilinear constraints are well-studied and significant progress has been made in solving large instances of the pooling problem to global optimality. This is due in no small … Read more
We study a number of variants of an abstract scheduling problem inspired by the scheduling of reclaimers in the stockyard of a coal export terminal. We analyze the complexity of each of the variants, providing complexity proofs for some and polynomial algorithms for others. For one, especially interesting variant, we also develop a constant factor … Read more
We study an incremental network design problem, where in each time period of the planning horizon an arc can be added to the network and a maximum flow problem is solved, and where the objective is to maximize the cumulative flow over the entire planning horizon. After presenting two mixed integer programming (MIP) formulations for … Read more
We introduce a class of incremental network design problems focused on investigating the optimal choice and timing of network expansions. We concentrate on an incremental network design problem with shortest paths. We investigate structural properties of optimal solutions, we show that the simplest variant is NP-hard, we analyze the worst-case performance of natural greedy heuristics, … Read more