Complexity Economics Engineering Medicine Society

On Combinatorial Optimization and Complexity

Combinatorial optimization is the process of searching for maxima (or minima) of an objective function F whose domain is a discrete but large configuration space.

The space of possible solutions is typically too large to search exhaustively using pure brute force. In some cases, problems can be solved exactly using Branch and Bound techniques. However, in other cases no exact algorithms are feasible, and randomized search algorithms must be employed, such as:

  • Random-restart hill-climbing
  • Simulated annealing
  • Genetic algorithms
  • Tabu search

A large part of the field of Operations Research involves algorithms for solving combinatorial optimization problems.

Applications for combinatorial optimization include, but are not limited to:

  • Logistics
  • Supply chain optimization
  • Developing the best airline network of spokes and destinations
  • Deciding which taxis in a fleet to route to pick up fares
  • Determining the optimal way to deliver packages
  • Working out the best allocation of jobs to people
  • Designing water distribution networks
  • Earth Science problems (e.g. reservoir flow-rates)

Another example is that of portfolio design, whereby a set of stocks is selected from a large universe of stocks is extracted using a particular criterion and with a particular objective in mind. Low complexity portfolios are known to be highly diversified and are therefore of interest to investors.

The selection of low complexity portfolios, i.e. subsets of stocks belonging to a given basket, when approached from a classical optimization perspective is an extremely difficult problem to solve as it is a combinatorial problem. In fact, one way to define the problem is in combinatorial terms as follows:

Given a set of N securities, select a subset of M elements such that its complexity is minimum

In the case of the Dow Jones Industrial index, for example, N=30 and M=15 and the number of combinations to analyze is C(N,M) = 155.117.520. In the case of the NASDAQ 100, with N=100 and M=25 we obtain C(N,M) = 2.425 E+23! For large baskets containing, for example N=1000 securities, with a portfolio size of M=25 leads to C(N,M) = 4.764186253 E+49. Such cases are clearly beyond the reach of the most powerful supercomputers. Evidently, conventional optimization is an impractical approach and a different methodology must be devised.

Such an alternative exists and is called Portfolio Complexity Profiling (PCP). Extracting Low-Complexity portfolios even from huge stock ensembles takes minutes on a PC and with clever programming may even run in a very high frequency context. A Complexity Profile is a standard output of a complexity analysis. An example of a Complexity Profile of a 42-dimensional data set is shown below.

Complexity Profile of a 42-dimensional data set

Once the profile is available, it is easy to pick, for example a subset of 5 components such that they form a minimum complexity set. These are: 9, 42, 20, 2 and 11. The following is an example of a maximum complexity 4 element set: 34, 16, 32 and 7. What minimum complexity sets accomplish is the lowest degree of coupling between elements. The inverse may be said of high complexity sets. In the case of investment portfolios it is easy to grasp the significance of this.

The idea, at this point, is to identify classes of problems, or to transform classical problems in a way that they may be formulated in terms of minimizing (or maximizing) complexity. It would be of great interest to transform certain brachistochrone-type variational problems in this manner.

Established originally in 2005 in the USA, Ontonix is a technology company headquartered in Como, Italy. The unusual technology and solutions developed by Ontonix focus on countering what most threatens safety, advanced products, critical infrastructures, or IT network security - the rapid growth of complexity. In 2007 the company received recognition by being selected as Gartner's Cool Vendor. What makes Ontonix different from all those companies and research centers who claim to manage complexity is that we have a complexity metric. This means that we MEASURE complexity. We detect anomalies in complex defense systems without using Machine Learning for one very good reason: our clients don’t have the luxury of multiple examples of failures necessary to teach software to recognize them. We identify anomalies without having seen them before. Sometimes, you must get it right the first and only time!

0 comments on “On Combinatorial Optimization and Complexity

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: