Browsing by Browse by FOR 2008 "010206 Operations Research"

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 study a capacity alignment planning problem for a coal chain. Given a set of train operators, a set of train paths and a terminal comprising of a dump station and a set of routes from the dump station to the stockyard, we seek a feasible assignment of train operators to train paths, to time slots at the dump station, and to routes. The assignment must maximize the number of system paths in the resulting schedule and the schedule should perform well with respect to various performance criteria. We model the problem as a mixed-integer conic program (MICP) with multiple objectives which we solve using a hierarchical optimization procedure. In each stage of this procedure, we solve a single objective MICP. Depending upon whether we evaluate the associated performance criteria under a 2- or 1-norm, we reformulate the MICP as either a mixed-integer second-order cone program or as a mixed-integer linear program, respectively, and can streamline the hierarchical optimization procedure by exploiting properties of the model or observed behaviour on practical instances. We compare the performance of the procedure under the different norms on a real instance of the problem and find that the quality of the solutions found by the faster 1-norm procedure compares well to the solution found under the 2-norm.

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.

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.

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.

Viet Nam's tertiary education sector has obtained remarkable achievements in terms of policies of national reform and strategies of international cooperation during the renovation process. However, whether these policies are appropriate for the country to quickly find its place in the global market place is still unclear. Although a number of government regulations have been devised to accelerate the progress of tertiary institutions, the development of the sector appears to be sluggish. This study aims to: (i) provide an overview of the progress in tertiary sector including innovation in the government policies; and (ii) highlight challenges facing tertiary institutions and evaluate their performance in the practical context. Using the case of 82 public universities for the period 2011-2013, the performance of the sector is examined. Results reveal that the operational efficiency of public institutions is less than one, on average at 0.729, suggesting a significant potential to enhance their performance. Moreover, six key national institutions were ranked on the top 10 based on the efficiency scores. While the ranking system for Vietnamese higher education sector is still an on-going process, assessing the performance of institutions on efficiency-based ranking is an alternative tool to enhance accountability and transparency of institutions in the progress of the comprehensive renovation of the Vietnamese higher education system.

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

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.

This paper addresses the coordination of railway network maintenance and train traffic. The work extends a previously developed optimization model by considering maintenance resource constraints for crew availability and work time regulations. The aim is to find a long term tactical plan that minimizes the total cost of maintenance and train operations, where train services and train free windows are scheduled such that maintenance can be carried out by a pool of crew resources, which are divided into bases and have limitations on maximum working hours per day and minimum rest time between these working days. A mixed integer linear programming model along with computational experiments are presented which show that these resource considerations can be correctly handled with a moderate increase in model size and solution time.

The early scene: I was appointed to the first Chair of Chemistry in 1955, the year after UNE became autonomous. However chemistry was already well established at the former University College, the first lecturer, T.B. Swanson, having been appointed in 1939. I arrived to find a flourishing department under Noel Riggs, whom I knew well from my Perth and Cambridge years. He, Jim Banfield and Keith Lewis were organic chemists, with Ray Stimson and Frank Dudley on the physical and inorganic side. The main buildings then were 'Booloominbah', which held several teaching rooms, the library, the administration and a dining room; the Booth building, which held several laboratories, lecture rooms and staff offices; and the Belshaw building, a large steel-framed asbestos-board structure accommodating several science disciplines. There were no colleges on the campus at that time, though Mary White College was just being started. Nearly all the students lived in large former family homes in the town, owned or leased by the University, and were brought in by bus for meals in 'Booloominbah' as well as their courses. The bridge on Elm Avenue was subject to occasional flooding, and the only access then was via a rough road through the farm to North Hill.

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.

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