Dr. Daniel Karapetyan Postdoctoral Fellow Operations Research Group Department of Mathematics Simon Fraser University (Surrey Campus) Curriculum Vitae Google Scholar Webpage (publications, h-index, etc.) Research Interests Combinatorial optimization; Operational research; Algorithm engineering; Local search methods; Bio-inspired computation; Mathematical programming; Multi-criteria optimization; Efficient implementations; Computational experiments; Problem modelling.

Current and Recent Projects

GTSP Instance Library

The GTSP Instances Library is a collection of de facto standard test instances used in computational experiments in many GTSP related publications. The library aims at providing the instances in a convenient form and to keep track of the best solutions found for each of these problems.

Bipartite Unconstrained 0-1 Quadratic Programming Problem

The Bipartite Unconstrained 0-1 Quadratic Programming Problem is a generalization of the well-known Unconstrained 0-1 Quadratic Programming Problem. It has numerous applications in graph theory, matrix factorization, etc. Although the problem is widely mentioning in literature, neither polynomially solvable cases nor heuristic approaches were thoroughly investigated before. We addressed these two subjects and achieved significant results in both cases.

Ferry Routing and Scheduling

The project aimed at finding an optimal fleet configuration for a large ferry company. It was focused of a group of 7 islands to support a major capital investment decision. For each fleet configuration, it was required to produce a set of schedules that would minimize the operating cost and maximize passenger satisfaction.

Because of a high number of constraints and sophisticated objective, ferry routing and scheduling is a hard combinatorial optimization problem, and only a few studies of it were conducted in the past. We proposed two approaches, namely a hybrid evolutionary algorithm and a mixed integer programming formulation, that were able to yield cost efficient ferry schedules of a given level of service in a reasonable time.

Satellite Mission Planning

In the first part of this project, we addressed the satellite downlink scheduleing problem. The data downlinking can be the bottleneck of a satellite's performance. In this project, we formulated the satellite downlink scheduling problem as a constrained parallel machine scheduling problem and proposed an efficient heuristic algorithm to solve this class of problems. In our case study, computational experiments showed that the proposed heuristic clearly outperforms currently implemented algorithms and reaches near-optimal solutions (this was proven by means of a mixed integer program) in less than a minute for any of our benchmark instances.

In the second part of the project, we focused on image acquisition scheduling for a satellite constellation. The existing literature on the subject cannot be applied to our case study problem and, thus, we develop new models and solution techniques to produce near-optimal schedules in a limited time.

Work Experience and Education

From 2011. Postdoctoral Fellow at Simon Fraser University, Department of Mathematics.

Supervisor: Abraham Punnen.

Current and recent projects: ferry routing and scheduling; satellite mission planning.

2007-2010. PhD at Roayl Holloway, University of London, Department of Computer Science.

Title: Design, Evaluation and Analysis of Combinatorial Optimization Heuristic Algorithms.

Supervisor: Gregory Gutin.

Examiners: Natalio Krasnogor and Tomasz Radzik.

Download the thesis.

2001-2007. BSc and MSc (6 years course) at Bauman Moscow State Technical University.

Department of High-Performance Computer Systems and Technologies.

Selected Publications and Preprints

1. Heuristic algorithms for the bipartite unconstrained 0-1 quadratic programming problem.

   Daniel Karapetyan and Abraham Punnen.

   Submitted.

   Download from arXiv. Extra tables. Small instances (56 Kb). Moderate instances (11 Mb). Large instances (260 Mb). Best known solutions (52 Kb).

2. The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases.

   Abraham Punnen, Piyashat Sripratak and Daniel Karapetyan.

   Submitted.

3. An ejection-chain heuristic for the satellite downlink scheduling problem: A case study with RADARSAT-2.

   Daniel Karapetyan, Krishna T. Malladi, Snezana Mitrovic-Minic and Abraham P. Punnen.

   Submitted.

   Download from arXiv.

4. A reduced integer programming model for the ferry scheduling problem.

   Daniel Karapetyan and Abraham P. Punnen.

   To appear in Public Transport.

   Download from arXiv. Go to the official webpage..

5. An efficient hybrid ant colony system for the generalized traveling salesman problem.

   Mohammad Reihaneh and Daniel Karapetyan.

   Algorithmic Operations Research 7, pages 22-29, 2012.

   Go to the official webpage. Download from arXiv.

6. Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem.

   Daniel Karapetyan and Gregory Gutin.

   European Journal of Operational Research 219(2), pages 234-251, 2012.

   Go to the official webpage. Download from arXiv.

7. A new approach to population sizing for memetic algorithms: A case study for the multidimensional assignment problem.

   Daniel Karapetyan and Gregory Gutin.

   Evolutionary Computation 19(3), pages 345-371, 2011.

   Go to the official webpage. Download from arXiv.

8. Lin-Kernighan heuristic adaptation for the generalized traveling salesman problem.

   Daniel Karapetyan and Gregory Gutin.

   European Journal of Operational Research 208(3), pages 221-232, 2011.

   Go to the official webpage. Download from arXiv.

9. Local search heuristics for the multidimensional assignment problem.

   Daniel Karapetyan and Gregory Gutin.

   Journal of Heuristics 17(3), pages 201-249, Springer 2011.

   Go to the official webpage. Download from arXiv.

   Download extra tables.

10. A memetic algorithm for the generalized traveling salesman problem.

    Gregory Gutin and Daniel Karapetyan.

    Natural Computing 9(1), pages 47-60, Springer 2010.

    Go to the official webpage. Download from arXiv.

    Download full source codes. The instances are provided in the GTSP Instances Library.

11. FPT algorithms in analysis of heuristics for extracting networks in linear programs.

    Gregory Gutin, Daniel Karapetyan and Igor Razgon.

    In Proc. of the 4th International Workshop on Parameterized and Exact Computation, IWPEC 2009, Lecture Notes Comp. Sci. 5917, pages 222-233, Springer 2009.

    Go to the official webpage. Download from arXiv.

12. A memetic algorithm for the multidimensional assignment problem.

    Gregory Gutin and Daniel Karapetyan.

    In Proc. of Stochastic Local Search '09 in Brussels, Lecture Notes Comp. Sci. 5752, pages 125-129, Springer 2009.

    Go to the official webpage. Download from arXiv.

13. Generalized traveling salesman problem reduction algorithms.

    Gregory Gutin and Daniel Karapetyan.

    Algorithmic Operations Research 4, pages 144-154, 2009.

    Go to the official webpage. Download from arXiv.

14. A selection of useful theoretical tools for the design and analysis of optimization heuristics.

    Gregory Gutin and Daniel Karapetyan.

    Memetic Computing 1(1), pages 25-34, Springer 2009.

    Go to the official webpage.

15. Local search heuristics for the multidimensional assignment problem.

    Gregory Gutin and Daniel Karapetyan.

    In Proc. of Graph Theory 2008 in Haifa, Lecture Notes Comp. Sci. 5420, pages 100-115, Springer 2009.

    Go to the official webpage. Download from arXiv.

16. Empirical evaluation of construction heuristics for the multidimensional assignment problem.

    Daniel Karapetyan, Gregory Gutin and Boris Goldengorin.

    In Proc. London Algorithmics 2008: Theory and Practice, eds: J. Chan, J. W. Daykin, M. S. Rahman. Texts in Algorithmics 11, pages 107-122, College Publications, 2009.

    Go to the official webpage. Download from arXiv.

17. Greedy like algorithms for the traveling salesman and multidimensional assignment problems.

    Gregory Gutin and Daniel Karapetyan.

    Chapter in Advances in Greedy Algorithms, pages 291-304, IN-TECH 2008.

    Download for the official webpage.

18. Memetic algorithm for the generalized asymmetric traveling salesman problem.

    Gregory Gutin, Daniel Karapetyan, and Natalio Krasnogor.

    In Proc. NICSO 2007, Studies in Computational Intelligence 129, pages 199-210, Springer 2008.

    Go to the official webpage.

Recent Talks

1. An algorithm for the satellite downlink scheduling problem.

   Speaker: Daniel Karapetyan.

   Daniel Karapetyan, Krishna T. Malladi, Snezana Mitrovic-Minic and Abraham P. Punnen.

   CORS 2012: 11-13 June 2012, Niagara Falls, Ontario, Canada.

   Also presented at a seminar in MDA Corporation on 13 Nov 2012.

   Go to the conference website. Download the slides.

2. Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem.

   Speaker: Daniel Karapetyan.

   Gregory Gutin and Daniel Karapetyan.

   Operations Research Seminar: 9 February 2012, Vancouver, Canada.

   Go to the seminar website. Download the slides.

3. A memetic algorithm for the multidimensional assignment problem.

   Speaker: Daniel Karapetyan.

   Gregory Gutin and Daniel Karapetyan.

   SLS'09: 3-5 September 2009, Brussels, Belgium.

   Go to the conference website. Download the slides.

4. A memetic algorithm for the multidimensional assignment problem.

   Speaker: Daniel Karapetyan.

   Gregory Gutin and Daniel Karapetyan.

   20th PCC: 22-24 June 2009, London, UK.

   Go to the conference website. Download the slides.

5. Local search heuristics for the multidimensional assignment problem.

   Speaker: Daniel Karapetyan.

   Gregory Gutin and Daniel Karapetyan.

   ECCO XXII: 15-17 May 2009, Jerusalem, Israel.

   Go to the conference website. Download the slides.

Contact Information

Email: .