LocalSolver


LocalSolver wins against MILP, MIQP, and CP solvers on QAPLIB // 01 Oct 2013

The Quadratic Assignment Problem (QAP) is one of fundamental combinatorial optimization problems in the branch of optimization or operations research, originally coming from facility location applications. Indeed, the problem models the following real-life problem. There are a set of n facilities and a set of n locations. For each pair of locations, a distance is specified and for each pair of facilities a weight or flow is specified (e.g., the amount of supplies transported between the two facilities). The problem is to assign all facilities to different locations with the goal of minimizing the sum of the distances multiplied by the corresponding flows. Intuitively, the cost function encourages factories with high flows between each other to be placed close together. The problem statement resembles that of the assignment problem, except that the cost function is expressed in terms of quadratic inequalities, hence the name. For more details, we invite the reader to have a look to the QAPLIB webpage.

A few months ago, a lot of discussions were raised by a paper presenting an attempt in using the power of quantum computing systems (actually D-Wave) to solve combinatorial optimization problems. The main benchmark used by the authors of this paper is the Quadratic Assignment Problem (QAP).

Beyond its computational hardness, this problem is in essence nonlinear: the decisions are boolean (0-1) and the objective contains quadratic terms (some products of decision variables like "x_i * x_j"). Then, it is not really suited to model and solve using Mixed-Integer Linear Programming (MILP) solvers, as well as using Constraint Programming (CP) solvers. One can imagine that Mixed-Integer Quadratic Programming (MIQP and MIQCQP) solvers could be better in solving these kinds of problems. Unfortunately, it is not the case: some evidences of the bad results of MILP, MIQP, and CP solvers are given here. In this article, the main reason invoked to explain why these general-purpose model-and-run solvers provide bad solutions to QAP instances is the following: they not only try to find good feasible solutions, but they spend a fair amount of time trying to prove optimality. This explanation is not clear since proving optimality of a solution implies you have this solution, which is not the case here. Worst, on many instances, these solvers do not find any feasible solution after hours of computation.

The reason why MILP solvers are not able to tackle QAP instances effectively is rather simple. Since the model is inherently quadratic (that is, nonlinear), the linear relaxation is not good. In particular not enough to cut the exponential tree search, as well as to find feasible solutions using rounding heuristics. Relying on several complementary optimization techniques embedded in a global neighborhood strategy, LocalSolver is able to adapt: if the linear relaxation brings nothing, then LocalSolver don't use it. Instead, LocalSolver follows a local search approach based on an incremental, direct evaluation of the constraints as well as of the objective.

Now, have a look to the QAP model written in LocalSolver, or more precisely using the modeling and scripting language (LSP) coming with LocalSolver. No need of linearizing when using LocalSolver, the QAP can be modeled in a straightforward way, as follows:

function model() {
  x[i in 1..n][j in 1..n] <- bool();
   
  for[i in 1..n]
    constraint sum[j in 1..n](x[i][j]) == 1;
   
  for[j in 1..n]
    constraint sum[i in 1..n](x[i][j]) == 1;
   
  obj <- sum[i in 1..n][j in 1..n][k in 1..n][l in 1..n]
             ( A[i][j] * B[k][l] * x[i][k] * x[j][l] );
   
  minimize obj;
}

Then we present the results obtained by LocalSolver 3.1 on the QAPLIB. The results are compared to the state of the art, obtained through dedicated, highly-tuned approaches combining different optimization techniques.

  • Lower objective is better
  • 5 minutes of running time for LocalSolver (and not for the state of the art)
  • Standard computer: Intel Core i7-820QM (4 cores, 1.73 GHz, 6 GB RAM, 8 MB cache)
  • Default settings
  • No need of linearizing or tuning in LocalSolver: the QAP model is written as is
Instances    n     Decisions  Expressions   LocalSolver 3.1  State of the art  Gap 
                                                                                   
esc32a       32    1,024      124,299       136              130               5%  
esc32b       32    1,024      180,872       188              168               12% 
esc32c       32    1,024      219,153       642              642               0%  
esc32d       32    1,024      150,922       200              200               0%  
esc32e       32    1,024      11,148        2                2                 0%  
esc32g       32    1,024      16,138        6                6                 0%  
esc32h       32    1,024      235,791       444              438               1%  
kra30a       30     900       288,166       92,130           88,900            4%  
kra30b       30     900       288,166       93,020           91,420            2%  
kra32        32    1,024      328,558       94,440           88,700            6%  
lipa30a      30     900       732,736       13,399           13,178            2%  
lipa30b      30     900       731,258       177,255          151,426           17% 
lipa40a      40    1,600      2,374,581     31,998           31,538            1%  
lipa40b      40    1,600      2,368,797     565,314          476,581           19% 
lipa50a      50    2,500      5,885,226     62,859           62,093            1%  
lipa50b      50    2,500      5,876,130     1,431,681        1,210,244         18% 
nug30        30     900       510,877       6,238            6,124             2%  
sko42        42    1,764      2,078,709     16,282           15,812            3%  
sko49        49    2,401      3,817,588     24,146           23,386            3%  
ste36a       36    1,296      435,141       10,488           9,526             10% 
ste36b       36    1,296      435,628       18,066           15,852            14% 
ste36c       36    1,296      435,822       8,612,782        8,239,110         5%  
tai30a       30     900       745,196       1,914,966        1,818,146         5%  
tai30b       30     900       484,316       638,762,469      637,117,113       0%  
tai35a       35    1,225      1,384,849     2,515,194        2,422,002         4%  
tai35b       35    1,225      737,819       287,227,702      283,315,445       1%  
tai40a       40    1,600      2,382,379     3,284,344        3,139,370         5%  
tai40b       40    1,600      1,341,640     689,131,580      637,250,948       8%  
tai50a       50    2,500      5,905,491     5,230,902        4,938,796         6%  
tai50b       50    2,500      2,911,505     481,156,669      458,821,517       5%  
tho30        30     900       379,599       153,286          149,936           2%  
tho40        40    1,600      976,311       249,326          240,516           4%  
wil50        50    2,500      5,387,864     49,526           48,816            1%  
                                                                                   
average                                                                        5%

The LSP file and the QAP instances are available in our Example Tour. You can download a ZIP file containing all files here. If you need a trial license to run the benchmark: create your account in a minute, download LocalSolver for your preferred platform, and follow the instructions to ask for a free full-version LocalSolver Trial license.


Other news

2017

New release: LocalSolver 7.0 // 02 May 2017

LocalSolver 7.0 offers new features and performance improvements for a bunch of combinatorial and numerical problems. Try it for free now!

LocalSolver is hiring an Optimization Engineer // 07 Apr 2017

Passionated about mathematical optimization and computer programming? Join a small, fast-growing tech company to change the game in the world of optimization.

Interested in doing an internship at LocalSolver? // 15 Jan 2017

Are you passionate about Operations Research and Mathematical Optimization? Have a look to our internship offers for the year 2017. Then join us!

2016

Welcome to our new clients // 31 Oct 2016

Several organizations have recently chosen LocalSolver to solve their most challenging optimization problems. Discover companies and institutions who trust us.

New release: LocalSolver 6.5 // 29 Jul 2016

LocalSolver 6.5 offers big performance improvements for routing & scheduling problems, as well as for almost-linear problems. Check it out for free now!

Solving a problem with 8 million boolean decisions // 15 Jun 2016

This is the number of binary decisions of the supply chain optimization problem solved in minutes by Pasco Shikishima and Future Architect, using LocalSolver.

We search for a business developer // 16 Mar 2016

Interested in selling mathematical software? Interested in joining a fast-growing tech company? Have a look to this open position at Innovation 24 & LocalSolver.

Welcome to our new clients // 01 Mar 2016

Several organizations have recently chosen LocalSolver to solve their most challenging optimization problems. Discover companies and institutions who trust us.

New release: LocalSolver 6.0 // 09 Feb 2016

LocalSolver 6.0 offers new unique, powerful features: solve routing & scheduling problems at hand using list variables, plug external functions easily to your optimization models, analyze efficiently why your model is infeasible, ...

LocalSolver sponsors ROADEF 2016 // 03 Feb 2016

LocalSolver 6.0 will be unveiled at ROADEF 2016, the annual congress of the French Operations Research Society, in Compiègne, 10-12th February 2016.

LocalSolver sponsors ORBEL // 25 Jan 2016

LocalSolver is glad to sponsor ORBEL30, the 30th annual conference of Belgian Operationnal Research Society at UCL-CORE, January 28-29, 2016.

2015

FICO Kaggle Challenge: Santa's Stolen Sleigh // 10 Dec 2015

The analytics company FICO has launched an optimization challenge on Kaggle: Santa's Stolen Sleigh. Julien Darlay, from LocalSolver R&D, proposes a simple optimization approach based on LocalSolver to solve this problem nearly optimally.

LocalSolver at PGMO DAYS 2015 // 25 Sep 2015

LocalSolver will be at PGMO DAYS 2015. Discover how LocalSolver solves a real-life network optimization problem with 14,000 nodes and 180,000 edges in minutes.

LocalSolver sponsors OR2015 in Vienna // 16 Jul 2015

LocalSolver sponsors OR2015 in Vienna. Come on our booth to meet the us and discover the big novelties released in LocalSolver 5.5 version!

LocalSolver 5.5 is released // 11 Jul 2015

Have a look to this new version which offers new modeling features, as well as performance improvements for a bunch of hard problems.

Welcome to our new clients // 03 Jul 2015

Several organizations have newly chosen LocalSolver to solve their most challenging optimization problems. Discover the corporations and institutions who trust us.

LocalSolver sponsors EURO 2015 // 30 Jun 2015

LocalSolver sponsors the biggest OR event in Europe: EURO 2015. Come on our booth to meet the us and discover the big novelties coming in LocalSolver 5.5 version!

LocalSolver at MIC 2015 // 15 Apr 2015

Julien Darlay will give a plenary talk at 11th Metaheuristics International Conference (MIC 2015) in Agadir, Morocco, from the 7 to 10th June 2015.

Applications of Optimization 2015 // 31 Mar 2015

Frédéric Gardi will give a talk at the Applications of Optimization 2015 workshop organized by the Danish Operations Research Society (DORS).

New release: LocalSolver 5.0 // 19 Jan 2015

LocalSolver 5.0 is out. Have a look to this new version which offers new modeling features, as well as performance improvements for a bunch of hard problems.

Je suis Charlie // 11 Jan 2015

We are shocked and depressed by the terrible events that occurred in recent days in France. We have a thought for the victims and their families. #JeSuisCharlie

2014

Welcome to our new clients // 20 Dec 2014

Several organizations have newly chosen LocalSolver to solve their most challenging optimization problems. Discover the corporations and institutions who trust us.

LocalSolver hires: welcome to Clément! // 10 Nov 2014

LocalSolver hires: our team is pleased to welcome Clément Pajean, graduated from ENSTA ParisTech, one of the French "Grandes Ecoles".

Plugging LocalSolver to the R language // 12 Aug 2014

Our Polish partner and reseller WLOG Solutions has developed the localsolver package for the R language.

New release: LocalSolver 4.5 // 21 Jul 2014

We invite all our users to install LocalSolver 4.5. This new version offers new modeling features, as well as performance and numerical precision improvements.

LocalSolver sponsors OR 2014 // 25 Jun 2014

LocalSolver sponsors OR 2014 in Aachen in Germany, from 2 to 5th September 2014. Come to our booth to discover LocalSolver and meet the team!

LocalSolver at EUROPT 2014 // 07 May 2014

LocalSolver will be presented at the 12th EUROPT Workshop on Advances in Continuous Optimization, July 10-12 2014, in Perpignan, France.

LocalSolver welcomes new clients // 23 Apr 2014

Several organizations have recently chosen LocalSolver as premier mathematical optimization solver: discover them!

LocalSolver at SMAI-MODE 2014 // 30 Mar 2014

The team was invited to present LocalSolver at the 2014 workshop on Mathematics for Optimization and Decision (MODE), part of the French Society for Applied and Industrial Mathematics (SMAI), March 26-28th 2014 in Rennes, France.

LocalSolver sponsors INFORMS 2014 // 14 Mar 2014

The LocalSolver team will have a booth and talk at INFORMS 2014 in Boston, Massachusetts. Come to meet us.

LocalSolver at Paris Machine Learning Meetup // 12 Mar 2014

LocalSolver team was recently invited to the Paris Machine Learning Meetup organized by Igor Caron, to talk about large-scale optimization related to machine learning.

Thierry Benoist's Habilitation // 06 Mar 2014

Thierry Benoist, member of the LocalSolver team, will defend his Habilitation Thesis on March 11th 2014 at Ecole des Mines de Nantes (France).

LocalSolver sponsors JFPC-JIAF 2014 // 01 Mar 2014

LocalSolver sponsors the French Meeting on Constraint Programming and Articficial Intelligence, from 11th to 13th June 2014 in Angers, France.

LocalSolver at ROADEF 2014 // 27 Jan 2014

LocalSolver will be at ROADEF 2014, the annual congress of the French Operations Research Society, in Bordeaux from 26th to 28th February. Come to meet the team!

LocalSolver at Workshop ORO 2013 // 03 Jan 2014

Frédéric Gardi was invited as plenary speaker to the ORO Workshop in Nantes. He spoke about his research line on "how industrializing local search-based OR software?" which leads to the genesis of LocalSolver.

2013

Merry Christmas: LocalSolver 4.0 is released! // 25 Dec 2013

We wish a Merry Christmas to all our clients and users: LocalSolver 4.0 is out! This new version allows to tackle large-scale mixed-variable non-convex optimization problems.

Frédéric Gardi's Habilitation // 25 Nov 2013

Frédéric Gardi, member of the LocalSolver team, has defended his Habilitation Thesis on November 25th 2013 at Université Pierre et Marie Curie (Paris 6, Jussieu).

Innovation 24, the parent company of LocalSolver // 17 Oct 2013

Discover Innovation 24, the parent company of LocalSolver, also offering expert services in business analytics and operations research.

LocalSolver wins on some of the hardest MIPLIB instances // 15 Oct 2013

LocalSolver wins against both Gurobi and IBM ILOG Cplex on some of the hardest MIPLIB instances. Have a look!

LocalSolver wins against MILP, MIQP, and CP solvers on QAPLIB // 01 Oct 2013

While MILP, MIQP or CP solvers are out of scope, LocalSolver reaches state-of-the-art results within 5 minutes on Quadratic Assignment Problem.

Welcome to our new clients // 24 Sep 2013

We welcome our new clients: Hitachi, MédiaTransports (Publicis), NIES, Nanjin University.

LocalSolver tutorial in IFORS Newsletter // 23 Sep 2013

IFORS is the International Federation of Operational Research Societies. A tutorial on LocalSolver appears in the last IFORS Newsletter.

Welcome to our new partners // 19 Sep 2013

We are glad to welcome new LocalSolver partners.

LocalSolver at the Summer School "Francesco Turco" 2013 // 10 Sep 2013

Our Italian partner LAC is sponsoring of Summer School "Francesco Turco" 2013. LocalSolver will be presented during the event.

LocalSolver at OR55 in Exeter (UK) // 13 Aug 2013

LocalSolver is sponsoring OR55 in Exeter (UK), 3-5th September 2013. Come to our booth to meet the team!

LocalSolver at OR 2013 in Rotterdam // 30 Jul 2013

LocalSolver is sponsoring OR 2013 in Rotterdam, 3-6th September 2013. Come to our booth to meet the team!

LocalSolver 3.1 is out // 28 Jun 2013

LocalSolver 3.1 is now available. Enjoy it!

LocalSolver at EURO-INFORMS 2013 // 15 Jun 2013

LocalSolver sponsors EURO-INFORMS 2013 in Rome. Don't miss the presentations made by the team!

Speed dating with LocalSolver // 06 Jun 2013

A nice post about LocalSolver by the OR blogger Marc-André Carle.

LocalSolver at ECCO 2013 // 30 Apr 2013

Don't miss the presentation of LocalSolver at ECCO 2013 in Paris.

Welcome to our new clients // 02 Apr 2013

We welcome our new clients: Air Liquide, Armée de Terre, Fujitsu.

LocalSolver at ROADEF 2013 // 18 Feb 2013

Retrieve all presentations about LocalSolver given at ROADEF 2013.

2012

LocalSolver 3.0 is out // 03 Dec 2012

Want better solutions faster? Download LocalSolver 3.0 now!

Customers & Partners // 14 Nov 2012

Welcome to our new customers & partners!

LocalSolver in Japanese // 08 Oct 2012

LocalSolver now speaks Japanese thanks to our partner MSI.

Logistics & Automation Consulting chooses LocalSolver // 24 Sep 2012

The Italian company Logistics & Automation Consulting (LAC) chooses LocalSolver as mathematical programming partner.

LocalSolver now in OR education // 10 Sep 2012

LocalSolver appears as complement of classical MIP and CP solvers in OR courses in French universities and high schools.

LocalSolver at ISMP 2012 // 15 Aug 2012

LocalSolver was at ISMP 2012, the world congress in mathematical programming, held in Berlin. Here are the (provocative!) slides.

Customers & Partners // 02 Aug 2012

Welcome to our new customers & partners!

New release: LocalSolver 2.1 // 06 Jul 2012

LocalSolver 2.1 was released the 6th July 2012. All users of LocalSolver 2.0 can take advantage of this new version for free.

LocalSolver at EURO 2012 // 27 Jun 2012

LocalSolver is a sponsor of EURO 2012 in Vilnius (8-11 July). Come on exhibition booth #20 to discover LocalSolver and the team!

Last results on Google ROADEF Challenge // 12 Jun 2012

We have submitted a LocalSolver-based solution for the final round of Google ROADEF Challenge. Here are given our results.

LocalSolver in Optimization Days 2012 // 04 May 2012

LocalSolver was presented in Optimization Days 2012 in Montreal. You can download the slides of the presentation.

Frédéric Gardi wins the 2012 Robert Faure Prize // 16 Apr 2012

This prize is awarded every 3 years by the French OR society to a worthy young researcher. This is the first time it has been awarded to an engineer working in industry and not to an academic.

LocalSolver at ROADEF 2012 // 08 Apr 2012

LocalSolver sponsorizes ROADEF 2012 congress. LocalSolver 2.0 will be presented in industrial semi-plenary session. Come to discover it!

LocalSolver available on Mac // 26 Mar 2012

Good news for Apple fans: LocalSolver is now available on Mac.

Official launch of LocalSolver 2.0 at Bouygues Headquarters // 11 Mar 2012

LocalSolver team invites you to the official launch of the commercial version of its new-generation solver: Tuesday March 13 2012.

LocalSolver tackles B instances on Google ROADEF Challenge // 24 Feb 2012

LocalSolver is able to solve some of the ultra-large instances from set B. Here are given some results.

LocalSolver succeeds on Google ROADEF Challenge // 08 Feb 2012

Ranked 25th among 82 teams from 33 countries, LocalSolver is the sole math programming solver qualified for the final round.

LocalSolver at Aussois 2012 // 09 Jan 2012

LocalSolver was recently presented at 16th Aussois Combinatorial Optimization Workshop.

2011

LocalSolver in 4OR journal // 01 Sep 2011

The first paper on LocalSolver has been published in 4OR, a Quarterly Journal of Operations Research published by Springer.

Contact us - Disclaimer - Copyright 2017 Innovation 24