Linear Programming | Operations Research | Bayesian Networks
Queuing Theory | Knowledge Management | Statistics

Linear Programming

Linear programming is an important field of optimization for several reasons. Many practical problems in operations research can be expressed as linear programming problems. Certain special cases of linear programming, such as network flow problems and multicommodity flow problems are considered important enough to have generated much research on specialized algorithms for their solution. A number of algorithms for other types of optimization problems work by solving LP problems as sub-problems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as duality, decomposition, and the importance of convexity and its generalizations.

Geometrically, the linear constraints define a convex polyhedron, which is called the feasible region. Since the objective function is also linear, all local optima are automatically global optima. The linear objective function also implies that an optimal solution can only occur at a boundary point of the feasible region.

There are two situations in which no optimal solution can be found. First, if the constraints contradict each other (for instance, x = 2 and x = 1) then the feasible region is empty and there can be no optimal solution, since there are no solutions at all. In this case, the LP is said to be infeasible.

Barring these two pathological conditions (which are often ruled out by resource constraints integral to the problem being represented, as above), the optimum is always attained at a vertex of the polyhedron. However, the optimum is not necessarily unique: it is possible to have a set of optimal solutions covering an edge or face of the polyhedron, or even the entire polyhedron (This last situation would occur if the objective function were uniformly equal to zero).

Operations Research

The terms Operations Research and Management Science are often used synonymously. When a distinction is drawn, management science generally implies a closer relationship to the problems of business management.

Operations research also closely relates to industrial engineering. Industrial engineering takes more of an engineering point of view, and industrial engineers typically consider OR techniques to be a major part of their toolset.

Some of the primary tools used by operations researchers are statistics, optimization, stochastic, queuing theory, game theory, graph theory, and simulation. Because of the computational nature of these fields OR also has ties to computer science, and operations researchers regularly use custom-written or off-the-shelf software.

Operations research is distinguished by its ability to look at and improve an entire system, rather than concentrating only on specific elements (though this is often done as well). An operations researcher faced with a new problem is expected to determine which techniques are most appropriate given the nature of the system, the goals for improvement, and constraints on time and computing power. For this and other reasons, the human element of OR is vital. Like any tools, OR techniques cannot solve problems by themselves.

A few examples of applications in which operations research is currently used include the following:

• designing the layout of a factory for efficient flow of materials
• constructing a telecommunications network at low cost while still guaranteeing quality service if particular connections become very busy or get damaged
• determining the routes of school buses so that as few buses are needed as possible
• designing the layout of a computer chip to reduce manufacturing time (therefore reducing cost)
• managing the flow of raw materials and products in a supply chain based on uncertain demand for the finished products

Bayesian Network

Questions about dependence among variables can be answered by studying the graph alone. It can be shown that the graphical notion called d-separation corresponds to the notion of conditional independence: if nodes X and Y are d-separated (given specified evidence nodes), then variables X and Y are independent given the evidence variables.

In order to carry out numerical calculations, it is necessary to further specify for each node X the probability distribution for X conditional on its parents. The distribution of X given its parents may have any form. However, it is common to work with discrete or Gaussian distributions, since that simplifies calculations.

The goal of inference is typically to find the conditional distribution of a subset of the variables, conditional on known values for some other subset (the evidence), and integrating over any other variables. Thus a Bayesian network can be considered a mechanism for automatically constructing extensions of Bayes' theorem to more complex problems.

Bayesian networks are used for modelling knowledge in gene regulatory networks, medicine, engineering, text analysis, image processing, and decision support systems.

Learning the structure of a Bayesian network is a very important part of machine learning. Given the information that the data is being generated by a bayesian network and that all the variables are visible in every iteration, the following methods are used to learn the structure of the acyclic graph and the conditional probability table associated with it. The elements of a structure finding algorithm are a scoring function and a search strategy. An exhaustive search returning back a structure that maximizes the score is one implementation which is superexponential in the number of variables. A local search algorithm makes incremental changes aimed at improving the score of the structure. A global search algorithm like Markov chain Monte Carlo does not get trapped in local minima. Friedman et. al. talk about using mutual information between variables and finding a structure that maximizes this. They do this by restricting the parent candidate set to k nodes and exhaustively searching therein.

Queuing Theory

Queuing Theory is the mathematical study of waiting lines (or queues). There are several related processes, arriving at the back of the queue, waiting in the queue (essentially a storage process), and being served by the server at the front of the queue. It is applicable in transport and telecommunication. Occasionally linked to ride theory.

The maximum size of the system. The maximum number of customers allowed in the system including those in service. When the number is at this maximum, further arrivals are turned away.
The size of calling source. The size of the population from which the customers come. This limits the arrival rate. As more jobs queue up there are fewer available to arrive into the system.
The word queue comes from the Latin cauda, meaning tail.

Queueing theory is directly applicable to intelligent transportation systems, call centers, PABXs, networks, telecommunications, server queueing, mainframe computer queueing of telecommunications terminals, advanced telecommunications systems, and traffic flow.

Knowledge Management

Knowledge Management caters to the critical issues of organizational adaptation, survival, and competence in face of increasingly discontinuous environmental change.... Essentially, it embodies organizational processes that seek synergistic combination of data and information processing capacity of information technologies, and the creative and innovative capacity of human beings."
In simpler terms, Knowledge Management seeks to make the best use of the knowledge that is available to an organization, creating new knowledge, increasing awareness and understanding in the process.

"The goal of commercial knowledge is not truth, but effective performance: not 'what is right' but 'what works' or even 'what works better' where better is defined in competitive and financial contexts" Demarest, M, 1997. Long Range Planning 30, (3) pp 374-384

Enterprise knowledge management - EKM is concerned with strategy, process and technologies to acquire, store, share and secure organizational understanding, insights and core distinctions. KM at this level is closely tied to competitive advantage, innovation and agility.

It is helpful to make a clear distinction between knowledge on the one hand, and information and data on the other.

Information can be considered as a message. It typically has a sender and a receiver. Information is the sort of stuff that can, at least potentially, be saved onto a computer. Data is a type of information that is structured, but has not been interpreted.

Knowledge might be described as information that has a use or purpose. Whereas information can be placed onto a computer, knowledge is emergent, and socially constructed, exists in the heads of people. Knowledge is information to which an intent has been attached.

Corporate Memory (CM) can be defined as the total body of data, information and knowledge required to deliver the strategic aims and objectives of an organization. A corporate memory is the combination of a repository - the space where objects and artefacts are stored, and the community - the people that interact with those objects to learn, make decisions, understand context or find colleagues.

Corporate Memory can be subdivided into the following types:

• Professional (Reference material, documentation, tools, methodologies)
• Company (Organizational structure, activities, products, participants)
• Individual (Status, competencies, know-how, activities)
• Project (Definition, activities, histories, results)

Key decisions when exploring CM are:

• What knowledge representation to use (stories, patterns, cases, rules, predicate logic...)
• Who will be the users - what are their information and learning needs?
• How to ensure security and who will be granted access
• How to best integrate with existing sources, stores and systems
• What to do to ensure the current content is correct, applicable, timely and weeded
• How to motivate experts to contribute
• What to do about ephemeral insights, how to capture informal scripts e.g. e-mail and IM instant messenger posts.
• Alternative & related terms are: organizational memory, group memory, knowledge base, knowledge repository.

Most commercial knowledge management efforts have included building some form of corporate memory to capture expertise, speed learning, help the organization remember, record decision rationale, document achievements or learn from past failures.

Statistics

Statistics is the science and practice of developing knowledge through the use of empirical data expressed in quantitative form. It is based on statistical theory which is a branch of applied mathematics. Within statistical theory, randomness and uncertainty are modelled by probability theory. Because one aim of statistics is to produce the "best" information from available data, some authors consider statistics a branch of decision theory. Statistical practice includes the planning, summarizing, and interpreting of observations, allowing for variability and uncertainty.