A Lagrangian relaxation approach to the edge-weighted clique problem
From MaRDI portal
Publication:5937353
DOI10.1016/S0377-2217(99)00449-XzbMath1039.90044WikidataQ127663449 ScholiaQ127663449MaRDI QIDQ5937353
Walter Kern, Ulrich Faigle, Marcel Hunting
Publication date: 2001
Published in: European Journal of Operational Research (Search for Journal in Brave)
linear programmingLagrangian relaxationcutting planeboolean quadric polytopeclique polytopecut polytopequadratic knapsack polytope
Programming involving graphs or networks (90C35) Integer programming (90C10) Boolean programming (90C09)
Related Items
Selecting hierarchical facilities in a service-operations environment, A new family of facet defining inequalities for the maximum edge-weighted clique problem, The effect of strengthened linear formulations on improving the lower bounds for the part families with precedence constraints problem, Iterated tabu search for the maximum diversity problem, Dynamic bundle methods, Solving the maximum edge weight clique problem via unconstrained quadratic programming, Approximation with a fixed number of solutions of some multiobjective maximization problems, A new branch-and-bound algorithm for the maximum edge-weighted clique problem, New facets and a branch-and-cut algorithm for the weighted clique problem., Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement, A nonconvex quadratic optimization approach to the maximum edge weight clique problem, Solving the maximum edge-weight clique problem in sparse graphs with compact formulations, Decomposition and dynamic cut generation in integer linear programming, Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem, A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem, Stronger \(K\)-tree relaxations for the vehicle routing problem, Cutting planes for RLT relaxations of mixed 0-1 polynomial programs, Non delayed relax-and-cut algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Facets of the clique partitioning polytope
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- Experiments in quadratic 0-1 programming
- Facets for the cut cone. I
- Facets for the cut cone. II: Clique-web inequalities
- On the Boolean-quadric packing uncapacitated facility-location polytope
- An extended formulation approach to the edge-weighted maximal clique problem
- A cutting-plane approach to the edge-weighted maximal clique problem
- Min-cut clustering
- Cardinality constrained Boolean quadratic polytope
- The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
- The discrete p-maxian location problem
- A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Heuristically determining cliques of given cardinality and with minimal cost within weighted complete graphs
- A restricted Lagrangean approach to the traveling salesman problem
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Faces for a linear inequality in 0–1 variables
- On convergence rates of subgradient optimization methods
- Heuristic and Special Case Algorithms for Dispersion Problems
- Quadratic knapsack relaxations using cutting planes and semidefinite programming
- Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
- On the cut polytope
- Validation of subgradient optimization
- A Branch and Bound Algorithm for Integer Quadratic Knapsack Problems
- Convergence rate of the gradient descent method with dilatation of the space
