Friday, October 21, 2011

Interfacing Haskell to the Concorde solver for Traveling Salesperson Problem

The Traveling Salesperson Problem (TSP) is a famous optimization problem with applications in logistics, manufacturing, and art. In its planar form, we are given a set of "cities", and we want to visit each city while minimizing the total travel distance.

Finding the shortest possible tour is NP-hard, and quickly becomes infeasible as the number of cities grows. But most applications need only a heuristically good solution: a tour which is short, if not the shortest possible. The Lin-Kernighan heuristic quickly produces such tours.

The Concorde project provides a well-regarded collection of TSP solvers. I needed TSP heuristics for a Haskell project, so I wrote a Haskell interface to Concorde's Lin-Kernighan implementation. Concorde provides a C library, but it's far from clear how to use it. Instead I chose to invoke the linkern executable as a subprocess.

The core of the Haskell interface looks like this:

tsp
:: Config -- provides various configurable parameters
-> (a -> R2) -- gives the rectangular coordinates of each point
-> [a] -- list of points to visit
-> IO [a] -- produces points permuted in tour order

tsp lets you represent the points to visit using any type you like. You just provide a function to get the coordinates of each point. The Config parameter controls various aspects of the computation, including the time/quality tradeoff. Defaults are provided, and you can override these selectively using record-update syntax. All considered it's a pretty simple interface which tries to hide the complexity of interacting with an external program.

Visualizing a tour

Here's a example program which computes a tour of 1,000 random points. We'll visualize the tour using the Diagrams library.

import Diagrams.Prelude
( Diagram , Point(P), fillColor , lineWidth
, translate, circle , fromVertices, lightgrey )

import Diagrams.Backend.Cairo.CmdLine
( Cairo, defaultMain )

import Data.Colour.SRGB ( sRGB )
import Data.Colour.RGBSpace ( uncurryRGB )
import Data.Colour.RGBSpace.HSV ( hsv )

import qualified Algorithms.Concorde.LinKern as T

import Control.Monad
import Data.Monoid
import System.Random

tsp takes a list of points and a function to extract the coordinates of a point. Our points are just the coordinates themselves, so we pass the identity function.

type R2 = (Double, Double)

findTour :: [R2] -> IO [R2]
findTour = T.tsp cfg id where
cfg = T.defConfig { T.verbose = True }

The tour is drawn as a loop of line segements. We also shade the interior of this polygon.

diaTour :: [R2] -> Diagram Cairo R2
diaTour xs@(x:_) = sty . fromVertices $ map P (xs ++ [x]) where
sty = fillColor lightgrey . lineWidth 10

Each point visited by the tour is drawn as a circle, with hue indicating its position in the tour.

diaPoints :: [R2] -> Diagram Cairo R2
diaPoints = mconcat . map circ . zip [0..] where
n = fromIntegral numPoints
circ (i,p) = translate p . fillColor color $ circle 40
where color = uncurryRGB sRGB (hsv (360*i/n) 1 1)

Now we put it all together. Note that linkern uses Euclidean distances rounded to the nearest integer. So we need coordinates with fairly large magnitudes. Picking values between 0 and 1 won't work.

numPoints :: Int
numPoints = 1000

main :: IO ()
main = do
let rnd = randomRIO (0,10000)
points <- replicateM numPoints (liftM2 (,) rnd rnd)
tour <- findTour points
defaultMain (diaPoints tour `mappend` diaTour tour)

We run it like so:

$ export PATH=~/concorde-031219/LINKERN:$PATH
$ runhaskell tour.lhs -o out.pdf
$ xpdf out.pdf

The computation takes about 2 seconds on my machine. And the output looks like this:

You can download this post as a Literate Haskell file and run the above program. You'll need to install the concorde and diagrams packages.

The source for the concorde Haskell package includes a more full-featured version of this example.

34 comments:

  1. Nice article, thanks for the information. It's very complete information. I will bookmark for next reference
    jaring futsal | jaring golf | jaring pengaman proyek |
    jaring pengaman bangunan | jaring pengaman gedung
    http://www.jual-jaring.blogspot.com/
    http://www.agen-jaring.blogspot.com/
    http://www.pancasamudera-safetynet.blogspot.com/
    http://www.toko-jaring.blogspot.com/
    http://www.pusat-jaring.blogspot.com/
    http://jualjaringpengaman.blogspot.com/
    https://pancasamudera.wordpress.com/
    https://pasangjaringfutsal.wordpress.com/
    https://jualtambangmurah.wordpress.com/
    https://tokojaring.wordpress.com/
    https://jualjaringfutsal.wordpress.com/
    https://jaringfutsal.wordpress.com/


    ReplyDelete
  2. شركة نورالعمران بحفرالباطن
    0506630089
    شركة مكافحة حشرات بحفرالباطن افضل شركة مكافحة حشرات بحفرالباطن افضل شركة مكافحة وابادة الصراصير والقوارض والنمل الابيض والعتة والوزغ والنمل الاسود والفيران بحفرالباطن
    https://hafralbatin88.000webhostapp.com/0506630089-%D8%B4%D8%B1%D9%83%D8%A9-%D9%85%D9%83%D8%A7%D9%81%D8%AD%D8%A9-%D8%AD%D8%B4%D8%B1%D8%A7%D8%AA-%D8%B5%D8%B1%D8%A7%D8%B5%D9%8A%D8%B1-%D9%81%D8%A6%D8%B1%D8%A7%D9%86-%D8%A8%D8%AD%D9%81%D8%B1

    https://hafralbatin88.000webhostapp.com/0506630089-%D8%B4%D8%B1%D9%83%D8%A9-%D9%85%D9%83%D8%A7%D9%81%D8%AD%D8%A9-%D8%AD%D8%B4%D8%B1%D8%A7%D8%AA-%D8%B5%D8%B1%D8%A7%D8%B5%D9%8A%D8%B1-%D9%81%D8%A6%D8%B1%D8%A7%D9%86-%D8%A8%D8%AD%D9%81%D8%B1

    https://hafralbatin88.000webhostapp.com/0506630089-%D8%B4%D8%B1%D9%83%D8%A9-%D9%85%D9%83%D8%A7%D9%81%D8%AD%D8%A9-%D9%88%D8%A7%D8%A8%D8%A7%D8%AF%D8%A9-%D8%A7%D9%84%D9%81%D8%A6%D8%B1%D8%A7%D9%86-%D9%88%D8%A7%D9%84%D9%82%D9%88%D8%A7%D8%B1

    ReplyDelete
  3. 0530921151
    منسقة ومتعهدة صبابات قهوة الضيافة ،متعهدة افراح ومناسبات بحفرالباطن والمنطقة الشرقية متعهدة تصوير حفلات الزفاف بحفرالباطن متعهدة مناسبات وافراح واعراس بحفرالباطن متعهدة كوش ومداخل بحفرالباطن متعهدة تصوير حفلات الزفاف بحفرالباطن متعهدة مناسبات واعياد وحفلات الزواج والمناسبات بحفرالباطن


    https://redahafralbatin.wordpress.com/


    http://www.ar-kan7.com/%D9%85%D9%86%D8%B3%D9%82%D9%87-%D8%A7%D9%81%D8%B1%D8%A7%D8%AD-%D8%A8%D8%AD%D9%81%D8%B1-%D8%A7%D9%84%D8%A8%D8%A7%D8%B7%D9%86/

    ReplyDelete
  4. من خلال التواصل مع موقع مكتبتك يمكنك الحصول علي العديد من الانواع المختلفة للتقنيات منها خدمة توفير المراجع التي يدعم بها الباحثين ابحاثهم كما يتواجد ايضا خدمة اعداد الاطار النظري للبحث العلمي

    ReplyDelete
  5. الحشرات من الأشياء التي ينزعج العديد على إثرها وايضاًً هي شيء يسبب الرهاب للكثير وهي من اهم الأشياء التي ينتج عن وجودها خسائر كثيرة، وعلل تواجدها أسباب كثيرة كالمكان والنظافة وأحوال المناخ والطقس فالحشرات تتغير وفق درجة السخونةشركة مكافحة حشرات بالطائف
    شركة رش مبيدات بالطائف
    المبيدات الحشرية الكيميائية
    شركة الانوار لرش المبيدات

    ReplyDelete
  6. Packers And Movers Bangalore Local Household Shifting Service, Get Free Best Price Quotes Local Packers and Movers in Bangalore List, Compare Charges, Save Money
    And Time @ Packers And Movers Bangalore

    ReplyDelete
  7. The Quickbooks Data Transfer Utility allows QuickBooks users to quickly and easily transfer list and transaction data from one QuickBooks file to another QuickBooks file.

    ReplyDelete
  8. https://crackknow.com/clip-studio-paint-ex-crack-keygen-download/
    Clip Studio Paint Pro 2021 Crack creates your clips and adjusts and levels them automatically. Here you will have a kit for 3D devices. It has an extensive repository of objects and 3D designs. That serves the real purpose of art. It is difficult to measure something and organize substitute positions. Its sophisticated techniques facilitate artificial measurement and position execution.

    ReplyDelete
  9. https://crackpropc.com/avast-cleanup-crack/
    Avast Cleanup Activation Key differs from the previous edition, it’s custom, basic and standard style. As you did the cleaning, PC Optimization is contingent on the type of scanning and also enough full time.

    ReplyDelete
  10. https://muzamilpc.com/vsdc-video-editor-crack/
    VSDC Video Editor Crack Key allows you to gain the videos of your desktop. It can merge and cut the video files and use the filters and wondrous effects to make it expert.

    ReplyDelete
  11. https://newcrack.org/camtasia-studio-crack-keygen/
    Cracked Here is a useful place where you can easily find Activators, Patch, Full version software Free Download, License key, serial key, keygen, Activation Key and Torrents.
    Get all of these by easily just on a single click.

    ReplyDelete
  12. https://oceancrack.com/mailbird-pro-license-key-2020/
    Cracked Here is a useful place where you can easily find Activators, Patch, Full version software Free Download, License key, serial key, keygen, Activation Key and Torrents.

    ReplyDelete
  13. http://crackerkeys.com/safe-exam-browser-crack-download/
    Safe Test Browser Crack is a customized web browser. Safe Exam Browser Hack Crack is a browser domain that can perform electronic diagnostics safely. Over time it temporarily transforms the system into a secure platform. Accessing or changing other applications is disabled by default. It prevents everything from going wrong.

    ReplyDelete
  14. Your writing skills greatly impressed me, as well as the clever blog structure.
    Is it a payment issue or do you change it yourself?
    However, if you stop writing in high quality, it's hard to see a good blog these days.
    cool edit pro
    resharper torrent serial key
    reimage pc repair crack
    adobe acrobat pro dc crack
    ableton live crack

    ReplyDelete
  15. Woah! I’m really enjoying the template/theme of this website.
    It’s simple, yet effective. A lot of times it’s very
    difficult to get that “perfect balance” between user friendliness and appearance.
    I must say that you’ve done a very good job with this.
    Also, the blog loads very quickly for me on Firefox.
    Exceptional Blog!
    hide all ip crack
    smartdraw
    mirillis action
    office tab enterprise
    nox cleaner apk

    ReplyDelete
  16. Hi there it’s me, I am also visiting this web page on a regular
    basis, this web site is actually good and the users are truly
    sharing fastidious thoughts.
    imazing crack
    auslogics file recovery crack
    avast pro antivirus crack
    kaspersky antivirus crack
    wondershare tunesgo crack
    malwarebytes crack

    ReplyDelete
  17. Woah! I’m really enjoying the template/theme of this website.
    It’s simple, yet effective. A lot of times it’s very
    difficult to get that “perfect balance” between user friendliness and appearance.
    I must say that you’ve done a very good job with this.
    Also, the blog loads very quickly for me on Firefox.
    Exceptional Blog!
    ableton live crack
    videosolo screen recorder crack
    avast internet security crack
    mirc crack
    wonder share v downloader crack
    pdf candy desktop crack

    ReplyDelete
  18. Woah! I’m really enjoying the template/theme of this website.
    It’s simple, yet effective. A lot of times it’s very
    difficult to get that “perfect balance” between user friendliness and appearance.
    I must say that you’ve done a very good job with this.
    Also, the blog loads very quickly for me on Firefox.
    Exceptional Blog!
    lumion pro crack
    drivermax pro crack
    pubg pc crack
    cinema 4d
    avg email server edition crack
    smart defrag portable crack

    ReplyDelete
  19. Nicely written & done.
    I started writing in the last few days and realized that lot of
    writers simply rework old ideas but add very little of value.
    It’s fantastic to read an informative post of some genuine value to myself and your other followers.
    It is on the list of things I need to replicate as a new blogger.
    Reader engagement and content quality are king.
    Some terrific ideas; you’ve most certainly managed to get on my list of blogs to watch!
    Carry on the terrific work!
    Well done,
    Cheryl.
    Thank you!
    airserver pc crack

    ReplyDelete
  20. https://www.webtalk.co/7115496
    Hello !, I love your article so much! We look forward to another match
    Your article on AOL? I need a specialist in this field to solve my problem.
    Maybe you are! Looking forward to seeing you. This is my website Get free crack software
    little snitch crack
    navicat premium crack
    bluestacks app player crack
    webstorm crack
    fl studio crack
    wm capture crack

    ReplyDelete
  21. I had the honor of receiving a call from a friend who received advice shared on your site.
    Reading your blog post is a truly amazing experience. Thanks again to readers like me and I wish you good luck as a professional.
    download piriform ccleaner pro crack
    autodesk autocad serial number crack
    autodesk autocad crack
    bandicam crack

    ReplyDelete
  22. I would like to point out that I am a beginner to blog, you can definitely taste your website. I probably
    want to add your website to your favorites. You must have a good book. Thanks for sharing your page.
    audials one crack

    ReplyDelete
  23. Hello! This post couldn't have been better! Reading this post reminded me of my good old roommate! He always talked about it. I will forward this page to him. I'm pretty sure he'll read it well. Thanks for sharing!
    du meter crack
    navicat premium crack
    unity pro crack
    anytrans

    ReplyDelete
  24. I really like your content. Your post is really informative. I have learned a lot from your article and I’m looking forward to applying it in my article given below!.
    OriginCrack
    vstcrackss.com
    TubeDigger Crack Free Download
    Enscape3D Crack Download
    Unity Pro Crack Download
    Idm Crack Download

    ReplyDelete
  25. I feel that is among the so much important information for me. And i am satisfied reading your article. However should statement on few common issues, The site style is great, the articles is in point of fact great : D. Excellent process, cheers.
    handy recovery crack
    effectrix vst crack
    exhale vst crack
    dvd cloner crack
    adobe premiere pro crack
    imagenomic portraiture crack
    wondershare dr fone crack
    cinema 4d crack
    proxy switcher pro crack

    ReplyDelete
  26. […] Freemake Video Converter is an entry-level video editing application. Non-linear video editing operations such as cutting, rotating, flipping, and merging multiple videos into one file with transition effects can also be created using photo slideshows with background music. Freemake Video Converter Crack Free Users can upload these videos to YouTube. This is another super software Apowersoft Video Converter Studio. […] cst studio suite crack license key free download
    movavi video suite crack
    daemon tools lite crack activation key latest free download

    ReplyDelete
  27. Great post, I really enjoy reading this post, it explains everything so it's super
    easy. I will visit this blog again for very important information for regular searches.
    corel paintshop pro crack

    ReplyDelete