liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
Alternative names
Publications (10 of 73) Show all publications
Hoppmann-Baum, K., Burdakov, O., Mexi, G., Casselgren, C. J. & Koch, T. (2022). Length-constrained cycle partition with an application to UAV routing*. Optimization Methods and Software, 37(6), 2080-2116
Open this publication in new window or tab >>Length-constrained cycle partition with an application to UAV routing*
Show others...
2022 (English)In: Optimization Methods and Software, ISSN 1055-6788, E-ISSN 1029-4937, Vol. 37, no 6, p. 2080-2116Article in journal (Refereed) Published
Abstract [en]

This article discusses the Length-Constrained Cycle Partition Problem (LCCP), which constitutes a new generalization of the Travelling Salesperson Problem (TSP). Apart from nonnegative edge weights, the undirected graph in LCCP features a nonnegative critical length parameter for each vertex. A cycle partition, i.e. a vertex-disjoint cycle cover, is a feasible solution for LCCP if the length of each cycle is not greater than the critical length of each vertex contained in it. The goal is to find a feasible partition having a minimum number of cycles. Besides analyzing theoretical properties and developing preprocessing techniques, we propose an elaborate heuristic algorithm that produces solutions of good quality even for large-size instances. Moreover, we present two exact mixed-integer programming formulations (MIPs) for LCCP, which are inspired by well-known modeling approaches for TSP. Further, we introduce the concept of conflict hypergraphs, whose cliques yield valid constraints for the MIP models. We conclude with a discussion on computational experiments that we conducted using (A)TSPLIB-based problem instances. As a motivating example application, we describe a routing problem where a fleet of uncrewed aerial vehicles (UAVs) must patrol a given set of areas.

Place, publisher, year, edition, pages
TAYLOR & FRANCIS LTD, 2022
Keywords
Combinatorial optimization; mixed-integer programming; uncrewed aerial vehicles; travelling salesperson problem
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-185276 (URN)10.1080/10556788.2022.2053972 (DOI)000794250800001 ()
Note

Funding Agencies|German FederalMinistry of Education and Research (BMBF) [05M14ZAM, 05M20ZBM]; Wallenberg AI, Autonomous Systems and Software Program (WASP) - Knut and Alice Wallenberg Foundation; Swedish Research Council [2017-05077]

Available from: 2022-05-25 Created: 2022-05-25 Last updated: 2023-03-28Bibliographically approved
Anistratov, P., Olofsson, B., Burdakov, O. & Nielsen, L. (2020). Autonomous-Vehicle Maneuver Planning Using Segmentation and the Alternating Augmented Lagrangian Method. In: Rolf Findeisen, Sandra Hirche, Klaus Janschek, Martin Mönnigmann (Ed.), 21th IFAC World Congress Proceedings: . Paper presented at The 21st IFAC World Congress (Virtual), Berlin, Germany, July 12-17, 2020 (pp. 15558-15565). Elsevier, 53
Open this publication in new window or tab >>Autonomous-Vehicle Maneuver Planning Using Segmentation and the Alternating Augmented Lagrangian Method
2020 (English)In: 21th IFAC World Congress Proceedings / [ed] Rolf Findeisen, Sandra Hirche, Klaus Janschek, Martin Mönnigmann, Elsevier, 2020, Vol. 53, p. 15558-15565Conference paper, Published paper (Refereed)
Abstract [en]

Segmenting a motion-planning problem into smaller subproblems could be beneficial in terms of computational complexity. This observation is used as a basis for a new sub-maneuver decomposition approach investigated in this paper in the context of optimal evasive maneuvers for autonomous ground vehicles. The recently published alternating augmented Lagrangianmethod is adopted and leveraged on, which turns out to fit the problem formulation with several attractive properties of the solution procedure. The decomposition is based on moving the coupling constraints between the sub-maneuvers into a separate coordination problem, which is possible to solve analytically. The remaining constraints and the objective function are decomposed into subproblems, one for each segment, which means that parallel computation is possible and benecial. The method is implemented and evaluated in a safety-critical double lane-change scenario. By using the solution of a low-complexity initialization problem and applying warm-start techniques in the optimization, a solution is possible to obtain after just a few alternating iterations using the developed approach. The resulting computational time is lower than solving one optimization problem for the full maneuver.

Place, publisher, year, edition, pages
Elsevier, 2020
Series
IFAC PapersOnline, E-ISSN 2405-8963
Keywords
trajectory and path planning, motion planning, optimal control, problem decomposition, vehicle safety maneuvers
National Category
Vehicle and Aerospace Engineering Robotics and automation Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-171784 (URN)10.1016/j.ifacol.2020.12.2400 (DOI)000652593600372 ()
Conference
The 21st IFAC World Congress (Virtual), Berlin, Germany, July 12-17, 2020
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)
Note

Funding: Wallenberg AI, Autonomous Systems and Software Program (WASP) - Knut and Alice Wallenberg Foundation

Available from: 2020-12-06 Created: 2020-12-06 Last updated: 2025-02-14Bibliographically approved
Hoppmann-Baum, K., Mexi, G., Burdakov, O., Casselgren, C. J. & Koch, T. (2020). Length-Constrained Cycle Partition with an Application to UAV Routing. Berlin: Zuse Institute Berlin
Open this publication in new window or tab >>Length-Constrained Cycle Partition with an Application to UAV Routing
Show others...
2020 (English)Report (Other academic)
Abstract [en]

In this article, we discuss the Length-Constrained Cycle Partition Problem (LCCP). Besides edge weights, the undirected graph in LCCP features an individual critical weight value for each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is a feasible solution if the length of each cycle is not greater than the critical weight of each of the vertices in the cycle. The goal is to find a feasible partition with the minimum number of cycles. In this article, we discuss theoretical properties, preprocessing techniques, and two mixed-integer programming models (MIP) for LCCP both inspired by formulations for the closely related Travelling Salesperson Problem (TSP). Further, we introduce conflct hypergraphs, whose cliques yield valid constraints for the MIP models. We conclude with a report on computational experiments conducted on (A)TSPLIB-based instances. As an example, we use a routing problem in which a set of uncrewed aerial vehicles (UAVs) patrols a set of areas.

Place, publisher, year, edition, pages
Berlin: Zuse Institute Berlin, 2020. p. 22
Series
ZIB-Report, ISSN 1438-0064, E-ISSN 2192-7782 ; 20-30
Keywords
Combinatorial Optimization, Mixed Integer Programming, Unmanned Aerial Vehicles
National Category
Discrete Mathematics Robotics and automation
Identifiers
urn:nbn:se:liu:diva-171788 (URN)
Funder
Swedish Research Council, 2017-05077Wallenberg AI, Autonomous Systems and Software Program (WASP)
Available from: 2020-12-07 Created: 2020-12-07 Last updated: 2025-02-05Bibliographically approved
Hoppmann, K., Mexi, G., Burdakov, O., Casselgren, C. J. & Koch, T. (2020). Minimum Cycle Partition with Length Requirements. In: Integration of Constraint Programming, Artificial Intelligence, and Operations Research: . Paper presented at 17th International Conference, CPAIOR 2020, Vienna, Austria, September 21–24, 2020 (pp. 273-282). , 12296
Open this publication in new window or tab >>Minimum Cycle Partition with Length Requirements
Show others...
2020 (English)In: Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2020, Vol. 12296, p. 273-282Conference paper, Published paper (Refereed)
Abstract [en]

In this article we introduce a Minimum Cycle Partition Problem with Length Requirements (CPLR). This generalization of the Travelling Salesman Problem (TSP) originates from routing Unmanned Aerial Vehicles (UAVs). Apart from nonnegative edge weights, CPLR has an individual critical weight value associated with each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is regarded as a feasible solution if the length of each cycle, which is the sum of the weights of its edges, is not greater than the critical weight of each of its vertices. The goal is to find a feasible partition, which minimizes the number of cycles. In this article, a heuristic algorithm is presented together with a Mixed Integer Programming (MIP) formulation of CPLR. We furthermore introduce a conflict graph, whose cliques yield valid constraints for the MIP model. Finally, we report on computational experiments conducted on TSPLIB-based test instances.

Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349
Series
Theoretical Computer Science and General Issues, ISSN 0302-9743
Keywords
Travelling salesman problem, Combinatorial optimization, Mixed integer linear programming, Conflict graph, Unmanned Aerial Vehicles
National Category
Discrete Mathematics Computer graphics and computer vision Robotics and automation
Identifiers
urn:nbn:se:liu:diva-169758 (URN)10.1007/978-3-030-58942-4_18 (DOI)000884722900018 ()9783030589417 (ISBN)
Conference
17th International Conference, CPAIOR 2020, Vienna, Austria, September 21–24, 2020
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP), 305286
Available from: 2020-09-18 Created: 2020-09-18 Last updated: 2025-02-05Bibliographically approved
Brust, J., Burdakov, O., Erway, J. B. & Marcia, R. F. (2019). A dense initialization for limited-memory quasi-Newton methods. Computational Optimization and Applications, 74(1), 121-142
Open this publication in new window or tab >>A dense initialization for limited-memory quasi-Newton methods
2019 (English)In: Computational Optimization and Applications, ISSN 0926-6003, Vol. 74, no 1, p. 121-142Article in journal (Other academic) Published
Abstract [en]

We consider a family of dense initializations for limited-memory quasi-Newton methods. The proposed initialization exploits an eigendecomposition-based separation of the full space into two complementary subspaces, assigning a different initialization parameter to each subspace. This family of dense initializations is proposed in the context of a limited-memory Broyden–Fletcher–Goldfarb–Shanno (L-BFGS) trust-region method that makes use of a shape-changing norm to define each subproblem. As with L-BFGS methods that traditionally use diagonal initialization, the dense initialization and the sequence of generated quasi-Newton matrices are never explicitly formed. Numerical experiments on the CUTEst test set suggest that this initialization together with the shape-changing trust-region method outperforms other L-BFGS methods for solving general nonconvex unconstrained optimization problems. While this dense initialization is proposed in the context of a special trust-region method, it has broad applications for more general quasi-Newton trust-region and line search methods. In fact, this initialization is suitable for use with any quasi-Newton update that admits a compact representation and, in particular, any member of the Broyden class of updates.

Place, publisher, year, edition, pages
Springer, 2019
Keywords
Large-scale nonlinear optimization, limited-memory quasi-Newton methods, trust-region methods, quasi-Newton matrices, shape-changing norm.
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-143315 (URN)10.1007/s10589-019-00112-x (DOI)000476600200005 ()
Note

Funding agencies: NSF [CMMI-1334042, CMMI-1333326, IIS-1741490, IIS-1741264]

Available from: 2017-12-04 Created: 2017-12-04 Last updated: 2019-08-12Bibliographically approved
Sysoev, O. & Burdakov, O. (2019). A smoothed monotonic regression via L2 regularization. Knowledge and Information Systems, 59(1), 197-218
Open this publication in new window or tab >>A smoothed monotonic regression via L2 regularization
2019 (English)In: Knowledge and Information Systems, ISSN 0219-1377, E-ISSN 0219-3116, Vol. 59, no 1, p. 197-218Article in journal (Refereed) Published
Abstract [en]

Monotonic regression is a standard method for extracting a monotone function from non-monotonic data, and it is used in many applications. However, a known drawback of this method is that its fitted response is a piecewise constant function, while practical response functions are often required to be continuous. The method proposed in this paper achieves monotonicity and smoothness of the regression by introducing an L2 regularization term. In order to achieve a low computational complexity and at the same time to provide a high predictive power of the method, we introduce a probabilistically motivated approach for selecting the regularization parameters. In addition, we present a technique for correcting inconsistencies on the boundary. We show that the complexity of the proposed method is O(n2). Our simulations demonstrate that when the data are large and the expected response is a complicated function (which is typical in machine learning applications) or when there is a change point in the response, the proposed method has a higher predictive power than many of the existing methods.

Place, publisher, year, edition, pages
Springer, 2019
Keywords
Monotonic regression, Kernel smoothing, Penalized regression, Probabilistic learning, Constrained optimization
National Category
Probability Theory and Statistics Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-147628 (URN)10.1007/s10115-018-1201-2 (DOI)000461390300008 ()
Available from: 2018-04-27 Created: 2018-04-27 Last updated: 2019-04-03Bibliographically approved
Burdakov, O., Dai, Y.-H. & Huang, N. (2019). Stabilized Barzilai-Borwein method. Journal of Computational Mathematics, 37(6), 916-936
Open this publication in new window or tab >>Stabilized Barzilai-Borwein method
2019 (English)In: Journal of Computational Mathematics, ISSN 0254-9409, E-ISSN 1991-7139, Vol. 37, no 6, p. 916-936Article in journal (Refereed) Published
Abstract [en]

The Barzilai-Borwein (BB) method is a popular and efficient tool for solving large-scale unconstrained optimization problems. Its search direction is the same as for the steepest descent (Cauchy) method, but its stepsize rule is different. Owing to this, it converges much faster than the Cauchy method. A feature of the BB method is that it may generate too long steps, which throw the iterates too far away from the solution. Moreover, it may not converge, even when the objective function is strongly convex. In this paper, a stabilization technique is introduced. It consists in bounding the distance between each pair of successive iterates, which often allows for decreasing the number of BB iterations. When the BB method does not converge, our simple modification of this method makes it convergent. For strongly convex functions with Lipschits gradients, we prove its global convergence, despite the fact that no line search is involved, and only gradient values are used. Since the number of stabilization steps is proved to be finite, the stabilized version inherits the fast local convergence of the BB method. The presented results of extensive numerical experiments show that our stabilization technique often allows the BB method to solve problems in a fewer iterations, or even to solve problems where the latter fails.

Place, publisher, year, edition, pages
Global Science Press, 2019
Keywords
Unconstrained optimization, Spectral algorithms, Stabilization, Convergence analysis.
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-162637 (URN)10.4208/jcm.1911-m2019-0171 (DOI)000504738100009 ()
Note

Funding agencies:  Visiting Scientist award under the Chinese Academy of Sciences Presidents International Fellowship Initiative; Chinese Natural Science FoundationNational Natural Science Foundation of China [11631013]; National 973 Program of ChinaNational Basic Research 

Available from: 2019-12-12 Created: 2019-12-12 Last updated: 2021-09-20Bibliographically approved
Burdakov, O. & Sysoev, O. (2017). A Dual Active-Set Algorithm for Regularized Slope-Constrained Monotonic Regression. Iranian Journal of Operations Research, 8(2), 40-47
Open this publication in new window or tab >>A Dual Active-Set Algorithm for Regularized Slope-Constrained Monotonic Regression
2017 (English)In: Iranian Journal of Operations Research, ISSN 2008-1189, Vol. 8, no 2, p. 40-47Article in journal (Refereed) Published
Abstract [en]

In many problems, it is necessary to take into account monotonic relations. Monotonic (isotonic) Regression (MR) is often involved in solving such problems. The MR solutions are of a step-shaped form with a typical sharp change of values between adjacent steps. This, in some applications, is regarded as a disadvantage. We recently introduced a Smoothed MR (SMR) problem which is obtained from the MR by adding a regularization penalty term. The SMR is aimed at smoothing the aforementioned sharp change. Moreover, its solution has a far less pronounced step-structure, if at all available. The purpose of this paper is to further improve the SMR solution by getting rid of such a structure. This is achieved by introducing a lowed bound on the slope in the SMR. We call it Smoothed Slope-Constrained MR (SSCMR) problem. It is shown here how to reduce it to the SMR which is a convex quadratic optimization problem. The Smoothed Pool Adjacent Violators (SPAV) algorithm developed in our recent publications for solving the SMR problem is adapted here to solving the SSCMR problem. This algorithm belongs to the class of dual active-set algorithms. Although the complexity of the SPAV algorithm is o(n2) its running time is growing in our computational experiments almost linearly with n. We present numerical results which illustrate the predictive performance quality of our approach. They also show that the SSCMR solution is free of the undesirable features of the MR and SMR solutions.

Place, publisher, year, edition, pages
Tehran: , 2017
Keywords
Monotonic regression, Regularization, Quadratic penalty, Convex quadratic optimization, Dual active-set method, Large-scale optimization
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-148061 (URN)10.29252/iors.8.2.40 (DOI)
Available from: 2018-05-29 Created: 2018-05-29 Last updated: 2018-06-07Bibliographically approved
Burdakov, O., Gong, L., Zikrin, S. & Yuan, Y.-x. (2017). On Efficiently Combining Limited-Memory and Trust-Region Techniques. Mathematical Programming Computation, 9(1), 101-134
Open this publication in new window or tab >>On Efficiently Combining Limited-Memory and Trust-Region Techniques
2017 (English)In: Mathematical Programming Computation, ISSN 1867-2949, E-ISSN 1867-2957, Vol. 9, no 1, p. 101-134Article in journal (Refereed) Published
Abstract [en]

Limited-memory quasi-Newton methods and trust-region methods represent two efficient approaches used for solving unconstrained optimization problems. A straightforward combination of them deteriorates the efficiency of the former approach, especially in the case of large-scale problems. For this reason, the limited-memory methods are usually combined with a line search. We show how to efficiently combine limited-memory and trust-region techniques. One of our approaches is based on the eigenvalue decomposition of the limited-memory quasi-Newton approximation of the Hessian matrix. The decomposition allows for finding a nearly-exact solution to the trust-region subproblem defined by the Euclidean norm with an insignificant computational overhead as compared with the cost of computing the quasi-Newton direction in line-search limited-memory methods. The other approach is based on two new eigenvalue-based norms. The advantage of the new norms is that the trust-region subproblem is separable and each of the smaller subproblems is easy to solve. We show that our eigenvalue-based limited-memory trust-region methods are globally convergent. Moreover, we propose improved versions of the existing limited-memory trust-region algorithms. The presented results of numerical experiments demonstrate the efficiency of our approach which is competitive with line-search versions of the L-BFGS method.

Place, publisher, year, edition, pages
Springer, 2017
Keywords
Unconstrained Optimization, Large-scale Problems, Limited-Memory Methods, Trust-Region Methods, Shape-Changing Norm, Eigenvalue Decomposition
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-129783 (URN)10.1007/s12532-016-0109-7 (DOI)000398897800004 ()2-s2.0-85013821893 (Scopus ID)
Available from: 2016-06-28 Created: 2016-06-28 Last updated: 2025-05-09Bibliographically approved
Burdakov, O., Kvarnström, J. & Doherty, P. (2017). Optimal scheduling for replacing perimeter guarding unmanned aerial vehicles. Annals of Operations Research, 249(1), 163-174
Open this publication in new window or tab >>Optimal scheduling for replacing perimeter guarding unmanned aerial vehicles
2017 (English)In: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 249, no 1, p. 163-174Article in journal (Refereed) Published
Abstract [en]

Guarding the perimeter of an area in order to detect potential intruders is an important task in a variety of security-related applications. This task can in many circumstances be performed by a set of camera-equipped unmanned aerial vehicles (UAVs). Such UAVs will occasionally require refueling or recharging, in which case they must temporarily be replaced by other UAVs in order to maintain complete surveillance of the perimeter. In this paper we consider the problem of scheduling such replacements. We present optimal replacement strategies and justify their optimality.

Place, publisher, year, edition, pages
Springer, 2017
Keywords
Scheduling problem, Optimal replacement strategies, Perimeter guarding, Unmanned aerial vehicles
National Category
Computer Sciences Computational Mathematics Information Systems
Identifiers
urn:nbn:se:liu:diva-126459 (URN)10.1007/s10479-016-2169-5 (DOI)000394151400010 ()2-s2.0-84961644607 (Scopus ID)
Funder
EU, FP7, Seventh Framework Programme, 600958VINNOVA, 2013-01206Linnaeus research environment CADICSELLIIT - The Linköping‐Lund Initiative on IT and Mobile Communications
Available from: 2016-03-27 Created: 2016-03-27 Last updated: 2018-01-10Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0003-1836-4200

Search in DiVA

Show all publications