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 is still unsolved, although I have shown 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.

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, http://arxiv.org/abs/1101.4903

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.

MIT OpenCourseware Resources for Operations Research.

MIT OCW is a large-scale, Web-based publication of the educational materials from the MIT faculty's courses. OCW provides users with open access to the syllabi, lecture notes, course calendars, problem sets and solutions, exams, reading lists, even a selection of video lectures, from 1,100 MIT courses representing 34 academic disciplines and all five of MIT's schools.

Here is a list of MIT subjects in the area of Operations Research.  All of these are available directly from the MIT OCW website or from the MIT OCW Archived Courses at DSpace.

Undergraduate Subjects

1.00           Introduction to Computers and Engineering Problem Solving, Spring 2002 

1.00           Introduction to Computers and Engineering Problem Solving, Fall 2002 

6.041         Probabilistic Systems Analysis and Applied Probability, Fall 2002 

6.046J       Introduction to Algorithms, Fall 2004 

14.12         Economic Applications of Game Theory, Fall 2002 

15.053       Introduction to Optimization, Spring 2002 

15.075       Applied Statistics, Spring 2003 

18.433       Combinatorial Optimization, Fall 2003 

18.441       Statistical Inference, Spring 2002 

18.443       Statistics for Applications, Fall 2003

Graduate Subjects

1.203J       Logistical and Transportation Planning Methods, Fall 2001 

1.206J       Airline Schedule Planning, Spring 2003 

1.225J       Transportation Flow Systems, Fall 2002

1.270J       Logistics and Supply Chain Management

2.098         Optimization Methods, Fall 2004 

2.111J       Quantum Computation, Fall 2003 

2.141         Modeling and Simulation of Dynamic Systems, Fall 2002 

2.830J       Control of Manufacturing Processes, Spring 2008 

2.851J       System Optimization and Analysis for Manufacturing, Summer 2003 

2.852         Manufacturing Systems Analysis, Spring 2004 

2.853         Manufacturing Systems I: Analytical Methods and Flow Models, Fall 2002 

2.854         Manufacturing Systems I, Fall 2004 

2.997         Decision Making in Large Scale Systems, Spring 2004 

6.231         Dynamic Programming and Stochastic Control, Fall 2002 

6.252J       Nonlinear Programming, Spring 2003 

6.252J       Nonlinear Programming, Spring 2004 

6.253         Convex Analysis and Optimization, Spring 2004 

6.254         Game Theory with Engineering Applications

6.263J       Data Communication Networks, Fall 2002 

6.268         Network Science and Models

6.281J       Logistical and Transportation Planning Methods, Fall 2001 

6.336J       Introduction to Numerical Simulation, Fall 2003 

6.431         Probabilistic Systems Analysis and Applied Probability, Fall 2002 

6.841J       Advanced Complexity Theory 

6.854J       Advanced Algorithms, Fall 2001 

6.855J       Network Optimization, Spring 2003 

6.856J       Randomized Algorithms, Fall 2002 

6.859         Integer Program Combination Optimization, Fall 2004 

14.126       Game Theory, Fall 2002 

15.057       Systems Optimization, Spring 2003 

15.060       Data, Models, and Decisions, Fall 2002 

15.063       Communicating With Data, Summer 2003 

15.066J     System Optimization and Analysis for Manufacturing, Summer 2003 

15.067       Competitive Decision-Making and Negotiation, Spring 2003 

15.073J     Logistical and Transportation Planning Methods, Fall 2001 

15.077J     Statistical Learning and Data Mining

15.082J     Network Optimization, Spring 2003 

15.083J     Integer Program Combination Optimization, Fall 2004 

15.084J     Nonlinear Programming, Spring 2004 

15.084J     Nonlinear Programming, Spring 2003 

15.093       Optimization Methods, Fall 2004 

15.094       Systems Optimization: Models and Computation, Spring 2002 

15.099       Readings in Optimization, Fall 2003         

15.760A    Operations Management, Spring 2002 

15.760B    Introduction to Operations Management, Spring 2004 

15.764       The Theory of Operations Management, Spring 2004 

15.769       Operations Strategy, Spring 2003 

15.770J     Logistics Systems, Fall 2003 

15.778       Management of Supply Networks for Products and Services, Summer 2004 

15.792J     Proseminar in Manufacturing, Fall 2002 

15.795       Seminar in Operations Management, Fall 2002 

15.871       System Dynamics for Business Policy, Fall 2003 

15.874       System Dynamics for Business Policy, Fall 2003 

15.875       Applications of System Dynamics, Spring 2004 

16.888       Multidisciplinary System Design Optimization

18.997       Topics in Combinatorial Optimization, Spring 1994

Textboooks Suggested by current ORC[MIT] affiliated faculty members.

	Andrew Lo A Non-Random Walk Down Wall Street   For over half a century, financial experts have regarded the movements of markets as a random walk -- unpredictable meanderings akin to a drunkard's unsteady gait -- and this hypothesis has become a cornerstone of modern financial economics and many investment strategies. Here Andrew W. Lo and A. Craig MacKinlay put the Random Walk Hypothesis to the test In this volume, which elegantly integrates their most important articles, Lo and MacKinlay find that markets are not completely random after all, and that predictable components do exist in recent stock and bond returns. Their book provides a state-of-the-art account of the techniques for detecting predictabilities and evaluating their statistical and economic significance, and offers a tantalizing glimpse into the financial technologies of the future.
	Andrew Lo The Econometrics of Financial Markets   The past twenty years have seen an extraordinary growth in the use of quantitative methods in financial markets. Finance professionals now routinely use sophisticated statistical techniques in portfolio management, proprietary trading, risk management, financial consulting, and securities regulation. This graduate-level textbook is intended for PhD students, advanced MBA students, and industry professionals interested in the econometrics of financial modeling. The book covers the entire spectrum of empirical finance, including: the predictability of asset returns, tests of the Random Walk Hypothesis, the microstructure of securities markets, event analysis, the Capital Asset Pricing Model and the Arbitrage Pricing Theory, the term structure of interest rates, dynamic models of economic equilibrium, and nonlinear financial models such as ARCH, neural networks, statistical fractals, and chaos theory.
	Andrew Lo The Industrial Organization and Regulation of the Securities Industry (National Bureau of Economic Research Conference Report) The regulation of financial markets has for years been the domain of lawyers, legislators, and lobbyists. In this unique volume, experts in industrial organization, finance, and law, as well as members of regulatory agencies and the securities industry, examine the securities industry from an economic viewpoint. Ten original essays address topics including electronic trading and the "virtual"stock exchange; trading costs and liquidity on the London and Tokyo Stock Exchanges and in the German and Japanese government bond markets; international coordination among regulatory agencies; and the impact of changing margin requirements on stock prices, volatility, and liquidity.
	Andrew Lo Market Efficiency: Stock Market Behaviour in Theory and Practice (International Library of Critical Writings in Economics) The efficient markets hypothesis is one of the most controversial and hotly contested ideas in all the social sciences. It is disarmingly simply to state, has far-reaching consequences for academic pursuits and business practice, and yet is surprisingly resilient to empirical proof or refutation. Even after three decades of research and literally thousands of journal articles, economists have not yet reached a consensus about whether markets - particularly financial markets - are efficient or not. These two volumes bring together the most influential articles surrounding the efficient markets hypothesis debate, from Paul Samuelson's pathbreaking proof that properly anticipated prices fluctuate randomly to Fischer Black's study of noise traders, from Eugene Fama's empirical implementation of the efficient markets hypothesis to Robert Merton's analysis of stock price volatility.
Logistics
	David Simchi-Levi, Philip Kaminsky, and Edith Simchi-Levi Designing & Managing the Supply Chain Supply chain management, both in industry and in academia, has grown rapidly over the past several years mainly due to an increase in corporate goals of reducing manufacturing costs and the savings that come from planning and managing the supply chain effectively. Most textbooks do not include models and decision support systems robust enough for industry. Designing and Managing the Supply Chain: Concepts, Strategies, and Cases, 2/e by Simchi-Levi, Kaminsky and Simchi-Levidiscusses the problems, models and concepts derived from issues related to effective supply chain management. This text is suitable for both academic study and practicing professionals. While many core supply chain management issues are interrelated, the authors have tried to make each chapter as self-contained as possible so that the reader can refer directly to chapters covering topics of interest. Each chapter utilizes case studies and numerous examples. Mathematical and technical sections can be skipped without loss of continuity. The accompanying CD-ROM also provides two simulations, the Computerized Beer Game and the Risk Pool Game and a computerized tool, new to this edition, for developing and executing supply chain contracts. These packages help illustrate many of the concepts discussed.
	David Simchi-Levi, Xin Chen, and Julien Bramel Logic Of Logistics: Theory, Algorithms, And Applications For Logistics Management Fierce competition in today's global market provides a powerful motivation for developing ever more sophisticated logistics systems. This book, written for the logistics manager and researcher, presents a survey of the modern theory and application of logistics. The goal of the book is to present the state of the art in the science of logistics management. As a result, the authors have written a timely and authoritative survey of this field that many practitioners and researchers will find makes an invaluable companion to their work.
	David Simchi-Levi, Philip Kaminsky, and Edith Simchi-Levi Managing the Supply Chain: The Definitive Guide for the Business Professional In today's environment of tight budgets and even tighter turnarounds, effective supply-chain management has become a core business requirement. Managing the Supply Chain adapts the number one supply-chain book on the college market to examine how professionals can consistently turn supply-chain strategy into a competitive advantage. This results-based book examines the experiences of today's most accomplished companies to demonstrate supply-chain innovation at work in the marketplace.
	Donald B. Rosenfield, John Magee, and William Copacino Modern Logistics Management, Linking Marketing, Manufacturing, and Physical Distribution This comprehensive overview of logistics provides a conceptual framework for understanding the logistics system, the integration of its basic elements, and its relationship to the overall firm. Discusses both manufacturing and physical distribution, new technologies in each of these areas, and how they related to each other and to the company. New topics covered range from approaches to strategic logistics planning and multi-location inventory planning, to international logistics issues and future directions.
	Yosef Sheffi The Resilient Enterprise: Overcoming Vulnerability for Competitive Advantage Logistics, argues that a company�s survival and prosperity depend more on what it does before such a disruption occurs than on the actions it takes as the event unfolds. In The Resilient Enterprise: Overcoming Vulnerability for Competitive Advantage, Sheffi explores high-impact/ low-probability disruptions, focusing not only on security but on corporate resilience�the ability to bounce back from such disruptions�and how resilience investments can be turned into competitive advantage. Sheffi provides tools for companies to reduce the vulnerability of the supply chain they live in. And along the way he tells the stories of dozens of enterprises, large and small, including Toyota, General Motors, UPS, Intel, Amazon.com, the US Navy, and others from across the globe. Their successes, failures, preparations, and methods provide a rich set of lessons in preparing for and managing disruptions.
	Yosef Sheffi Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods What happens to a company when the unimaginable occurs? When an earthquake hits its primary contract manufacturer? When labor strikes shut down an entire port? When terrorists cripple a transportation system?
Management Science
	Dimitris Bertsimas and Robert Freund Data, Models, and Decisions This book represents a departure from existing textbooks. Rather than covering methodology, the book introduces decision support systems through real world applications, and uses spreadsheets to model and solve problems. It uses management science techniques (statistics, simulation, probabilistic modeling and optimization), but only as tools to facilitate problem solving.
Manufacturing
	Stanley B. Gershwin Manufacturing Systems Engineering This book provides quantitative methods for the capacity analysis and real-time scheduling of manufacturing systems. It treats these issues as engineering problems, without slogans, and it faces technical details in an appropriate, useful way. This book provides a fundamental description of some of the most important phenomena affecting material flow in manufacturing systems: machine failures, starvations, blockages, and set-ups. It has a point of view: that disruptions, while undesirable, are a fact of life in a factory. While effort should be expended to reduce them, or even to eliminate them, some amount of disruption is inevitable, and we should develop ways of predicting and limiting their negative effects. The book describes some potentially disruptive events that affect production, the control actions that managers can take in anticipation of or in response to the disruptions, and the consequences of the control actions. The goal is to contribute to the development of a rigorous, and useful, manufacturing systems science. The emphasis in the early chapters is a capacity analysis of flow systems. The later chapters deal with the real-time control of manufacturing systems. Mathematical background in Markov processes, linear programming, and dynamic programming is provided.
Optimization
	Dimitris Bertsimas and John N. Tsitsiklis Introduction to Linear Optimization The book is a modern and unified introduction to linear optimization (linear programming, network flows and integer programming) at the PhD level. It covers, in addition to the classical material, all the recent developments in the field in the last ten years including the development of interior points, large scale optimization models and algorithms and complexity of linear optimization. It emphasizes the underlying geometry, intuition and applications of large scale systems.
	Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin Network Flows: Theory, Algorithms, and Applications Bringing together the classic and the contemporary aspects of the field, this comprehensive introduction to network flows provides an integrative view of theory, algorithms, and applications. It offers in-depth and self-contained treatments of shortest path, maximum flow, and minimum cost flow problems, including a description of new and novel polynomial-time algorithms for these core models. For professionals working with network flows, optimization, and network programming.
	Dimitris Bertsimas and Robert Weismantel Optimization over Integers The purpose of this book is to provide a unified, insightful, and modern treatment of the theory of integer optimization with an eye towards the future. We have selected those topics that we feel have influenced the current state of the art and most importantly we feel will affect the future of the field. We depart from earlier treatments of integer optimization by placing significant emphasis on strong formulations, duality, algebra and most importantly geometry.
OR in the Public Sector
	Richard C. Larson and Amedeo R. Odoni Urban Operations Research Richard C. Larson and Amadeo R. Odoni Urban Operations Research Approximately 68 percent of the citizens of the world's developed countries live today in cities or in city-centered metropolitan areas. ¹ The economic and social fabric of these high-density clusters is elaborately interwoven, with the well-being of each citizen intricately enmeshed with the activities of others. Strong interdependencies arise in all areas of human need: food, shelter, safety, clothing, recreation, maintenance, energy provision, and so on. Servicing these needs requires highly structured transportation and communication networks throughout the city for effective provision of a variety of urban services: emergency medical, police, mail collection and delivery, fire protection, street and highway maintenance, utility repair, snowplowing, street cleaning, refuse collection, bus and subway transportation, taxi transportation, and so on. Increasingly, citizens are demanding more urban services, by type, quantity, and quality. Yet the ability of most cities in the United States and elsewhere to pay for additional services has been severely strained during the 1970s. The resulting pressure, between the demands for more and better services, on the one hand, and decreased costs, on the other, has created a strong need for improved management decision making in urban services. It is a primary purpose of this book to provide methods for assisting these decisions.