Search · four archives
Search · four archives
14 papers · ranked by Valyu relevance
Joshua T. Vogelstein, John M. Conroy, Vince Lyzinski, Louis J. Podrazik + 6 more
'Louis J. Podrazik' 'Steven G. Kratzer' 'Eric T. Harley' 'Donniell E. Fishkind' 'R. Jacob Vogelstein' 'Carey E. Priebe' 'Mark R. Muldoon'] Quadratic assignment problems arise in a wide variety of domains, spanning operations research, graph theory, computer vision, and neuroscience, to name a few. The graph matching…
Alfonsas Misevičius, Dovilė Verenė
In this paper, we present a hybrid genetic-hierarchical algorithm for the solution of the quadratic assignment problem. The main distinguishing aspect of the proposed algorithm is that this is an innovative hybrid genetic algorithm with the original, hierarchical architecture. In particular, the genetic algorithm is…
Wojciech Chmiel, Joanna Kwiecień
The paper focuses on the opportunity of the application of the quantum-inspired evolutionary algorithm for determining minimal costs of the assignment in the quadratic assignment problem. The idea behind the paper is to present how the algorithm has to be adapted to this problem, including crossover and mutation…
Wee Loon Lim, Antoni Wibowo, Mohammad Ishak Desa, Habibollah Haron
The quadratic assignment problem (QAP) is an NP-hard combinatorial optimization problem with a wide variety of applications. Biogeography-based optimization (BBO), a relatively new optimization technique based on the biogeography concept, uses the idea of migration strategy of species to derive algorithm for solving…
Hao Hu, Renata Sotirov, Henry Wolkowicz
We consider both facial reduction, FR, and symmetry reduction, SR, techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. In fact, this approach allows for simply adding on nonnegativity constraints, and…
S. H. Sathish Indika, Douglas R. Shier
This work is motivated by a particular scheduling problem that is faced by logistics centers that perform aircraft maintenance and modification. Here we concentrate on a single facility (hangar) which is equipped with several work stations (bays). Specifically, a number of jobs have already been scheduled for…
Olga Brezhneva, Agnieszka Prusińska, Alexey A. Tret’yakov, Ravi P. Agarwal
'Ravi P. Agarwal'] The paper describes an application of the p-regularity theory to Quadratic Programming (QP) and nonlinear equations with quadratic mappings. In the first part of the paper, a special structure of the nonlinear equation and a construction of the 2-factor operator are used to obtain an exact formula…
Immanuel Bomze, Bo Peng, Yuzhou Qiu, E. Alper Yıldırım
Standard quadratic optimization problems (StQPs) provide a versatile modelling tool in various applications. In this paper, we consider StQPs with a hard sparsity constraint, referred to as sparse StQPs. We focus on various tractable convex relaxations of sparse StQPs arising from a mixed-binary quadratic formulation…
Li Ge, Sanyang Liu
To globally solve a nonconvex quadratic programming problem, this paper presents an accelerating linearizing algorithm based on the framework of the branch-and-bound method. By utilizing a new linear relaxation approach, the initial quadratic programming problem is reduced to a sequence of linear relaxation programming…
Alberto Ceselli, Marco Premoli
Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic…
Amnon Rosenmann
The k-cardinality assignment (k-assignment, for short) problem asks for finding a minimal (maximal) weight of a matching of cardinality k in a weighted bipartite graph $K_{n,n}$, $k \le n$. Here we are interested in computing the sequence of all k-assignments, $k=1,\ldots ,n$. By applying the algorithm of Gassner and…
Chunshan Xue, Hongwei Jiao, Jingben Yin, Yongqiang Chen
This paper presents a novel range division and contraction approach for globally solving nonconvex quadratic program with quadratic constraints. By constructing new underestimating linear relaxation functions, we can transform the initial nonconvex quadratic program problem into a linear program relaxation problem. By…
Matúš Benko, Helmut Gfrerer
We propose an SQP algorithm for mathematical programs with vanishing constraints which solves at each iteration a quadratic program with linear vanishing constraints. The algorithm is based on the newly developed concept of ${\mathcal{Q}}$-stationarity (Benko and Gfrerer in Optimization 66(1):61-92, [5]). We…
Nikhil Bansal, Tim Oosterwijk, Tjark Vredeveld, Ruben van der Zwaan
We consider the Vector Scheduling problem, a natural generalization of the classical makespan minimization problem to multiple resources. Here, we are given n jobs, represented as d-dimensional vectors in $[0,1]^d$, and m identical machines, and the goal is to assign the jobs to machines such that the maximum load of…