ORSUM 2004

Episode II

Time: 1:00pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Dr J. V. Howard (The London School of Economics and Political Science)

Title: Alternating search in two regions

Abstract:

A new class of search problem is called `alternating search'. In such a problem, two searchers starting at given points in different search regions, who can mov e alternately with speed one, or (as a limiting case) simultaneously with combin ed speed one, seek to find an object in least expected time. The hidden object i s stationary and its location is given by a known distribution over the union of the two search regions.

An important special case is the `Double Linear Search Problem' in which both se arch regions are infinite lines, and which has been shown to be equivalent to th e `Asymmetric Rendezvous Search Problem on the Line' (ARSPL). Our general results are concerned with determining the method of interleaving two given dist ributions so as to minimize the first moment of the resulting distribution.

(This is joint work with Steve Alpern)

These slides are based on the paper: Alpern, S. and Howard, J. V. "Alternating search at two locations". Dynamics and Control, 10: 319--339, 2001.

Episode III

Time: 1.05pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Ana Novak (University of Melbourne)

Title: Using Packet Pair Probing to Estimate Arrival-Rate and Packet Size

Abstract:

The appeal of the active probing is its intrinsically end-to-end nature which allows the non-privileged users to probe Internet traffic. This talk will present a packet-pair based method used to estimate packet size and arrival rate on a singular link. It will be shown how to tune the probe packet size and pair separation so that the width of the confidence interval for the estimated parameter is minimised.

Episode IV

Time: 1.05pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Prof Hyam Rubinstein (University of Melbourne)

Title: Shortest Networks in Space

Abstract:

The study of shortest networks in the plane (sometimes called the motorway or Steiner problem) has a very long history. In the 1960s and 1970s researchers at ATT Bell labs became interested in this problem and made significant progress. Recently, attention has been drawn to the analogous problem in 3-dimensional space. I will survey what is known and some of the interesting questions in this area. One of the most exciting developments has been the connection to the design of underground mines.

All of our work is with the networks group of Marcus Brazil (EE), David Lee (UniSA), Doreen Thomas (EE), Jia Weng (EE), Nick Wormald (Waterloo).

Episode V

Time: 1.05pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Tim Robinson (University of Melbourne)

Title: Using Mehrotra's Predictor Corrector Scheme in Model Predictive Control

Abstract:

Model predictive control is an optimal control technique where the control action is calculated by solving on-line an optimization problem. One of the key features of model predictive control is its ability to handle hard constraints on the plant being controlled. In [the presentation], the control signal is formulated using discrete Laguerre functions rather than the traditional approach of using a train of Dirac delta pulses. The framework for the Laguerre function technique is a discrete-time state space model. A quadratic cost function is formulated in order to penalize deviations of the output from a given sequence of setpoints. The minimum of this cost function is found using a quadratic programming version of Mehrotra's predictor-corrector algorithm. This algorithm is a primal-dual interior-point method and incorporates a few heuristics in order to attain its high efficiency.

Episode VI

Time: 1.05pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Maya Ramakrishnan (University of Melbourne)

Title: A distributed approach to bandwidth allocation in logical networks

Abstract:

We consider a dynamic bandwidth re-allocation scheme in a logically connected network. We pose the problem in an optimisation framework and note that any algorithm that solves such a problem must be scalable. Scalability in this setting is reliant on the algorithm being decentralised in nature. Under assumptions regarding the connectedness of the logical network, the optimisation problem can be solved arbitrarily closely in a distributed manner. The solution method is via a continuous bandwidth (capacity) re-allocation scheme within localised parts of the network. We use Lyapunov arguments to determine stability of the system. The theoretical framework motivates a discretised system, that is more appropriate from an implementation perspective. Comparisons between the two schemes are presented.

Episode VII

Time: 1.05pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Dr Tripti Chakrabarti (University of Calcutta)

Title: An inventory model for deteriorating items with price-dependent demand rate, shortages and quantity discounts

Abstract:

It is a well established fact in a market economy that the price and the demand for most of the products are inversely related. Empirical observations indicate that a price reduction results in an increase in demand, except for some luxury goods where the demand increases even when the price increases. Suppliers often offer temporary price discounts to retailers. This discount motivates retailers to increase their order quantity and the retailers in turn offer a discount to their customers to increase demand and profit.

The classical quantity discount EOQ model has been extensively studied in the inventory literature. The model has been studied from the point of view of the buyer to determine the optimal order quantity. The quantity discount problem from the point of view of supplier has also been analysed. All the above models assume that the demand for the product is a known constant. But in retailing situations, the demand for the product cannot be constant; it would be a function of the price that the retailer sets for the product. The traditional quantity discount models have been studied considering two kinds of price discount-"all unit quantity discount" and "incremental discount".

Lee introduced another type of discount structure in the inventory model. He formulated the classical EOQ model with setup cost including a fixed cost and freight cost where the freight cost incorporated a quantity discount. Hwang et. al. developed a classical EOQ model by taking all unit quantity discounts on the purchasing price and freight cost simultaneously. Abad developed inventory models to determine selling price and lot size for a retailer when the supplier would offer all-unit quantity discounts and incremental discounts and demand would be price dependent. Burwell et. al. extended the model of Abad allowing shortages.

In all the above inventory models, it has been assumed that the items can be stored indefinitely to meet the future demands. However, certain types of inventories either deteriorate or become obsolete in the course of time. If the rate of decay is very slow, its effect on the inventory replenishment policy can be ignored. But there are many items like electronic components, radioactive substances, food-stuff etc., where the decay plays a vital role. Hence the impact of deterioration in the modelling of such inventory system can not be neglected.

The present talk analyses the inventory model to determine the optimal selling price and lot size for a retailer when the demand is price-dependent and the supplier offers both all-unit quantity discounts and freight cost discounts, allowing shortages in inventory and taking deterioration of items into account.

Episode VIII

Time: 1.05pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Assoc Prof Bruce Craven (University of Melbourne)

Title: Stock Market Modelling

Abstract:

While the behavior of stock market indices (e.g. S & P 500) is close to a random walk, some additional features call for explanation. There are "up-phases", where prices rise, roughly linearly but with large fluctuations, for an extended period, and similar "down-phases" of falling prices. They are separated by short "crash-phases" of high variability. The statistical parameters appear to jump between phases. Within a phase, the "diflogs" (first differences of llogarithms of prices) are uncorrelated, and have a distribution far from gaussian (much more weight in the tails). While these facts are often observed, most theory assumes gaussian distributions, and models of autoregressive type, rather than jumps or pointwise disturbances. A simple model is proposed, where the changes in overall price levels depend on factors including interest rates, and available credit and external investment. This leads to a random walk for "diflogs", with an "offset" of the mean from zero, depending on the factors mentioned, An "up-phase" may end with a substantial price drop, either random (with substantial probability with a heavy-tailed distribution), or limited by external funding. However, there is yet no explanation for the heavy-tailed distribution, nor for the change in variance, sometimes observed between phases. This analysis gives no comfort to a trader wanting to predict when a crash will happen, since this depends largely on random fluctuations. (The bookmaker, not the punter, makes the money!)

Episode IX

Time: 1:05pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Prof Peter Taylor (University of Melbourne)

Title: Takacs' Ballot Theorem

Abstract:

In the process of doing some work on Ana Novak's Ph D topic, we found it necessary to understand a generalisation of the classical ballot theorem, due to Takacs. The result appeared in Takacs' book of 1962.

I want to discuss the result for two reasons. First, it is a beautiful result. Second, the proof is typical of how mathematics used to be communicated in those days. The statement and proof of the theorem do not take up much more than a half a page, but it took me some hours to make sure that I understood the entire thing perfectly.

In this talk, I shall present the classical ballot theorem, together with Takacs' generalisation and its proof.

If anyone wants to do some preparation, I shall have some copies of the relevant page of Takacs' book available a few days before the talk - soon to be available at this website.

Pages 1 and 2 are the important ones: Page 1 - Page 2 - Page 3

Episode X

Time: 1:05pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Dr Jana Siagiov, (University of Auckland)

Title: A graph covering approach in the degree-diameter problem and packings of graphs

Abstract:

In the design of interconnection networks with a large number of nodes, the two most common constraints are a limited number of connections attached to any node, and a restricted length of a communication route between any two nodes. On a theoretical level this leads to the {\em degree-diameter problem}, which is to determine, for each $d$ and $k$, the largest order $n_{d,k}$ of a graph of maximum degree $d$ and diameter $\le k$. Several techniques have been used for constructing large graphs of given degree and diameter. In our talk we present the covering graph approach, using the language of voltage assignments and lifts. We demonstrate the power of this method by re-constructing the currently largest known vertex-transitive graphs of diameter two and given degree. A number of other applications will be discussed as well, including the degree-diameter problem on surfaces and packings of graphs.

Episode XI

Time: 1:05pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Dr Vicky Mak (Deakin University)

Title: Column aggregation and disaggregation in Integer Programming: a review

Abstract:

While conducting research on variable aggregation and disaggregation in linear programming and integer programming, I found some very interesting paper on error bounds on variable aggregation/disaggregation. Previous work mostly went as far as that. This talk will review previous work, propose possible research directions, and discuss difficulties met so far.

Episode XII

Time: 1:05pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Liam Merlot (University of Melbourne)

Title: The School Course Timetabling Problem or How the Messiness of Real Life Can Obscure a Nice Model

Abstract:

The School Course Timetabling Problem is one that is faced by every school every year. How does one decide on a timetable which allows all students and teachers to attend all lessons of the classes of the subjetcs they are taking? The Population and Course Timetabling Problem or PCTP (where students need to be allocated to classes of their subjects and all lessons of all classes of all subjects need to be allocated to sessions) is too complex to be solved in itself, so it is normally decomposed into sub-problems. A common decomposition of the PCTP is the blocking decomposition, where the PCTP is decomposed into the Class Blocking and Population Problem (CBPP) and Block Timetabling Problem (BTP). The CBPP is normally decomposed further, but in this talk a model for a simplified CBPP is presented for solving this problem in one step. The model is then modified in order to solve the CBPP (and consequently the PCTP) for an Australian secondary school.

Episode XIII

Time: 1:05pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Dr Renata Sotirov (University of Melbourne)

Title: What is "in" Semidefinite Programming?

Abstract:

Semidefinite Programming (SDP) is an extension of linear programming where the nonnegativity constraints are replaced by positive semidefiniteness on the matrix variables. Though SDPs (under various names) have been studied as far back as the 1940s, the interest has grown tremendously during the last 10 years. That is due to the recent developments in algorithms as well as in computational platforms that resulted in a large improvement in the capability to solve SDP problems. Since SDP offers excellent possibilities for the design of very tight relaxations for combinatorial problems, problems in engineering etc., it turns to be one of the "hottest" area in Optimization. In the Seminar we give motivation, some properties, examples and applications of SDP. But maybe, we provide You even more ...

Episode XIV

Time: 1:05pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Dr Sanming Zhou (University of Melbourne)

Title: The weighted ring arc-loading problem with splitting: a polynomial-time algorithm

Abstract:

Rings (cycles) are among the most widely used structures for interconnection networks. For example, the SONET (synchronous optical network) ring is a standard configuration in telecommunication. Given a ring and a set of communication requests, each request associated with an integer weight, a fundamental problem is to design a transmission route for each request such that the maximum load on arcs of the ring is minimized, where an arc is an edge endowed with a direction and the load on an arc is the total weight of those requests that are routed through the arc in its direction. In the non-weighted case (namely, the weight of each arc is equal to 1), this problem can be solved in polynomial time by a result of Wilfong and Winkler. For the weighted case, the problem was proved to be NP-hard in 2002. Recently, by using the LP rounding technique together with combinatorial methods, we proved with Yuan that, if the weight of each request is allowed to split into two integral parts routed in two directions around the ring, then the problem can be solved in polynomial time. This talk is about the story of this polynomial algorithm. Other routing problems for rings will also be mentioned briefly.

Episode XIV

Time: 1:05pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Alan Brown (Swinburne University of Technology)

Title: Stochastic Programming for Business

Abstract:

The OR community expends considerable effort in developing decision support packages for use at the tactical level. These models are often complex and take account of a large number of constraints. Computer run times can be significant. Extending these packages to support decisions at the strategic level is not easy. It becomes necessary to make risk adjustments for errors that may occur in many estimates of future values.

The aim of this talk is to introduce a method for building into models a process of risk adjustment which does not incur excessive overheads. The method has both strengths and weaknesses, which will be exposed using examples from linear, quadratic and integer programming.

Interest in this topic is prompted by the integer programming models for open pit mining being developed at the University of Melbourne for BHP-Billiton. The thoughts on this particular project have led to a consideration of the wider application of a method of risk adjustment in practice.

Episode XV

Time: 1:05pm

Venue: Room 213, Richard Berry Building, The University of Melbourne

Speaker: Dr Heping Pan (Ballarat University)

Title: A Swingtum Theory of Intelligent Finance. Integrating Technical, Fundamental, Quantitative and Strategic Analysis of the Financial Markets

Abstract:

Swingtum stands for Swing and Momentum. A Swingtum Theory of Intelligent Finance is presented here in order to provide a scientific and engineering foundation to professional Swing Trading and Momentum Trading. The origins of Swingtum Theory naturally go deep into the empirical professional Technical Analysis, Fundamental Analysis and Strategic Analysis, and academic Quantitative Analysis including financial mathematics, econophysics and computational intelligence. The central perspective of Swingtum Theory is the pervasive existence of multilevel swings and abrupt momentum moves in the market prices, business fundamentals, mass psychology, and even the news flow. The dualism of swing versus momentum may resemble the wave-particle dualism in quantum mechanics, however with much higher nonlinearity and sophistication of human traders as building elements of the markets. This view forms the Swingtum Market Hypothesis, which is closer to the reality than Efficient Market Hypothesis and Fractal Market Hypothesis are. The Swingtum Theory models the markets with two parallel and intertwining lines of thought: the multilevel swings and momentums of a target market, and the influences from interrelated markets and the surrounding economic environment. The two lines are then unified into a comprehensive framework - Super Bayesian Influence Networks (SBIN) consisting of many probability ensembles of neural networks. To describe the multilevel swings and momentum for a single market, the scale space of phase provides the most essential information as input features to a SBIN model. Multifractality, log-periodic power laws, and physical cycles provide much of the building blocks to the unimarket swingtum models. Asymmetrical Dependence Test with conditionality and scaling of time provides a major tool for detecting intermarket influence relations. The Swingtum Theory focuses not only on abstract market modeling, but also on continuous monitoring the global financial markets, looking for pockets of predictability and profitability with the Global Influence Networks as an actual application of SBIN. Although this theory is still at an early stage of development, a SBIN for predicting daily direction of Australian All Ordinary Index (High, Low, Close) has already shown significant and nontrivial performance.

© The University of Melbourne 1994-2003.
Disclaimer and Copyright Information.

Created: 25 February 2004
Last modified: 29 November 2004
Authorised by: Moshe Sniedovich, Department of Mathematics and Statistics.