Solving the market split problem via branch-and-cut Online publication date: Wed, 09-Dec-2009
by Haibo Wang, Gary Kochenberger, Bahram Alidaee, Mark Lewis
International Journal of Mathematical Modelling and Numerical Optimisation (IJMMNO), Vol. 1, No. 1/2, 2009
Abstract: In 1999 some researchers put forth some small but extremely difficult 0/1 problems derived from the market split (market sharing) problem originally proposed by a researcher in 1978. These problems, offered as a challenge to the optimisation community, motivated a series of research efforts trying several competing methodologies. As part of their testing, they employed both branch-and-bound and branch-and-cut algorithms and reported that branch-and-bound performed poorly and branch-and-cut did even worse. Based on this result they concluded that 'standard approaches to integer programming are not well suited for this class of problems'. Other researchers offered similar assessments. In this note we demonstrate that current state of the art branch-and-cut methods, unavailable earlier, is able to solve these problems to optimality. Then we also solve 40 numerical problems to optimality and also find that it works quite nicely on even larger problem instances.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Mathematical Modelling and Numerical Optimisation (IJMMNO):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook