University of Cambridge > Mathematics > Statistical Laboratory > Richard Weber > Unsolved Problems

Unsolved Problems in OR

This page contains a list of open problems that I find intriguing. They are not major problems (like whether P does or not equal NP), but they are all easy to state and understand, and their solution has defied the efforts of good researchers over a number of years.

This set of problems reflects my own interests and is not attempting to be comprehensive. Most of these problems are in the realm of stochastic dynamic programming and optimization. I would love to see a solution to any of these problems

I have noticed that this page receives quite a lot of internet traffic, so I will attempt to update it sometime soon and add some other problems. I have also implemented a place at the end of this page where people who view it may leave comments..

There has been some significant progress on the first two of these problems that is not fully described here, but whch can be found on other of my web pages. I make a few brief comments below (I am writing on 23 October 2011). If anyone has any news about any of these problems, or would like to suggest a problem. please do contact me.

A related page of interest is Harvey Greenberg's Myths and Counterexamples in Mathematical Programming.

The bomber problem

(see description) This problem originates in the 1960s and remained unsolved for many years. I showed in the paper below that Conjecture B is false if the usual assumptions are only mildly relaxed. See

R.R. Weber, ABCs of the bomber problem and its relatives, 2011.

Excitingly, Takashi Kamihigashi has now shown that Conjecture B is false. See

T. Kamihigashi, 41 Counterexamples to property (B) of the discrete time bomber problem, 2016.

He did this by an exhaustive search over 999^2 x 100^2 parameter values. He found 41 instances in which Conjecture B fails. One of these, for example, is when the enemy plane survies k anit-aircraft misslies with probability 1-q^k, q=0.829, and attacks occur with probability r=0.830, he finds that with 6 steps to go the optimal number of missiles to fire is 16 when the number of remaining missiles is 88, but 17 when the number remaining is the lesser number of 87.

The rendezvous problem

(see description) There are many unsolved rendezvous problems. However, the problem on the complete graph K3 has now been solved. See

R.R. Weber, The optimal strategy for rendezvous search on K3, 2006.

There remain many interesting open questions. For example, consider the game that is played on a a complete graph of N vertices. No one has ever been able to show that the rendezvous value (minimum expected rendezvous time) is increasing in N.

The problem of symmetric rendezvous search on a line is particularly interesting. Players start 2 units apart, not knowing whether the other player is in front or behind by 2 units. At each step each player moves forward or back by 1 unit. Initially the players might be told that they are faced the same direction, or they might be told that their facing directions are random directions. So far as minimizing the expected rendezvous time goes, it seems not to matter which initial condition is given. Explain this!

Search for a moving target

(see abstract) Long ago, I solved a continuous-time version of this problem.

R.R. Weber. Optimal search for a randomly moving object. J. Appl. Prob. 23:708-717, 1986.

But the discrete-time version of this problem is still unsolved. There have been parital solutions, but no solution for all possible values of the model parameters.

Non-preemptive release of stochastic jobs to uniform machines

See abstract and R.R. Weber. On a conjecture about assigning jobs to processors of different speeds. IEEE Trans. Auto. Control 38, 166-169, 1993.

I make the conjecture that an optimal policy has the property that whenever it assigns a job to an available processor, it makes the assignment to the fastest available processor. Moreover, there exist thresholds, one for each state of the processors and decreasing in the state (seen as a boolean vector, in which busy and idle processors are indicated by 1 and 0, respectively), such that an optimal policy is to assign a job to an available processor if, and only if, the number of jobs in the buffer exceeds the relevant threshold for the present state of the processors.

The unimportance of inserted idle time in non-preemptive stochastic scheduling to minimize flow time on parallel machines

Suppose you have n jobs that are to be processed on m identical machines which operate in parallel (m<n). The processing time of job i is modelled as being a random variable X_i with some known distribution. We wish to process the jobs so as to minimize the expected value of the sum of completion times. Scheduling is non-preeemptive, so once a job has begun processing on a machine it must continue to be processed until it is complete. At each time that a job finishes we could either immediately start another job on the machine that is now free, or leave that machine idle while we wait until a further job completes on some other machine (and thereby learn a bit more before committing to our next job assignment). Is it ever advantageous to wait (i.e. to insert idle time)? The conjecture is that it is not. We should always proceed to start a job on each machine as soon as it becomes free. (I am not convinced that I remember this probelm correctly. I thought it was for X_i exponentially distributed, but in that case it seems obvious (?) that one should not insert idle time.)

Berry's conjecture for Bernoulli bandits

Berry (1972) makes the following plausible and intriguing conjecture.

Consider two independent Bernoulli bandit processes (or arms) having beta priors Beta(u_i,v_i), i=1,2. That is, the probability of success of arm i, say p, has a prior density on [0,1] that is proportional to p^{u_1–1}(1–p)^{v_1–1}, and so a priori mean of u_i/(u_i+v_i). Such a arm arises if we begin with a arm for which p is assumed to be uniformly distributed on [0,1], and then we sample it u_i+v_i–2 times, and observe u_i–1 successes and v_i–1 failures.

Suppose that arm 1 offers the greatest immediate probability of a success at its next sampling, i.e. u_1/(u_1+v_1) >=u_2/(u_2+v_2). Suppose that arm 1 has also been sampled less, so u_1+v_1<=u_2+v_2. The aim is to conduct N more trials of amongst these two arms in such a way as to maximize the expected total number of successes that are obtained. Berry's conjecture is that in these circumstances the next trial should optimally be of arm 1. This is intutively very plausible since arm 1 not only offers the greater immediate reward, but also there is more useful information to be gained by sampling arm 1 (since thus far it has been sampled less).

The conjecture is obviously true if N=1. It can probably be proved true for small N. It is true (because of Gittins index results) when the time horizon is infinity and rewards are geometrically discounted. But the status of the conjecture for finite N and no discounting remains unresolved.

D. A. Berry (1972) A Bernoulli two-armed bandit. Ann. Math. Statist. 43 871-897.

Some related work and comment on this conjecture appears in
Y. Yu (2011) Prior ordering and monotonicity in Dirichlet bandits,

Ruckle's conjecture for accumulation games

This open problem is described by S. Alpern, R. Fokkinck and K. Kikuta On Ruckle's conjecture on accumulation games, SIAM Journal on Control and Optimization, 48 (8). pp. 5073-5083. ISSN 0363-0129. The abstract to this paper reads:

"In an accumulation game, the Hider secretly distributes his given total wealth h among n locations, while the Searcher picks r locations and confiscates the material placed there. The Hider wins if what is left at the remaining n–r locations is at least 1; otherwise the Searcher wins. Ruckle's conjecture says that an optimal Hider strategy is to put an equal amount h/k at k randomly chosen locations for some k."

Note that the wealth in this problem is to be regarded as a continuous quantity. For example, we might imagine that Alladin is hiding a quantity of h litres of oil in n jars, from which a random subset of r jars will be stolen.

W. Ruckle (2001), Accumulation games, Sci. Math. Jpn. 54, no. 1, 173-203.

Please feel free to comment on these problems and suggest others.
blog comments powered by Disqus

University of Cambridge > Mathematics > Statistical Laboratory > Richard Weber > Unsolved Problems