A simple effective heuristic for embedded mixed-integer quadratic programming
From MaRDI portal
Publication:5207801
Abstract: In this paper we propose a fast optimization algorithm for approximately minimizing convex quadratic functions over the intersection of affine and separable constraints (i.e., the Cartesian product of possibly nonconvex real sets). This problem class contains many NP-hard problems such as mixed-integer quadratic programming. Our heuristic is based on a variation of the alternating direction method of multipliers (ADMM), an algorithm for solving convex optimization problems. We discuss the favorable computational aspects of our algorithm, which allow it to run quickly even on very modest computational platforms such as embedded processors. We give several examples for which an approximate solution should be found very quickly, such as management of a hybrid-electric vehicle drivetrain and control of switched-mode power converters. Our numerical experiments suggest that our method is very effective in finding a feasible point with small objective value; indeed, we find that in many cases, it finds the global solution.
Recommendations
- An approximation algorithm for indefinite mixed integer quadratic programming
- Compact mixed-integer programming formulations in quadratic optimization
- Improved algorithm for mixed-integer quadratic programs and a computational study
- Heuristics for convex mixed integer nonlinear programs
- A note on solving quadratic programs using mixed-integer programming
- On approximation algorithms for concave mixed-integer quadratic programming
- On approximation algorithms for concave mixed-integer quadratic programming
- A branch and bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation
- scientific article; zbMATH DE number 3920195
- A dual heuristic for mixed integer programming
Cites work
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 1219584 (Why is no real title available?)
- scientific article; zbMATH DE number 1312984 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A Real-Time Iteration Scheme for Nonlinear Optimization in Optimal Feedback Control
- A branch-and-cut method for 0-1 mixed convex programming
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- A feasibility pump heuristic for general mixed-integer problems
- A universal lattice code decoder for fading channels
- Alternating direction method of multipliers for real and complex polynomial optimization models
- An alternating direction algorithm for matrix completion with nonnegative factors
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Branch-and-Bound Methods: A Survey
- CVXGEN: a code generator for embedded convex optimization
- Computational study of a family of mixed-integer quadratic programming problems
- Condition numbers and equilibration of matrices
- Consensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic Signals
- Consensus-ADMM for General Quadratically Constrained Quadratic Programming
- Control of systems integrating logic, dynamics, and constraints
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Dual coordinate step methods for linear network flow problems
- Global convergence of splitting methods for nonconvex composite optimization
- Improving the feasibility pump
- Introduction to nonlinear optimization: theory, algorithms, and applications with MATLAB
- Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs
- Nonconvex Splitting for Regularized Low-Rank + Sparse Decomposition
- Numerical Optimization
- On cutting-plane proofs in combinatorial optimization
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- On the facial structure of set packing polyhedra
- Online Object Tracking With Sparse Prototypes
- Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems
- Outline of an algorithm for integer solutions to linear programs
- Parallel Algorithms for Constrained Tensor Factorization via Alternating Direction Method of Multipliers
- Receding Horizon Control
- Reducibility among combinatorial problems
- Solving propositional satisfiability problems
- The feasibility pump
- qpOASES: a parametric active-set algorithm for~quadratic programming
Cited in
(10)- A general system for heuristic minimization of convex functions over non-convex sets
- The voice of optimization
- Low-Complexity Method for Hybrid MPC with Local Guarantees
- Decomposition methods for global solution of mixed-integer linear programs
- Exact augmented Lagrangian duality for mixed integer quadratic programming
- Penalty alternating direction methods for mixed-integer optimal control with combinatorial constraints
- Alternating direction method of multipliers for truss topology optimization with limited number of nodes: a cardinality-constrained second-order cone programming approach
- Training recurrent neural networks by sequential least squares and the alternating direction method of multipliers
- Sparse loss-aware ternarization for neural networks
- An ADMM based method for underdetermined box-constrained integer least squares problems
This page was built for publication: A simple effective heuristic for embedded mixed-integer quadratic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207801)
