OpenOpt Suite 0.38

I'm glad to inform you about new OpenOpt Suite quarter release 0.38, free (BSD license) Python-written software:

OpenOpt:

interalg can handle discrete variables (see MINLP for examples)
interalg can handle multiobjective problems (MOP)
interalg can handle problems with parameters fixedVars/freeVars
Many interalg improvements and some bugfixes
Add another EIG solver: numpy.linalg.eig
New LLSP solver pymls with box bounds handling

FuncDesigner:

Some improvements for sum()
Add funcs tanh, arctanh, arcsinh, arccosh
Can solve EIG built from derivatives of several functions, obtained by automatic differentiation by FuncDesigner

SpaceFuncs:

Add method point.symmetry(Point|Line|Plane)
Add method LineSegment.middle
Add method Point.rotate(Center, angle)

DerApproximator:

Minor changes

See also: FuturePlans.

Regards, D.

Physicist cuts airplane boarding time in half

I have always been fascinated with the airplane boarding problem.  I wish I was in the airline industry because I would love to tackle this problem.  I used to travel a lot for my job and I would marvel at how inefficient the time  it took to board an airliner.  My first inclination is to redesign the plane (and the airport jetway) to include exits at middle and rear of the plane to go along with the forward exit.  Yet I never put my ideas to paper and tried to calculate efficiency gains.  There have been a lot of ideas try to find the optimal boarding arrangement.  Would you believe that random boarding, i.e. Southwest Airlines, is a more optimal boarding procedure then the current row assignment method?

Yet a physicist from Fermilab, Jason Steffen, did have some interesting ideas to improve the existing airplane boarding procedures.  By using Monte Carlo simulations to measure efficiency and test his ideas he was able to improve airplane boarding by as much as half the time.  From the article, his methods were to using sections of window seats first but alternate aisles so passengers would not interfere with each other.

This is a very clever idea.  Yet I found one flaw that may not have been assumed in his study.  I've noticed that overhead space is a premium for passengers, especially for business travelers.  Business travelers often bring two carry-on bags.  These bags tend to fill up the overhead bins rather quickly.  When the overhead bins fill up then passengers have to search in the aisles looking for available space for their bags.  This creates a bottleneck and queues develop for the other boarding passengers.  It seems to me that Jason's study makes an assumption that all overhead bins would be available at time of boarding.  If in fact alternating rows are used in his model than overhead bins might become filled to capacity before passengers board and create more bottlenecks.  Its just one theory that would be worth investigating before Jason's procedures are implemented.

I applaud Dr. Steffen's studies and finds in the airplane boarding problem.  It is a fascinating problem as most of us have encountered airplane boarding from time to time.  For more information on his methods you can read about Jason's work airplane boarding, which is very fascinating, on his website.

Open Source replacements for Operations Research and Analytics Software

I was reading an article from Datamation on 70 Open Source Replacements for Small Business when I noticed a glaring omission.  Where are the software applications for Operations Research and Analytics?  So here is my best addendum to this article that should complete what small business should know about Open Source analytics productivity software.

Statistics and Computation

1.  R Project

Replaces: SAS, SPSS

R is a free and open source statistical computing environment that holds its own against some of the most established proprietary statistical environments.  R is available on all operating systems and is free for download.  R also has a community driven library of add-on packages that are also freely available and cover almost any statistical, mathematical, or optimization need.

Also a great reference manual for those switching from SAS to R is SAS and R: Data Management, Statistical Analysis, and Graphics




2.  RapidMiner

Replaces:  KnowledgeSEEKER

RapidMiner is a data mining software with a graphical front-end.  RapidMiner is suitable for most data mining and data transformation needs.


Mathematical Programming and Optimization

3.  GLPK

Replaces:  AMPL

GLPK is a GNU/free software linear programming software kit.  GLPK is intended for large-scale linear programming, mixed integer programming.  GLPK is based on GNU MathProg (or GMPL) which is considered a subset of the AMPL syntax.  GLPK also has its own solver.

4.  Symphony

Replaces: CPLEX, Gurobi

Symphony is a mixed integer linear programming solver developed under COIN-OR.  Symphony is a flexible framework that offers many methods to customize solver capabilities given problem sets.


5.  OpenSolver

Replaces:  Excel Solver

OpenSolver is a linear an integer optimizer alternative to the Excel Solver in Microsoft Excel.  OpenSolver is based on the COIN-OR CBC engine.  Unlike the Excel Solver there is no software limits to the size of the problem that can be solved.

OpenOpt Suite release 0.33

New release 0.33 of OpenOpt Suite is out:

OpenOpt:

• cplex has been connected
• New global solver interalg with guarantied precision, competitor to LGO, BARON, MATLAB's intsolver and Direct (also can work in inexact mode), can work with non-Lipschitz and even some discontinuous functions
  
• New solver amsg2p for unconstrained medium-scaled NLP and NSP

FuncDesigner:

• Essential speedup for automatic differentiation when vector-variables are involved, for both dense and sparse cases
• Solving MINLP became available
• Add uncertainty analysis
• Add interval analysis
• Now you can solve systems of equations with automatic determination is the system linear or nonlinear (subjected to given set of free or fixed variables)
• FD Funcs min and max can work on lists of oofuns
• Bugfix for sparse SLE (system of linear equations), that slowed down computations and demanded more memory
• New oofuns angle, cross
• Using OpenOpt result(oovars) is available, also, start points with oovars() now can be assigned easier

SpaceFuncs (2D, 3D, N-dimensional geometric package with abilities for parametrized calculations, solving systems of geometric equations and numerical optimization with automatic differentiation):

• Some bugfixes

DerApproximator:

• Adjusted with some changes in FuncDesigner

For more details visit http://openopt.org.

Science of Matchmaking

The science of matchmaking has seen serious growth in the last few years.  What exactly is so scientific about matchmaking anyway?  The goal of any commercial enterprise (and some public organizations) is to match products or services to the demand of consumers.  The idea of matching consumers with products and services is not new.  Matchmaking is essentially the business art of Marketing.  The science behind the matchmaking has seen the most advancement and improvement in recent time.  Generally speaking computing power has made the difference for the technologically leap forward.  Millions of points of observations and data can be sifted and combed with great ease as compared to even just a decade ago.  There is a scientific magic fiddling to the matchmaking phenomenon (sorry, bad Fiddler On The Roof pun). 


Mathematics of Matchmaking

I'm not sure I can cover all of the math behind the science of matchmaking.  I thought it best to describe an example with the company Netflix.  Netflix wants to make the decision process of selecting movies for its customers easier.  Netflix developed an algorithm to match customers' interests in movies.  In fact they even decided to farm out an improvement to the algorithm in a worldwide contest.  So how does the Netflix algorithm work?  There is a lot of math behind the algorithm but it essentially comes down to finding common features in the customer and movie data.  The customers give Netflix a clue to the features they want by ranking movies the customers enjoy.  This then becomes the dependent variables in the algorithm formulation.  Then the algorithms churn out likely matches based on common feature sets. 

Perhaps one of the best writings on this subject was given by Simon Funk on his blog about his Netflix Contest adventures.  Simon thought a creative way to find features would be to use the matrix transformation process of Singular Value Decomposition.  Traditionally Singular Value Decomposition was used in the microelectronics industry to improve digital signal processing.  Simon wrote up an easy solution for matchmaking movie features with the SVD method which spurned a wave of enthusiasm in the Netflix Contest entrants.


Finding feature sets is not exclusively in the realm of Linear Algebra.  There are also methods of clustering, regression, support vector machine, neural networks, bayesian networks, and decision trees just to name a few.  The science of matchmaking is closely related to artificial intelligence and is commonly referred to machine learning.  Machine learning is using algorithms and mathematical methods to evolve and generate behaviors from data in order to solve a problem.


Processing the Matchmaking Data

The science of matchmaking would not be complete without the data.  The advent of the internet has opened a lot of new enterprises that makes use of millions of data observations.  These internet companies have a lot of data to process in huge server arrays that will make even the ENIAC envious.  So how do these companies process all of this matchmaking data with their matchmaking algorithms?  The basic answer is to break it down into manageable chunks.  Perhaps no greater example is Google and their MapReduce methods.  MapReduce is a software framework process that takes a large computing need and breaks it down into a distributed network that is more manageable.  The first step in the MapReduce process is to Map the data.  The Map process is to organize and distribute the data to computing nodes, usually a huge cluster.  The Reduce process is to apply the algorithm or learning process to a node in the network and determine an answer to the data its given.  This essentially gives it a local optimum.  This process is iterated until a globally learned optimum is achieved.  This is a very cut and dry description but you get the idea.


The MapReduce software framework is proprietary to Google.  That has not stopped software enthusiasts.  An open source MapReduce method was created called Hadoop and is growing into a stronger user supported community.


So what can be used with the science of matchmaking?  Really anything the heart desires (okay, again, that was bad).  Amazon.com uses recommendation algorithms for its books and products.   Online dating sites (how appropriate) uses matchmaking methods for matching interested daters.  Search engines like Google uses matchmaking algorithms, known as PageRank, to match search keywords with websites.  As you can tell these types of enterprises are doing very well thanks to the science of matchmaking.



This article is part of the INFORMS Online blog challenge.  February's blog challenge is Operations Research and Love.

Operations Research and gerrymandering

INFORMS blog challenge for January involves Operations Research and politics.  While public debate on politics will never change perhaps one thing that can change is the involvement better decision making to solving some of the political discourse.

One area of politics is the topic of gerrymandering.  For those that are not familiar to gerrymandering it is the process of resetting electoral boundaries for voting purposes.  Gerrymandering is a hot topic around any election because it is usually the party in power controls the rights to reset the electoral boundaries.  This leads to an obvious advantage to the party as they can maintain a seat in a legislature with setting boundaries based on past voting behavior.

Operations Research can be a valuable asset to the process of redistricting.  In fact Operations Research has been very much involved in redistricting for at least 50 years.  Decisions to draw electoral lines can follow any number of constructions including demographics, population centers, municipality boundaries or industry types.  As information abounds more freely there is more opportunity to use it for decision making.  It seems every new census brings more available data.  The growth of the internet has allowed information to be available more openly.  Opportunities should grow in Operations Research to provide redistricting decision makers the information for informed analysis.

Perhaps one of the better uses of Operations Research could be the ethical context of the gerrymandering debate.  I have often heard it debated that Operations Research may have created the politically polarized country we have today.  The same tools of Operations Research could be used to allow transparency in the redistricting process.  It could be useful for citizens to know how probable or likely outcomes of elections based on redistricting suggestions.  Websites like OpenSecrets.org shows how money influences party affiliation and elections.   Perhaps similar websites can emerge on electoral districts and the legislation that helped create them.

The debate of gerrymandering will last for centuries I am sure.  I believe Operations Research can play a vital part in the debate.   Information is more open and easy to access than ever.  Let's use that to our best ability and help inform the voting electorate.

New OpenOpt/FuncDesigner quarterly release

New OpenOpt and FuncDesigner quarterly release is out: 0.32.

OpenOpt:
* New class: LCP (and related solver)
* New QP solver: qlcp
* New NLP solver: sqlcp
* New large-scale NSP solver gsubg. Currently it still requires lots of improvements (especially for constraints - their handling is very premature yet and often fails), but since the solver sometimes already works better than ipopt, algencan and other competitors it was tried with, I decided to include the one into the release.
* Now SOCP can handle Ax <= b constraints (and bugfix for handling lb <= x <= ub has been committed) * Some other fixes and improvements

FuncDesigner:
* Add new functions removeAttachedConstraints, min and max
* Systems of nonlinear equations: possibility to assign personal tolerance for an equation
* Some fixes and improvements (especially for automatic differentiation)

See also: Full Changelog, Some Applications, Future Plans

Shortest past algorithm solved by ants?

University of Syndey researchers are working on the next greatest optimization algorithms.  You would think they would be hunkered down in the math or computer science departments working with large multi-core processors.  Yet Chris Reid and Madeleine Beekman, working with David Sumpter of Uppsala Univ., are studying how ants solve the shortest path problem.  By studying how ants solve complex and dynamic problems such as getting food back to their colony they could unravel some new and innovative ways to solve routing problems.  The researchers published their results in Journal of Experimental Biology. 

There has already been some algorithms developed out of studying the ants.  One method is the Ant Colony Optimisation (ACO) algorithms.  Ants solve the complex problem of shortest path by communicating to other ants in the colony by pheromone trails.  Each ant leaves a pheromone trail as a signal back to a following ant.  The trail has a certain "optimal path" signal telling other ants the best way to get to the intended destination.

It would be really interesting to find out that the best shortest path algorithm might have been literally under our noses the entire time.  This will be an interesting study to follow for the Operations Research community.

OpenOpt release 0.31

New OpenOpt Suite release is out. This is free (license: BSD) and cross-platform (Linux, Windows, Mac etc) Python language modules for numerical optimization, automatic differentiation, solving systems of linear/nonlinear/ordinary differential equations, interpolation, integration etc.

OpenOpt 0.31:

• Lots of new NLP, NSP (nonsmooth) and GLP (global) solvers from nlopt have been connected
• New LP solver: pclp (very premature, but permissive license (BSD) and pure Python implementation)
• Some bugfixes (mostly wrt using sparse matrices) and code cleanup

FuncDesigner 0.21:

• New features: Integration, Translator
• Some speedup for functions evaluation, automatic differentiation, optimization problems with some fixed variables
• New parameter useSparse for optimization probs and automatic differentiation (sometimes autoselect works prematurely)
• Some bugfixes (mostly wrt using sparse matrices) and code cleanup

DerApproximator 0.21:

• Add parameter exactShape (prevents flattering operations on result)

Welcome to our homepage: http://openopt.org

Favorite Operations Research books from OR-Exchange

A while ago I posted a question on OR-Exchange about some of the favorite Operations Research books that OR-Exchange members like to reference.  I was rather pleased with the response.  Of course there are great books on the subject of Operations Research.  The best part of OR-Exchange allows for the community to vote up the favorites.  A lot of these books are just plain good to have in your desk drawer or in your work study.  I have to admit that I have not read all of these books.  So this gives me a good excuse to go get them and perhaps offer up some reviews in the future.

So in order of OR-Exchange votes here are the favorite Operations Research books.

1.  Applied Mathematical Programming by Bradley, Hax, Magnanti.

Applied Mathematical Programming

Also available at http://web.mit.edu/15.053/www/ but if you like it you might want to give it a purchase.


2.  Network Flows:  Theory, Algorithms, and Applications by Ahuja, Magnanti, Orlin
















3.  Linear Programming by Chvatal















4.  Model Building in Mathematical Programming by Williams

















5.  Introduction to Operations Research by Hillier, Lieberman















6.  50 Years of Integer Programming by Juenger, Liebling, Naddef, Nemhauser, Pulleyblank, Reinelt, Rinaldi, Wolsey















7.  The Traveling Salesman Problem: A Computational Study by Applegate, Bixby, Chvatal, Cook















8.  Tabu Search by Glover, Laguna














 9.  Prisoner's Dilemma by Poundstone















10.  Serious Play by Schrage















11.  The Fifth Discipline by Senge















12.  The Predictioneer's Game by Mesquita















13.  Optimization Algorithms for Networks and Graphs by Evans, Minieka

Open source solver for Excel

Thanks to a post by Michael Trick we find that the open source solver community has an new platform with Excel.  Although its not a replacement for Solver the OpenSolver does offer a lot of benefits that the existing Excel optimization platform does not perform.  OpenSolver is an extender of the existing Solver.  You will still need to use Solver to develop the model.  Yet OpenSolver can take over from there.  Some of the benefits include

• COIN-OR CBC optimization engine to perform the calculations
• Compatible to existing Solver models
• No artificial limits to the size of the problem (huge win here!)

Some of the disadvantages are that it does not solve non-linear models.  Also it does not run as a stand-alone plug-in as the current Solver.  I believe that OpenSolver is only developed for the Excel 2007 platform.  OpenSolver was developed by Andrew Mason and is licensed under GPL.  OpenSolver is free to distribute and download.

I'm hoping to give this a try soon.  I'm really encouraged by OpenSolver because I always thought the current Solver was very limited.  Looking forward to great things from OpenSolver.  For other ideas about Open Source solvers with spreadsheets be sure to look at Open Office Calc.

Kaggle hosting INFORMS 2010 Data Mining Contest

Kaggle is hosting the 2010 INFORMS Data Mining Contest.  The goal of this years INFORMS Data Mining Contest is to predict intra-day stock price movements.  All data and submission guidelines are provided on the Kaggle website.  Entries that are submitted are immediately scored and evaluated by an AUC calculation.  The leading AUC score by the end of the contest is going to be honored as the annual INFORMS meeting which is in Austin, Texas (Nov. 7-10).

There is already a lot of good discussions of modeling techniques.  Mark started off with a question on OR-Exchange about modeling methods for the INFORMS contest.   Since the data is a binary categorical target his preferred method was using Logistic Regression.  Mark provides example R code to provide collaborative input to the contest.  I followed suit and provided an IEORTools entry to the contest.  I used the same methods of Logistic Regression.  I also did some variable analysis using the rpart package in R to develop a decision tree.  After pulling some variables that were not significant I was able to get on the leaderboard with Mark.  The pictured leaderboard is of June 28. 

There is also some good discussion on the Kaggle website contest forum.  Posted on the forum one entrant suggested possible variables to use in a Logistic Regression model which is very beneficial.

I really like to see this collaborate effort to modeling.  This was one of the qualities I really enjoyed in the Netflix Prize.  I hope Kaggle and INFORMS continues to provide these fun and thought provoking contests.

OpenOpt release 0.29

New OpenOpt Suite release is out. This is free (license: BSD) and cross-platform (Linux, Windows, Mac etc) Python language modules for numerical optimization, automatic differentiation, solving systems of linear/nonlinear/ordinary differential equations etc. It is published quarterly since 2007, already has some essential applications and expected to become even more popular with Python release 3.3, where dynamic compilation will be implemented.

OpenOpt 0.29:
* Some minor bugfixes
* Some improvements for handling sparse matrices
ralg:
* Bugfix for problems with nonlinear equality constraints
* Major changes for problems with nConstraints>1

FuncDesigner 0.19:
* Some improvements for automatic differentiation
* New feature: attached constraints
* New feature: oosystem
* Now you can model & solve ODE systems

DerApproximator 0.19:
* Function get_d2
* Add new stencil

You can try it online via our Sage-server.
See also: Full Changelog, Future Plans

Railways improved by mobilizing Operations Research

A great article by PhysOrg.com on the values of Operations Research implemented in the Dutch railways. Improvements were able to be realized in train arrivals, passenger utilization in the cars, and operating profit. Many countries were impacted by the improved railway service all across Europe including Netherlands, Germany, and Switzerland among others.

The team that implemented the Operations Research strategies for the railway improvement project is lead by Christos Zaroliagis, a professor of Computer Science and Informatics at University of Patras. Christos was part of the team that earned the 2008 Edelman Prize from INFORMS for "The New Dutch Timetable: The O.R. Revolution." The team of the ARRIVAL project is a consortium of several researchers from many European countries.

This is a great example of Operations Research in practice and how OR continues to improve the operations and lives of organizations. I really like sharing stories like this because I don't feel they often get their due respect. There is a lot of research and planning in the background of a good research project, let alone Operations Research, that does not get noticed.

New IEOR Tools contributor - developer of OpenOpt

I would like to welcome Dmitrey, developer of the open source optimization software suite, OpenOpt and maintainer of OpenOpt.org. Dmitrey will contribute from time to time about OpenOpt and software releases.

When I started the IEOR Tools blog I wanted it to be a forum for discussion, evaluation, and peer review of the tools available to the Industrial Engineering and Operations Research community. I believe that the best opportunity for continued development and research of tools of the trade is in the Open Source community. I hope that this blog can be a conduit for continued development and opportunity.

I'm excited for the contributions that Dmitrey will provide with OpenOpt and other open source developments.

GLPK 4.40 released today

Andrew Makhorin, lead developer of the GNU Linear Programming Kit project, released the latest version of GLPK 4.40 today. Some of the following enhancements include...

• New API routines. Mostly with graphs.
• New branching and MIP heuristics
• And of course some bug fixes

As described by Andrew, GLPK is intended for solving large-scale linear programming, mixed integer linear programming, and related problems. GLPK is written in ANSI C and is organized as a callable library.

IEOR Tools also had a feature on GLPK on how to use it in the Windows environment as IEOR Tools tutorial: Using GLPK in Windows.

IBM to open health analytics center in Dallas

IBM is opening a Health Analytics Solution Center in Dallas, TX as announced by the Dallas Morning News. It will employ 100 analytics and technology consultants in the regional area.

This is an interesting deal for Dallas as it may have ramifications for EDS and Perot Systems, Dell's new aquisition, which are both based in the Dallas area.

Yet from an Operations Research and Analytics point of view the most interesting excerpt from the article is this...

IBM did not specify how much it would invest in Dallas, but it plans to invest more than $10 billion companywide to build its capabilities around business analytics. As part of the plan, the company expects to retrain or hire up to 4,000 new analytics consultants globally.

IBM's Business Analytics and Optimization segment is expected to grow at around 10 percent this year, and to between 15 and 20 percent from 2010 onward, accounting for more than $2 billion in sales in 2010, Haswell said.

The field of Analytics and Operations Research is definitely growing which is a good sign. If IBM's projections are accurate than they could be perhaps the premier Analytics and Operations Research company worldwide. This is a trend by IBM that was seen early this year as it acquired ILOG. As a whole for Operations Research and Business Analytics it seems this is a good time to be in the field.

Operations Researcher predicts Yankees to win World Series

Bruce Buckiet of NJIT predicts that the Yankees are going to win the World Series as covered by Science Daily. Bruce's model predicts a 70 percent chance that the Yankees will beat the Phillies. You can follow Bruce's predictions on his website http://m.njit.edu/~bukiet/baseball/playoffs09.htm. Bruce has game to game predictions for the best of seven series including the probably outcomes of each possible starting pitcher.

Baseball is no stranger to Operations Research. Michael Trick is a member of the Sports Scheduling Group that assists MLB in scheduling their games for the past three years.

IBM to use Operations Research for war on terror

According to a report from BusinessWeek IBM has won a contract with the U.S. Special Operations Command to apply their analytical analysis. There is a long standing of tradition of the U.S. military using Operations Research to help optimize its operations, as the article alludes.

More interestingly that this article demonstrates is that IBM is increasingly becoming a go-to company for Operations Research services. This no doubt is an objective of IBM as a whole with their recent ILOG aquisition. I would be willing to bet that there will be more interesting news from IBM in the future.

The perils of a data-driven culture at Google

Techradar.com has an article about Google's culture of being data-driven decision making and its affect on the visual and user experience teams. In fact it had such a big affect on the former Visual Design Lead, Douglas Bowman, he left the company. Techradar interviews Google's Director of User Experience Irene Au. Irene explains the importance of data and how Google's culture emphasizes experimentation which may rub some designers the wrong way.

I've never really thought of being a data-driven culture could have its drawbacks. As an analyst I see only the merits of having data. But there are people who like to think way outside the box and not agree with me. This could be a good thing to learn as an Operations Research practitioner. There are definitely some soft-skills we could learn to help implement our data-driven ideas in our respective organizations.

There is one thing that I didn't agree with from Irene Au in the article. Here's here quote from the article...

"That's why we have a significant team of designers who bring unique skills to the teams they work with. Data informs decision-making but it's less useful for conceiving and building conceptually new directions. It's most useful for optimising and refining an established concept."

While I agree it's good to get other people's ideas to the table I do not agree on how data is less useful for conceiving and building new concepts. Maybe I'm taking her a little out of context but I could argue how data can help shape new ideas of thinking. I've done that a lot in my career. In fact the whole field of data mining pretty much defines this as their objective.

I definitely think there could be things to learn from examining the cultures of the organizations we work. Implementing Operations Research ideas and recommendations can be difficult. Perhaps it takes examining our organization and finding how others define optimality.