In this paper several equivalent formulations for the quadratic binary programming problem are presented. Based on these formulations we describe four different kinds of strategies for estimating lower bounds of the o...
详细信息
In this paper several equivalent formulations for the quadratic binary programming problem are presented. Based on these formulations we describe four different kinds of strategies for estimating lower bounds of the objective function, which can be integrated into a branch and bound algorithm for solving the quadratic binary programming problem. We also give a theoretical explanation for forcing rules used to branch the variables efficiently, and explore several properties related to obtained subproblems. From the viewpoint of the number of subproblems solved, new strategies for estimating lower bounds are better than those used before. A variant of a depth-first branch and bound algorithm is described and its numerical performance is presented.
We present in this paper an improved estimation of duality gap between binaryquadratic program and its Lagrangian dual. More specifically, we obtain this improved estimation using a weighted distance measure between ...
详细信息
We present in this paper an improved estimation of duality gap between binaryquadratic program and its Lagrangian dual. More specifically, we obtain this improved estimation using a weighted distance measure between the binary set and certain affine subspace. We show that the optimal weights can be computed by solving a semidefinite programming problem. We further establish a necessary and sufficient condition under which the weighted distance measure gives a strictly tighter estimation of the duality gap than the existing estimations. (C) 2011 Elsevier B.V. All rights reserved.
In this paper, we develop a Lagrangian decomposition based heuristic method for general quadraticbinary programs (QBPs) with linear constraints. We extend the idea of Lagrangian decomposition by Chardaire and Sutter ...
详细信息
In this paper, we develop a Lagrangian decomposition based heuristic method for general quadraticbinary programs (QBPs) with linear constraints. We extend the idea of Lagrangian decomposition by Chardaire and Sutter (Manag Sci 41(4):704-712, 1995) and Billionnet and Soutif (Eur J Oper Res 157(3):565-575, 2004a, Inf J Comput 16(2):188-197, 2004b) in which the quadratic objective is converted to a bilinear function by introducing auxiliary variables to duplicate the original complicating variables in the problem. Instead of using linear constraints to assure the equity between the two types of decision variables, we introduce generalized quadratic constraints and relax them with Lagrangian multipliers. Instead of computing an upper bound for a maximization problem, we focus on lower bounding with Lagrangian decomposition based heuristic. We take advantage of the decomposability presented in the Lagrangian subproblems to speed up the heuristic and identify one feasible solution at each iteration of the subgradient optimization procedure. With numerical studies on several classes of representative QBPs, we investigate the sensitivity of lower-bounding performance on parameters of the additional quadratic constraints. We also demonstrate the potentially improved quality of preprocessing in comparison with the use of a QBP solver.
Epileptic seizures are manifestations of intermittent spatiotemporal transitions of the human brain from chaos to order. Measures of chaos, namely maximum Lyapunov exponents (STL (max) ), from dynamical analysis of th...
详细信息
Epileptic seizures are manifestations of intermittent spatiotemporal transitions of the human brain from chaos to order. Measures of chaos, namely maximum Lyapunov exponents (STL (max) ), from dynamical analysis of the electroencephalograms (EEGs) at critical sites of the epileptic brain, progressively converge (diverge) before (after) epileptic seizures, a phenomenon that has been called dynamical synchronization (desynchronization). This dynamical synchronization/desynchronization has already constituted the basis for the design and development of systems for long-term (tens of minutes), on-line, prospective prediction of epileptic seizures. Also, the criterion for the changes in the time constants of the observed synchronization/desynchronization at seizure points has been used to show resetting of the epileptic brain in patients with temporal lobe epilepsy (TLE), a phenomenon that implicates a possible homeostatic role for the seizures themselves to restore normal brain activity. In this paper, we introduce a new criterion to measure this resetting that utilizes changes in the level of observed synchronization/desynchronization. We compare this criterion's sensitivity of resetting with the old one based on the time constants of the observed synchronization/desynchronization. Next, we test the robustness of the resetting phenomena in terms of the utilized measures of EEG dynamics by a comparative study involving STL (max) , a measure of phase (phi (max) ) and a measure of energy (E) using both criteria (i.e. the level and time constants of the observed synchronization/desynchronization). The measures are estimated from intracranial electroencephalographic (iEEG) recordings with subdural and depth electrodes from two patients with focal temporal lobe epilepsy and a total of 43 seizures. Techniques from optimization theory, in particular quadratic bivalent programming, are applied to optimize the performance of the three measures in detecting preictal entrainment.
We consider a parametric convex quadraticprogramming (CQP) relaxation for the quadratic knapsack problem (QKP). This relaxation maintains partial quadratic information from the original QKP by perturbing the objectiv...
详细信息
We consider a parametric convex quadraticprogramming (CQP) relaxation for the quadratic knapsack problem (QKP). This relaxation maintains partial quadratic information from the original QKP by perturbing the objective function to obtain a concave quadratic term. The nonconcave part generated by the perturbation is then linearized by a standard approach that lifts the problem to matrix space. We present a primal-dual interior point method to optimize the perturbation of the quadratic function, in a search for the tightest upper bound for the QKP. We prove that the same perturbation approach, when applied in the context of semidefinite programming (SDP) relaxations of the QKP, cannot improve the upper bound given by the corresponding linear SDP relaxation. The result also applies to more general integer quadratic problems. Finally, we propose new valid inequalities on the lifted matrix variable, derived from cover and knapsack inequalities for the QKP, and present separation problems to generate cuts for the current solution of the CQP relaxation. Our best bounds are obtained alternating between optimizing the parametric quadratic relaxation over the perturbation and applying cutting planes generated by the valid inequalities proposed. (C) 2019 Elsevier B.V. All rights reserved.
This paper deals with the Max-Mean Dispersion Problem (Max-Mean DP) belonging to the general category of clustering problems which aim to find a subset of a set which maximizes a measure of dispersion/similarity betwe...
详细信息
This paper deals with the Max-Mean Dispersion Problem (Max-Mean DP) belonging to the general category of clustering problems which aim to find a subset of a set which maximizes a measure of dispersion/similarity between elements. A three-phase hybrid heuristic was developed, which combines a mixed integer non-linear solver, a local branching scheme and a path relinking procedure. Computational results performed on the literature instances show that the proposed procedure outperforms the state-of-the-art approaches. (C) 2016 Elsevier Ltd. All rights reserved.
暂无评论