A dual local search framework for combinatorial optimization problems with TSP application

Jamal Ouenniche, Prasanna Kumar Ramaswamy, Michel Gendreau

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

In practice, solving realistically sized combinatorial optimization problems to optimality is often too time-consuming to be affordable; therefore, heuristics are typically implemented within most applications software. A specific category of heuristics has attracted considerable attention, namely local search methods. Most local search methods are primal in nature; that is, they start the search with a feasible solution and explore the feasible space for better feasible solutions. In this research, we propose a dual local search method and customize it to solve the traveling salesman problem (TSP); that is, a search method that starts with an infeasible solution, explores the dual space—each time reducing infeasibility, and lands in the primal space to deliver a feasible solution. The proposed design aims to replicate the designs of optimal solution methodologies in a heuristic way. To be more specific, we solve a combinatorial relaxation of a TSP formulation, design a neighborhood structure to repair such an infeasible starting solution, and improve components of intermediate dual solutions locally. Sample-based evidence along with statistically significant t-tests support the superiority of this dual design compared to its primal design counterpart.
Original languageEnglish
Pages (from-to)1377-1398
JournalJournal of the Operational Research Society
Issue number11
Early online date23 Jan 2017
Publication statusPublished - 21 Dec 2017

Keywords / Materials (for Non-textual outputs)

  • dual local search
  • relaxation
  • optimization
  • traveling salesman
  • routing and scheduling


Dive into the research topics of 'A dual local search framework for combinatorial optimization problems with TSP application'. Together they form a unique fingerprint.

Cite this