Browsing by Browse by FOR 2008 "010303 Optimisation"

Shape matrix decomposition is a subproblem in radiation therapy planning. A given fluence matrix A has to be decomposed into a sum of shape matrices corresponding to homogeneous fields that can be shaped by a multileaf collimator (MLC). We solve the problem of minimizing the delivery time for an approximation of A satisfying certain prescribed bounds, under the additional condition that the used MLC requires the interleaf collision constraint.

We investigate how well the graph of a bilinear function 𝑏 : [0,1] ⁿ →R can be approximated by its McCormick relaxation. In particular, we are interested in the smallest number 𝑐 such that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is at most 𝑐 times the difference between the concave and convex envelopes. Answering a question of Luedtke, Namazifar and Linderoth, we show that this factor 𝑐 cannot be bounded by a constant independent of 𝑛. More precisely, we show that for a random bilinear function 𝑏 we have asymptotically almost surely 𝑐 ≥ √𝑛/4. On the other hand, we prove that 𝑐 ≤ 600√𝑛, which improves the linear upper bound proved by Luedtke, Namazifar and Linderoth. In addition, we present an alternative proof for a result of Misener, Smadbeck and Floudas characterizing functions 𝑏 for which the McCormick relaxation is equal to the convex hull.

The use of multileaf collimators (MLCs) is a modern way to realize intensity modulated fields in radiotherapy. An important step in the treatment planning is the shape matrix decomposition: the desired fluence distribution, given by an integer matrix, has to be decomposed into a small number shape matrices, i.e. (0,1)-matrices corresponding to the field shapes that can be delivered by the MLC used. The two main objectives are to minimize the total irradiation time, and the number of shape matrices. Assuming that the entries of the fluence matrix are bounded by a constant, we prove that a shape matrix decomposition with minimal number of shape matrices under the condition that the total irradiation time is minimal, can be determined in time polynomial in the matrix dimensions. The results of our algorithm are compared with Engel’s [K. Engel, A new algorithm for optimal multileaf collimator field segmentation, Discrete Appl. Math. 152 (1–3) (2005) 35–51.] heuristic for the reduction of the number of shape matrices.

Recently, evolutionary algorithms (encompassing genetic algorithms, evolution strategies, and genetic programming) have proven to be the best general method for the optimisation of large, difficult problems, including agricultural models. Differential evolution (DE) is one comparatively simple variant of an evolutionary algorithm. DE has only three or four operational parameters, and can be coded in about 20 lines of pseudo-code. Investigations of its performance in the optimisation of a challenging beef property model with 70 interacting management options (hence a 70-dimensional optimisation problem) indicate that DE performs better than Genial (a real-value genetic algorithm), which has been the preferred operational package thus far. Despite DE’s apparent simplicity, the interacting key evolutionary operators of mutation and recombination are present and effective. In particular, DE has the advantage of incorporating a relatively simple and efficient form of self-adapting mutation. This is one of the main advantages found in evolution strategies, but these methods usually require the burdening overhead of doubling the dimensionality of the search-space to achieve this. DE's processes are illustrated, and model optimisations totaling over two years of Sun workstation computation are presented. These results show that the baseline DE parameters work effectively, but can be improved in two ways. Firstly, the population size does not need to be overly high, and smaller populations can be considerably more efficient; and second, the periodic application of extrapolative mutation may be effective in counteracting the contractive nature of DE's intermediate arithmetic recombination in the latter stages of the optimisations. This provides an escape mechanism to prevent sub-optimal convergence. With its ease of implementation and proven efficiency, DE is ideally suited to both novice and experienced users wishing to optimise their simulation models.

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 pools and outputs so as to satisfy requirements on the output qualities. The blending in two stages (in pools and outputs) introduces bilinear constraints. The pooling problem can alternatively be described as a minimum cost network flow problem with additional bilinear constraints to capture the blending of raw materials. In this paper we study a variation of the pooling problem that arises naturally in the coal mining industry and is sometimes referred to as grade targeting. Coal is made-to-order according to customers’ desired product qualities. Deviations from these target qualities result in contractually agreed bonuses and penalties. In the pooling problem variation we study, costs are associated with these bonuses and penalties instead of network flows. While in the original pooling problem we have hard bounds on the qualities and unmet demand is penalised in the objective function, in our coal mining variation we have hard demand constraints and deviations from target qualities are penalised. This makes finding a feasible solution easy, while in the pooling problem finding a nontrivial feasible solution that satisfies the quality requirements is already hard. An implication of this is that we are able to solve larger problem instances than those typically studied in the pooling problem literature. To model the coal blending process accurately, we define a time-expanded network where the intermediate pools represent coal stockpiles over time. Since coal is transported in large quantities, we study the trade-off between continuous and discretized flows in coal blending, i.e., solving a continuous flow problem where arbitrarily small flows are allowed versus solving a discretized flow problem where flows must be in multiples of some basic unit, e.g. trainloads. We also study two exact mixed-integer linear programming (MILP) linearizations of these mixed-integer nonlinear programs (MINLPs), which can be derived from unary and binary expansions of the flow integrality constraint. Such discretizations are typically studied as approximations to an originally continuous problem, however, in our application, a discretized formulation describes the original problem more accurately than a continuous formulation. The paper is organized as follows. In Section 1.1, we introduce the pooling problem and present a variant of the well-known PQ-formulation. In Section 1.2, we extend the pooling problem to model a simplified coal supply chain. After a short literature review on coal supply chains, we present four different problems: the continuous flow problem (a MINLP), in which arbitrarily small flows are allowed, and three discretized flow problems (a MINLP and two MILPs), in which flows must be in multiples of trainloads. The discretization can be achieved by adding integrality constraints for the flow variables. We then show how to overcome the nonlinearity which is inherent in the pooling problem with the use of unary and binary expansions of the integer flow variables, which yields exact MILP reformulations of the discretized MINLP. We conclude the paper with Section 2 where we provide computational results for the four different problems which we solve for a real-life industry setting.

We consider the problem to decompose a binary matrix into a small number of binary matrices whose 1-entries form a rectangle. We show that the linear relaxation of this problem has an optimal integral solution corresponding to a well known geometric result on the decomposition of rectilinear polygons.

Intensity maps are non-negative matrices describing the intensity modulation of beams in radiotherapy. An important step in the planning process is to determine a segmentation, that is a representation of an intensity map as a positive combination of special matrices corresponding to fixed positions of the multileaf collimator, called segments. We consider the problem of constructing segmentations with small total numbers of monitor units and segments. Generalizing the approach of Engel [Discrete Appl. Math., https://doi.org/10.1016/j.dam.2004.10.007] so that it applies to the segmentation problem with interleaf collision constraint, we show that the minimal number of monitor units in this case can be interpreted as the maximal length of a path in a layered digraph. We derive an efficient algorithm that constructs a segmentation with this minimal number of monitor units, and we propose a heuristic approach to the reduction of the number of segments.

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 a systematic study of properties of f that guarantee that certain classes of BQP facets are sufficient for an extended formulation. We use a modification of Zuckerberg’s geometric method for proving convex hull characterizations (Zuckerberg, 2016) to prove some initial results in this direction. In particular, we provide small-sized extended formulations for bilinear functions whose corresponding graph is either a cycle with arbitrary edge weights or a clique or an almost clique with unit edge weights.

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 this NP-complete problem, we describe several heuristics and prove performance bounds for some special cases. In a series of computational experiments, we compare the performance of the MIP formulations as well as the heuristics.

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, show that the simplest variant is NP-hard, analyze the worst-case performance of natural greedy heuristics, derive a 4-approximation algorithm, and conduct a small computational study.

Australia has a large operational heavy railway network which is approximately 33,355 route-kilometres. This network accounted for approximately 55 percent of all freight transport activity in Australia in the financial year 2013–14, almost 367 billion tonne-kilometres which was up 50 percent from 2011–12 (BITRE (2016)). To provide a safe and reliable railway network to customers, an effective maintenance regime is a key requirement. Planned maintenance and asset renewal in capital intensive industries such as the railway industry, which has expensive infrastructure, is a common and effective maintenance practice. Infrastructure is of essential importance to maintain a reliable customer service. To prevent long unplanned interruptions in the service to customers, a proper maintenance and renewal program is required. The objective is to schedule planned maintenance and asset renewal jobs in such a way that their impact on the capacity that will be provided to customers is minimised while at the same time keeping the infrastructure in good working condition. A proper maintenance and renewal schedule limits the frequency with which disruptive emergency maintenance is needed. We investigate a planned maintenance and asset renewal scheduling problem on a railway corridor with train traffic in both directions. Potential train journeys are represented by train paths, where a train path is specified by a sequence of (location,time)-pairs, and we distinguish between up- and down paths, depending on the direction of travel. Necessary maintenance and renewal activities, or work, are specified by a release time, a deadline, a processing time and a location. Scheduling work at a particular time has the consequence that the train paths passing through the corresponding location while the work is carried out have to be cancelled. An instance of the problem is given by a set of train paths and a set of work activities, and the task is to schedule all the work such that the total number of cancelled paths is minimised. There is a vast literature on scheduling problems and on transportation network problems. However, the interaction of these problems in contexts such as the railway industry have not been studied thoroughly. Boland et al. (2014) study the problem of scheduling maintenance jobs in a network. Each maintenance job causes a loss in the capacity of network while it is being done. The objective is to minimize this loss or equivalently maximize the capacity over time horizon in such a way that all jobs are scheduled. They model the problem as a network flow problem over time. This problem and its variants are investigated in Boland et al. (2013), Boland et al. (2014), Boland et al. (2015), Boland et al. (2016) and Abed et al. (2017). Our work is different from the previous works. The main difference is that we model the capacity by train paths whereas in a network flow model over time the capacity is modelled approximately by flows over time. The primary purpose of this study is to provide further insight into this problem, to characterize the structural properties of optimal solutions, and to use these properties to develop efficient combinatorial and integer programming based solution algorithms. We present theoretical and computational results on the performance of the developed solution approaches.

We consider multistage stochastic programs, in which decisions can adapt over time, (i.e., at each stage), in response to observation of one or more random variables (uncertain parameters). The case that the time at which each observation occurs is decision-dependent, known as stochastic programming with endogeneous observation of uncertainty, presents particular challenges in handling non-anticipativity. Although such stochastic programs can be tackled by using binary variables to model the time at which each endogenous uncertain parameter is observed, the consequent conditional non-anticipativity constraints form a very large class, with cardinality in the order of the square of the number of scenarios. However, depending on the properties of the set of scenarios considered, only very few of these constraints may be required for validity of the model. Here we characterize minimal sufficient sets of non-anticipativity constraints, and prove that their matroid structure enables sets of minimum cardinality to be found efficiently, under general conditions on the structure of the scenario set.

Shape matrix decomposition is a sub-problem in radiation therapy planning. A given fluence matrix 𝐴 has to be written as a sum of shape matrices corresponding to homogeneous fields that can be shaped by a multileaf collimator. We solve the problem of finding an approximation 𝐵 of 𝐴 satisfying prescribed upper and lower bounds for each entry. The approximation 𝐵 is determined such that the corresponding fluence can be realized with a prescribed delivery time using a multileaf collimator with an interleaf collision constraint, and under this condition the distance between 𝐴 and 𝐵 is minimized.

We consider the scheduling of the annual maintenance for the Hunter Valley Coal Chain. The coal chain is a system comprising load points, railway track and different types of terminal equipment, interacting in a complex way. A variety of maintenance tasks have to be performed on all parts of the infrastructure on a regular basis in order to assure the operation of the system as a whole. The main objective in the planning of these maintenance jobs is to maximize the total annual throughput. Based on a network flow model of the system, we propose a mixed integer programming formulation for this planning task. In order to deal with the resulting large scale model which cannot be solved directly by a general purpose solver, we propose two steps. The number of binary variables is reduced by choosing a representative subset of the variables of the original problem, and a rolling horizon approach enables the approximation of the long term (i.e. annual) problem by a sequence of shorter problems (for instance, monthly).

An important method in cancer treatment is the use of high energetic radiation. To kill tumor cells, the patient is exposed to radiation that is delivered by a linear accelerator whose beam head can be rotated about the treatment couch. Inevitably, the healthy tissue surrounding the tumor is also exposed to some radiation. So the problem arises to arrange the treatment such that the tumor receives a sufficiently high uniform dose while the damage to the normal tissue is as small as possible. The standard approach to this problem is as follows. First the patient body is discretized into the so-called voxels. The set of voxels is then partitioned into three sets: the clinical target volume, the critical structures, and the remaining tissue. There are certain dose constraints for each of these parts. Basically, the dose in the target volume has to be sufficient to kill the cancerous cells and the dose in the critical structures must not destroy the functionality of the corresponding organs. The determination of a combination of radiation fields is usually done by inverse methods based on certain physical models of how the radiation passes through a body. In the early 1990s, the method of intensity modulated radiation therapy (IMRT) was developed to obtain additional flexibility. Using a multileaf collimator (MLC) it is possible to form homogeneous fields of different shapes. By superimposing some homogeneous fields an intensity modulated field is delivered. An MLC consists of two banks of metal leaves that block the radiation and can be shifted to form irregularly shaped beams.

In this research, we describe an optimization problem motivated by the need to maintain infrastructure net-works over time. We consider infrastructure networks in which product is transported between distinct origin-destination pairs, and at the same time the infrastructure assets need to be maintained by resources moving in the network. In order to perform maintenance the assets have to be shut down from time to time thus reducing the system capacity for those time periods. The objective is to maximize the total transported product by aligning the maintenance activities appropriately. This problem combines flow maximization with maintenance scheduling capturing some important aspects of the motivating practical problem: (1) the interaction between utilization of network assets such as nodes and arcs and their maintenance demands, (2) the limited resources available to perform the maintenance, and (3) the time for moving the maintenance resources between different locations in the network. Depending on the application context, there are a number of natural ways to reflect these in a mathematical model, and this gives rise to a rich and challenging optimization problem which we call the network maintenance problem. We formally introduce the problem, and present a mixed integer programming formulation. Next, we consider the case of a single commodity and a single maintenance resource when the network is a single path. We describe a polynomial time algorithm which, under some simplifying assumptions, solve the single path case to optimality. The problem becomes more challenging when the simplifying assumptions are dropped.

The network maintenance problem is motivated by the need to maintain infrastructure networks over time. We consider networks in which a commodity is transported between origin-destination pairs, and at the same time the infrastructure assets need to be maintained by resources moving in the network. In order to perform maintenance the assets have to be shut down thus reducing the system capacity. The objective is to maximise the total throughput by aligning the maintenance activities efficiently. In this paper, we study a special case of the network maintenance problem where the network consists of a single arc connecting an origin to a destination. Furthermore, there is no restriction on the amount of repair if the resource is to perform maintenance in a time period.
This problem is of interest for the following reasons. Firstly, it generalises variants of the lot-sizing problem and the warehouse problem, both of which have been well-studied in the literature. Secondly, we hope that understanding this special case will be useful in tackling more general variants of the network maintenance problem.
In this paper, we present a mixed integer linear programming formulation. We then show that a special class of feasible solutions, called Maximum Flow Order Up (MFOU) solutions, contains at least one optimal solution. Based on this result, we introduce an alternative integer linear programming formulation with only five decision variables. As a consequence, the optimal objective function value for any instance of the problem can be obtained in polynomial time.

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 part to reformulations of the problem. Recently, Alfaki and Haugland proposed a multi-commodity flow formulation of the pooling problem based on input commodities. The authors proved that the new formulation has a stronger linear relaxation than previously known formulations. They also provided computational results which show that the new formulation outperforms previously known formulations when used in a global optimization solver. In this paper, we generalize their ideas and propose new multi-commodity flow formulations based on output, input and output and (input, output)-commodities. We prove the equivalence of formulations, and we study the partial order of formulations with respect to the strength of their LP relaxations. In an extensive computational study, we evaluate the performance of the new formulations. We study the trade-off between disaggregating commodities and therefore increasing the size of formulations versus strengthening the relaxed linear programs and improving the computational performance of the nonlinear programs. We provide computational results which show that output commodities often outperform input commodities, and that disaggregating commodities further only marginally strengthens the linear relaxations. In fact, smaller formulations often show a significantly better performance when used in a global optimization solver.

This paper is concerned with computation of the Karcher mean on the unit sphere Sn and the special orthogonal group SO(n). The Karcher mean, or the Riemannian centre of mass, is defined as the point minimising the sum of the squared distances from that point to each of the given points. By its definition, the mean always belongs to the same space as the given points, however, it may not be unique. Motivated by applications in control, vision and robotics, this paper studies the numerical computation of the Karcher mean. We propose simpler and computationally more efficient gradient-like and Newton-like algorithms. We give explicit forms of these algorithms and show that if the set of points lie within a particular open ball, the algorithms are guaranteed to converge to the Karcher mean.

The separation technologies of 3D chromatograms have been researched for a long time to obtain spectra and chromatogram peaks for individual compounds. However, before applying most of the current methods, the number of compounds must be known in advance. Independent Component Analysis (ICA) is applied to separate 3D chromatograms without knowing the compounds' number in advance, but the existence of the noise component in the results makes it complex for computation. In this paper, a parallel model of Independent Component Analysis constrained by a 5-parameter Reference Curve (pICA5pRC) is proposed based on the ICA model. Introducing a priori knowledge from chromatogram peaks, the pICA5pRC model transformed the 3D chromatogram separation problem to a 5 parameters optimization issue. An algorithm named multi-target particle swarm optimization (mPSO) has been developed to solve the pICA5pRC model. Through simulations, the performance and explanation of our method were described. Through experiments, the practicability of our method is validated. The results show that: (1) our method could separate 3D chromatograms efficiently even with severe overlap without knowing the compounds' number in advance; (2) our method extracted chromatogram peaks from the dataset directly without noise components; (3) our method could be applied to the practical HPLC-DAD dataset.

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 between (strongly) NP-hard and polynomially solvable cases of the pooling problem.

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 approximation algorithm.

Multileaf collimators (MLCs) are the prevailing tool for the realization of radiation fields in intensity modulated radiation therapy (IMRT). One step in the treatment planning is to determine a set of leaf positions realizing a certain intensity modulated radiation field. In this paper we suggest two extensions in the use of the MLC that lead to considerable savings in terms of monitor units, thus potentially increasing the treatment quality. We test our method with random and with clinical sample matrices.

We present an algorithm for optimal step-and-shoot multileaf collimator field segmentation minimizing tongue-and-groove effects. Adapting the concepts of [7] we characterize the minimal decomposition time as the maximal weight of a path in a properly constructed weighted digraph. We also show that this decomposition time can be realized by a unidirectional plan, thus proving that the algorithm from [9] is monitor unit optimal in general and not only for unidirectional leaf movement. Our characterization of the minimal decomposition time has the advantage that it can be used to derive a heuristic for the reduction of the number of shape matrices following the ideas of [7]. [7] T. Kalinowski. A duality based algorithm for multileaf collimator field segmentation with interleaf collision constraint. Discrete Appl. Math., 152(1-3):52–88, 2005. [9] S. Kamath, S. Sartaj, J. Palta, S. Ranka, and J. Li. Optimal leaf sequencing with elimination of tongue-and-groove underdosage. Phys. Med. Biol., 49:N7–N19, 2004.

We consider the problem of scheduling a set of maintenance jobs on the arcs of a network so that the total flow over the planning time horizon is maximized. A maintenance job causes an arc outage for its duration, potentially reducing the capacity of the network. The problem can be expected to have applications across a range of network infrastructures critical to modern life. For example, utilities such as water, sewerage and electricity all flow over networks. Products are manufactured and transported via supply chain networks. Such networks need regular, planned maintenance in order to continue to function. However the coordinated timing of maintenance jobs can have a major impact on the network capacity lost due to maintenance. Here we describe the background to the problem, define it, prove it is strongly NP-hard, and derive four local search-based heuristic methods. These methods integrate exact maximum flow solutions within a local search framework. The availability of both primal and dual solvers, and dual information from the maximum flow solver, is exploited to gain efficiency in the algorithms. The performance of the heuristics is evaluated on both randomly generated instances, and on instances derived from real-world data. These are compared with a state-of-the-art integer programming solver.

We study the problem of scheduling maintenance on arcs of a capacitated network so as to maximize the total flow from a source node to a sink node over a set of time periods. Maintenance on an arc shuts down the arc for the duration of the period in which its maintenance is scheduled, making its capacity zero for that period. A set of arcs is designated to have maintenance during the planning period, which will require each to be shut down for exactly one time period. In general this problem is known to be NP-hard, and several special instance classes have been studied. Here we propose an additional constraint which limits the number of maintenance jobs per time period, and we study the impact of this on the complexity.

We consider a problem that marries network flows and scheduling, motivated by the need to schedule maintenance activities in infrastructure networks, such as rail or general logistics networks. Network elements must undergo regular preventive maintenance, shutting down the arc for the duration of the activity. Careful coordination of these arc maintenance jobs can dramatically reduce the impact of such shutdown jobs on the flow carried by the network. Scheduling such jobs between given release dates and deadlines so as to maximize the total flow over time presents an intriguing case to study the role of time discretization. Here we prove that if the problem data is integer, and no flow can be stored at nodes, we can restrict attention to integer job start times. However if flow can be stored, fractional start times may be needed. This makes traditional strong integer programming scheduling models difficult to apply. Here we formulate an exact integer programming model for the continuous time problem, as well as integer programming models based on time discretization that can provide dual bounds, and that can – with minor modifications – also yield primal bounds. The resulting bounds are demonstrated to have small gaps on test instances, and offer a good trade-off for bound quality against computing time.

Rail infrastructure forms a critical part of the mining supply chain in Australia due to the high weight to volume ratio of the product and the long distances between the mines and the ports. Across Australia, rail infrastructure has been steadily expanding to account for the growth in export volumes and the movement of mining operations further inland, and so the efficient and effective management of this critical infrastructure is vitally important. Maintenance plays a crucial role in this management as it ensures that the infrastructure assets are in a condition that allows safe, reliable, and efficient transport. In this paper we consider the annual planning of maintenance for Australia’s largest coal rail network, the Central Queensland Coal Network (CQCN), that is owned, operated, and managed, by Aurizon Holdings Pty Ltd. The current planning approach at Aurizon uses the concept of a maintenance access window (MAW) which provides a train-free time window across geographically contiguous track locations that define a maintenance zone. These train-free time windows facilitate the scheduling of specific maintenance tasks at specific track locations within zones closer to day of operation and forms the basis for a planning framework. A MIP model is introduced which facilitates the planning of different maintenance resources across this network to schedule MAWs. The model takes into account maintenance requirement forecasts as well as the availability of resources. Candidate solutions are compared using a proxy for network throughput capacity. Due to the long computation times required to solve the MIP model at the annual planning horizon a matheuristic is developed and two variants are tested. On average 80% less computational time is required to find a good solution (average gap of 5%) using the matheuristic compared to solving the MIP model directly (average gap of 1.5%). The MIP model and associated matheuristic provides a suitable framework for semi-automated maintenance planning and is being integrated into the current suite of decision support tools used by Aurizon.

We study a variant of an abstract scheduling problem inspired by the management of reclaimers in the stockyard of a coal export terminal. We prove NP-completeness of the problem and formulate it as a mixed-integer program. We show that for a given reclaiming sequence, the problem can be solved in pseudo-polynomial time. In addition, we provide simple, constant-factor approximation algorithms as well as exact branch-and-bound algorithms. An extensive computational study analyzes the performance of the algorithms.

We study the problem of scheduling maintenance on arcs of a capacitated network so as to maximize the total flow from a source node to a sink node over a set of time periods. Maintenance on an arc shuts down the arc for the duration of the period in which its maintenance is scheduled, making its capacity zero for that period. A set of arcs is designated to have maintenance during the planning period, which will require each to be shut down for exactly one time period. In general this problem is known to be NP-hard. Here we identify a number of characteristics that are relevant for the complexity of instance classes. In particular, we discuss instances with restrictions on the set of arcs that have maintenance to be scheduled; series parallel networks; capacities that are balanced, in the sense that the total capacity of arcs entering a (non-terminal) node equals the total capacity of arcs leaving the node; and identical capacities on all arcs.

We study a network design problem inspired by a strategic planning problem encountered in the Hunter Valley Coal Chain. Demand is given in the form of freight that is available from a specific date and has to be transported from multiple origins to a single destination before its deadline. It is possible to temporarily store freight at certain intermediate locations along the way from origins to destination. The objective is to determine minimum-cost capacity expansions required on the links and nodes of the network, if any, so as to be able to transport all freight within its given time windows. A natural mixed integer programming formulation with a daily granularity quickly becomes computationally intractable. We investigate the potential of time aggregation to overcome the computational challenges. By aggregating consecutive time periods, a smaller instance is obtained, which can be solved more easily and provides a lower bound on the optimal value. A carefully designed iterative disaggregation scheme identifies a time aggregation that yields an optimal solution to the original problem. An extensive computational study demonstrates the efficacy of the proposed approach.