Binary quadratic programming (BQP) is a typical integer programming problem widely applied in the field of signal processing, economy, management and engineering. However, it is NP-hard and lacks ...efficient algorithms. Due to this reason, in this paper, some novel polynomial algorithms are proposed to solve a class of unconstrained and linearly constrained binary quadratic programming problems. We first deduce the polynomial time solvable algorithms to the unconstrained binary quadratic programming problems with Q being a seven-diagonal matrix (UBQP7) and a five-diagonal matrix (UBQP5) respectively with two different approaches. Then, the algorithm to unconstrained problem is combined with the dynamic programming method to solve the linearly constrained binary quadratic programming problem with Q being a five-diagonal matrix (LCBQP5). In addition, the polynomial solvable feature of these algorithms is analyzed and some specific examples are presented to illustrate these new algorithms. Lastly, we demonstrate their polynomial feature as well as their high efficiency.
Given an undirected graph with costs associated to its edges and pairs of edges, the Quadratic Minimum Spanning Tree Problem (QMSTP) requires to determine a spanning tree of minimum total cost. This ...is a proper model for network problems in which both routing and interference costs need to be considered. It is NP-hard in the strong sense and not approximable unless P=NP. This paper describes a Tabu Search algorithm, with two independent and adaptively tuned tabu lists, and a Variable Neighbourhood Search algorithm. Both metaheuristics are based on the same neighbourhood, but the Tabu Search proves more effective and robust than the Variable Neighbourhood Search. To assess the quality of these results, we provide a comparison with the heuristic algorithms proposed in the recent literature and we reimplement, with minor improvements, an exact algorithm drawn from the literature, which confirms the optimality of the results obtained on small instances.
This book is a printed edition of the Special Issue Advances in Intelligent Vehicle Control that was published in the journal Sensors. It presents a collection of eleven papers that covers a range of ...topics, such as the development of intelligent control algorithms for active safety systems, smart sensors, and intelligent and efficient driving. The contributions presented in these papers can serve as useful tools for researchers who are interested in new vehicle technology and in the improvement of vehicle control systems.
Glover’s linearization technique is revisited for solving the binary quadratic programming problem with a budget constraint (BBQP). When compared with the recent two linearizations for (BBQP), it not ...only provides a tighter relaxation at the root node, but also has a much better computational performance for globally solving (BBQP).
The maximum diversity problem (MDP) is a challenging NP-hard problem with a wide range of real applications. Several researchers have pointed out close relationship between the MDP and unconstrained ...binary quadratic program (UBQP). In this paper, we provide procedures to solve MDP ideas from the UBQP formulation of the problem. We first give some local optimality results for r-flip improvement procedures on MDP. Then, a set of highly effective diversification approaches based on sequential improvement steps for MDP are presented. Four versions of the approaches are used within a simple tabu search and applied to 140 benchmark MDP problems available on the Internet. The procedures solve all 80 small- to medium-sized problems instantly to the best known solutions. For 22 of the 60 large problems, the procedures improved by significant amounts the best known solutions in reasonably short CPU time.
We introduce and prove new necessary and sufficient conditions to carry out a compact linearization approach for a general class of binary quadratic problems subject to assignment constraints that ...has been proposed by Liberti (4OR 5(3):231–245,
2007
,
https://doi.org/10.1007/s10288-006-0015-3
). The new conditions resolve inconsistencies that can occur when the original method is used. We also present a mixed-integer linear program to compute a minimally sized linearization. When all the assignment constraints have non-overlapping variable support, this program is shown to have a totally unimodular constraint matrix. Finally, we give a polynomial-time combinatorial algorithm that is exact in this case and can be used as a heuristic otherwise.
In recent years, the general binary quadratic programming (BQP) model has been widely applied to solve a number of combinatorial optimization problems. In this paper, we recast the maximum vertex ...weight clique problem (MVWCP) into this model which is then solved by a probabilistic tabu search algorithm designed for the BQP. Experimental results on 80 challenging DIMACS-W and 40 BHOSLIB-W benchmark instances demonstrate that this general approach is viable for solving the MVWCP problem.
Many combinatorial optimization problems and engineering problems can be modeled as boolean quadratic programming (BQP) problems. In this paper, two augmented Lagrangian methods (ALM) are discussed ...for the solution of BQP problems based on a class of continuous functions. After convexification, the BQP is reformulated as an equivalent augmented Lagrangian function, and then solved by two ALM algorithms. Within this ALM algorithm, L-BFGS is called for the solution of unconstrained nonlinear programming problem. Experiments are performed on max-cut problem, 0–1 quadratic knapsack problem and image deconvolution, which indicate that ALM method is promising for solving large scale BQP by the quality of near optimal solution with low computational time.
Every quadratic programming problem with a mix of continuous and binary variables can be equivalently reformulated as a completely positive optimization problem, that is, a linear optimization ...problem over the convex but computationally intractable cone of completely positive matrices. In this paper, we focus on general inner approximations of the cone of completely positive matrices on instances of completely positive optimization problems that arise from the reformulation of mixed binary quadratic programming problems. We provide a characterization of the feasibility of such an inner approximation as well as the optimal value of a feasible inner approximation. In particular, our results imply that polyhedral inner approximations are equivalent to a finite discretization of the feasible region of the original completely positive optimization problem. Our characterization yields, as a byproduct, an upper bound on the gap between the optimal value of an inner approximation and that of the original instance. We discuss the implications of this error bound for standard and box-constrained quadratic programs as well as general mixed binary quadratic programs with a bounded feasible region.
Celotno besedilo
Dostopno za:
BFBNIB, DOBA, GIS, IJS, IZUM, KILJ, KISLJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
Unconstrained binary quadratic programming (UBQP) provides a unifying modeling and solution framework for solving a remarkable range of binary optimization problems, including many accompanied by ...constraints. Current methods for solving UBQP problems customarily rely on neighborhoods consisting of
flip moves
that select one or more binary variables and “flip” their values to the complementary value (from 1 to 0 or from 0 to 1). We introduce a class of approaches called
f-flip strategies
that include a fractional value f as one of those available to the binary variables during intermediate stages of solution. A variety of different f-flip strategies, particularly within the context of multi-start algorithms, are proposed for pursuing intensification and diversification goals in metaheuristic algorithms, accompanied by special rules for evaluating and executing f-flips efficiently.
PDF
