Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Intelligent medical expert system: addressing philosophical and logistical deficiencies of the rule-based medical expert system

Christopher A. Hughes

Published Jan 1, 1990• 1 citation
OpenAlex

Abstract

Quadratic programming is a fundamental problem in constrained optimization. One of the simplest quadratic programs has only simple bounds. In this thesis, we present several algorithms for the numerical solution of quadratic programs with simple bounds along with numerical results. All of our algorithms are designed for or applicable to the case where the Hessian matrix is large and sparse. Direct active set methods traditionally have not been used for large sparse problems because their storage requirements and data structure manipulations were thought to be prohibitive and because typical dense active set methods require a large number of iterations if the initial active set is very different from that at the solution. We show how a standard direct active set method for solving definite and indefinite quadratic programs with simple bounds can be efficiently implemented for large sparse problems. We show that all of the necessary factorizations can be carried out in a static data structure that can be set up before the numeric computations begin and requires only as much space as one Cholesky factorization of the Hessian of the quadratic. To allow us to add and delete several constraints from the active set at each iteration, we use projection techniques and a new search direction for the indefinite case. We also propose a heuristic method for finding a starting point that reduces the number of iterations required in practice. Iterative methods are attractive for large sparse quadratic programs because they require less data structure manipulation and hence are considerably easier to implement. The numerical results available for existing iterative methods indicate that they have linear rates of convergence. To avoid difficulties we experienced because of the feasibility requirement of interior point methods, we show how to reformulate a convex quadratic program with simple bounds as an unconstrained piecewise quadratic function with the same optimality conditions. We present an iterative method for solving this new problem that is superlinearly convergent and is suitable for sparse problems.

Related papers

Algorithms for unconstrained quadratic 0-1 programming and related problems on contemporary computer architectures

Gregory P. Rodgers

Unconstrained quadratic zero-one programming belongs to the class of NP-complete problems. It is therefore considered computationally intractable. Much research has been done in trying to find subsets of unconstrained quadratic 0-1 programs that can be solved in polynomial time. However, for the general problem, nonpolynomial methods must be used, resulting in limitations on the size of problems that can be solved. Branch and bound is a computational method that implicitly enumerates all possible solutions. Research on branch and bound algorithms is vast. Due to the computational complexity of the algorithm, efficient implementations are necessary in order to solve even moderate size problems. It is natural to expect that any implementation of a branch and bound algorithm may consume large amounts of computer resources due to the nature of the algorithm. Therefore, it is desirable to exploit contemporary high performance computers. In this thesis, efficiencies in the implementation of new 0-1 branch and bound algorithms on contemporary computer architectures are studied. Though not primarily designed for combinatorial problems, it is shown that many contemporary architectures, including distributed and shared memory multiprocessors, are capable of increasing the scope of solvable discrete programming problems. An application of unconstrained quadratic 0-1 programming is the maximum clique problem. It is shown that the variable selection rule in the proposed algorithm is equivalent to a nongreedy vertex selection rule for the maximum clique problem. This rule enhances the use of preprocessing rules that are applied to all branch and bound subproblems. By using this rule and by exploiting efficient data structures, maximum clique problems are solved for graphs of up to 1,000 vertices and 150,000 edges.

•Jan 3, 1990•4 citations

A Feasible Active Set Method with Reoptimization for Convex Quadratic Mixed-Integer Programming

Christoph Buchheim, Marianna De Santis, Stefano Lucidi +2 more

We propose a feasible active set method for convex quadratic programming problems with nonnegativity constraints. This method is specifically designed to be embedded into a branch-and-bound algorithm for convex quadratic mixed- integer programming problems. The branch-and-bound algorithm generalizes the approach for unconstrained convex quadratic integer programming proposed by Buchheim, Caprara, and Lodi [Math. Program., 135 (2012), pp. 369--395] to the presence of linear constraints. The main feature of the latter approach consists of a sophisticated preprocessing phase, leading to a fast enumeration of the branch-and-bound nodes. Moreover, the feasible active set method takes advantage of this preprocessing phase and is well suited for reoptimization. Experimental results for randomly generated instances show that the new approach significantly outperforms the MIQP solver of \tt CPLEX 12.6 for instances with a small number of constraints.

arXiv:1512.02369•SIAM Journal on Optimization•Jan 1, 2016•21 citations

Enhancing convexification techniques for solving nonconvex quadratic programming problems

Xiaofei Qi

At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory.With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has many valuable contributions and has attracted considerable interest over the past few decades.As a more general formulation, quadratically constrained quadratic programming (QCQP) problems arise naturally from a lot of applications such as facility location, production planning, economic equilibria and Euclidean distance geometry, etc.Most global optimization approaches for nonconvex QCQPs are based on constructing a convex or linear relaxation of the problem, and embedding it within an exhaustive search mechanism, where a lower bound is calculated as the value of the objective function of this relaxation (for a minimization problem) at each iteration of the search tree.The two principle elements affecting the overall effectiveness of such exhaustive search methods are the tightness of the underlying relaxation and the efficiency of calculating the lower bound.Besides, the performance of a branch-and-bound algorithm also relies on the procedure used to select a branching node and branching variable, which leads to good quality feasible solutions or equivalently an upper bound.vii LIST OF TABLES 5.5 Computational results of 0-1 QPs with n = 40 . . . . . . . . . . . .110 5.6 Computational results of 0-1 QPs with n = 50 . . . . . . . . . . . .

•Jan 1, 2017•0 citations

Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques

Wei Xia, Juan C. Vera, Luis F. Zuluaga

We reformulate a (indefinite) quadratic program (QP) as a mixed-integer linear programming (MILP) problem by first reformulating a QP as a linear complementary problem, and then using binary variables and big-M constraints to model its complementary constraints. To obtain such reformulation, we use fundamental results on the solution of perturbed linear systems to impose bounds on the QP’s dual variables without eliminating any of its (globally) optimal primal solutions. Reformulating a nonconvex QP as a MILP problem allows the use of current state-of-the-art MILP solvers to find its global optimal solution. To illustrate this, we compare the performance of this MILP-based solution approach, labeled quadprogIP, with quadprogBB, BARON, and CPLEX. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. Also, unlike quadprogBB, quadprogIP is able to solve QP instances in which the dual feasible set is unbounded. The MATLAB code quadprogIP and the instances used to perform the reported numerical experiments are publicly available at https://github.com/xiawei918/quadprogIP .

arXiv:1511.02423•INFORMS journal on computing•Jul 19, 2019•55 citations

Polynomial unconstrained binary optimisation â part 2

Fred Glover, Jin‐Kao Hao, Gary A. Kochenberger

The class of problems known as quadratic zero-one (binary) unconstrained optimization has provided access to a vast array of combinatorial optimization problems, allowing them to be expressed within the setting of a single unifying model. A gap exists, however, in addressing polynomial problems of degree greater than 2. to bridge this gap, we provide methods for efficiently executing core search processes for the general polynomial unconstrained binary (PUB) optimization problem. A variety of search algorithms for quadratic optimization can take advantage of our methods to be transformed directly into algorithms for problems where the objective functions involve arbitrary polynomials. Part 1 of this paper (Glover, Hao and Kochenberger, 2010) provided fundamental results for carrying out the transformations and described coding and decoding procedures relevant for efficiently handling sparse problems, where many coefficients are 0, as typically arise in practical applications. In the present Part 2 paper, we provide special algorithms and data structures for taking advantage of the basic results of Part 1. We also disclose how our designs can be used to enhance existing quadratic optimization algorithms.

International Journal of Metaheuristics•Jan 1, 2011•12 citations

A Direct SDP Approach for Constrained Quadratic Binary Optimization Problems

MilaNedic, Zvmcevap

This repository contains the source code, computational experiments, analysis, and benchmarks accompanying the paper A Direct SDP-Based Framework for Certified Bounds for Constrained Quadratic Binary Optimization Problems. The repository implements a direct semidefinite programming (SDP) approach for constrained quadratic binary optimization, designed to obtain strong bounds for exact optimization. The SDP relaxation is strengthened using quadratized linear constraints and triangle (hypermetric) inequalities. To address the numerical infeasibility of SDP solutions obtained from numerical solvers such as MOSEK, the framework includes a correction procedure that converts approximate SDP solutions into mathematically certified bounds suitable for use in Branch-and-Bound algorithms. The repository also implements an adaptation of the Goemans–Williamson randomized hyperplane rounding scheme to constrained binary optimization, together with problem-specific feasibility restoration. Computational experiments are provided for the Sparsest k-Subgraph and Maximum Independent Set problems. The work presented in this repository was funded and developed under the QBIQ project (project no. 644), funded by the Slovenian Research and Innovation Agency (ARIS) through the Applied Projects programme. The code and accompanying data are intended to facilitate reproducibility of the computational results and provide a foundation for further research on exact SDP-based methods for constrained quadratic binary optimization.

•Aug 25, 2026•0 citations
Quadratic programming is a fundamental problem in constrained optimization. One of the simplest quadratic programs has only simple bounds. In this thesis, we present several algorithms for the numerical solution of quadratic programs with simple bounds along with numerical results. All of our algorithms are designed for or applicable to the case where the Hessian matrix is large and sparse.
Direct active set methods traditionally have not been used for large sparse problems because their storage requirements and data structure manipulations were thought to be prohibitive and because typical dense active set methods require a large number of iterations if the initial active set is very different from that at the solution. We show how a standard direct active set method for solving definite and indefinite quadratic programs with simple bounds can be efficiently implemented for large sparse problems. We show that all of the necessary factorizations can be carried out in a static data structure that can be set up before the numeric computations begin and requires only as much space as one Cholesky factorization of the Hessian of the quadratic. To allow us to add and delete several constraints from the active set at each iteration, we use projection techniques and a new search direction for the indefinite case. We also propose a heuristic method for finding a starting point that reduces the number of iterations required in practice.
Iterative methods are attractive for large sparse quadratic programs because they require less data structure manipulation and hence are considerably easier to implement. The numerical results available for existing iterative methods indicate that they have linear rates of convergence. To avoid difficulties we experienced because of the feasibility requirement of interior point methods, we show how to reformulate a convex quadratic program with simple bounds as an unconstrained piecewise quadratic function with the same optimality conditions. We present an iterative method for solving this new problem that is superlinearly convergent and is suitable for sparse problems.
Unconstrained quadratic zero-one programming belongs to the class of NP-complete problems. It is therefore considered computationally intractable. Much research has been done in trying to find subsets of unconstrained quadratic 0-1 programs that can be solved in polynomial time. However, for the general problem, nonpolynomial methods must be used, resulting in limitations on the size of problems that can be solved. Branch and bound is a computational method that implicitly enumerates all possible solutions. Research on branch and bound algorithms is vast. Due to the computational complexity of the algorithm, efficient implementations are necessary in order to solve even moderate size problems. It is natural to expect that any implementation of a branch and bound algorithm may consume large amounts of computer resources due to the nature of the algorithm. Therefore, it is desirable to exploit contemporary high performance computers. In this thesis, efficiencies in the implementation of new 0-1 branch and bound algorithms on contemporary computer architectures are studied. Though not primarily designed for combinatorial problems, it is shown that many contemporary architectures, including distributed and shared memory multiprocessors, are capable of increasing the scope of solvable discrete programming problems. An application of unconstrained quadratic 0-1 programming is the maximum clique problem. It is shown that the variable selection rule in the proposed algorithm is equivalent to a nongreedy vertex selection rule for the maximum clique problem. This rule enhances the use of preprocessing rules that are applied to all branch and bound subproblems. By using this rule and by exploiting efficient data structures, maximum clique problems are solved for graphs of up to 1,000 vertices and 150,000 edges.
We propose a feasible active set method for convex quadratic programming problems with nonnegativity constraints. This method is specifically designed to be embedded into a branch-and-bound algorithm for convex quadratic mixed- integer programming problems. The branch-and-bound algorithm generalizes the approach for unconstrained convex quadratic integer programming proposed by Buchheim, Caprara, and Lodi [Math. Program., 135 (2012), pp. 369--395] to the presence of linear constraints. The main feature of the latter approach consists of a sophisticated preprocessing phase, leading to a fast enumeration of the branch-and-bound nodes. Moreover, the feasible active set method takes advantage of this preprocessing phase and is well suited for reoptimization. Experimental results for randomly generated instances show that the new approach significantly outperforms the MIQP solver of \tt CPLEX 12.6 for instances with a small number of constraints.
At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory.With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has many valuable contributions and has attracted considerable interest over the past few decades.As a more general formulation, quadratically constrained quadratic programming (QCQP) problems arise naturally from a lot of applications such as facility location, production planning, economic equilibria and Euclidean distance geometry, etc.Most global optimization approaches for nonconvex QCQPs are based on constructing a convex or linear relaxation of the problem, and embedding it within an exhaustive search mechanism, where a lower bound is calculated as the value of the objective function of this relaxation (for a minimization problem) at each iteration of the search tree.The two principle elements affecting the overall effectiveness of such exhaustive search methods are the tightness of the underlying relaxation and the efficiency of calculating the lower bound.Besides, the performance of a branch-and-bound algorithm also relies on the procedure used to select a branching node and branching variable, which leads to good quality feasible solutions or equivalently an upper bound.vii LIST OF TABLES 5.5 Computational results of 0-1 QPs with n = 40 . . . . . . . . . . . .110 5.6 Computational results of 0-1 QPs with n = 50 . . . . . . . . . . . .
We reformulate a (indefinite) quadratic program (QP) as a mixed-integer linear programming (MILP) problem by first reformulating a QP as a linear complementary problem, and then using binary variables and big-M constraints to model its complementary constraints. To obtain such reformulation, we use fundamental results on the solution of perturbed linear systems to impose bounds on the QP’s dual variables without eliminating any of its (globally) optimal primal solutions. Reformulating a nonconvex QP as a MILP problem allows the use of current state-of-the-art MILP solvers to find its global optimal solution. To illustrate this, we compare the performance of this MILP-based solution approach, labeled quadprogIP, with quadprogBB, BARON, and CPLEX. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. Also, unlike quadprogBB, quadprogIP is able to solve QP instances in which the dual feasible set is unbounded. The MATLAB code quadprogIP and the instances used to perform the reported numerical experiments are publicly available at https://github.com/xiawei918/quadprogIP .
The class of problems known as quadratic zero-one (binary) unconstrained optimization has provided access to a vast array of combinatorial optimization problems, allowing them to be expressed within the setting of a single unifying model. A gap exists, however, in addressing polynomial problems of degree greater than 2. to bridge this gap, we provide methods for efficiently executing core search processes for the general polynomial unconstrained binary (PUB) optimization problem. A variety of search algorithms for quadratic optimization can take advantage of our methods to be transformed directly into algorithms for problems where the objective functions involve arbitrary polynomials. Part 1 of this paper (Glover, Hao and Kochenberger, 2010) provided fundamental results for carrying out the transformations and described coding and decoding procedures relevant for efficiently handling sparse problems, where many coefficients are 0, as typically arise in practical applications. In the present Part 2 paper, we provide special algorithms and data structures for taking advantage of the basic results of Part 1. We also disclose how our designs can be used to enhance existing quadratic optimization algorithms.
This repository contains the source code, computational experiments, analysis, and benchmarks accompanying the paper A Direct SDP-Based Framework for Certified Bounds for Constrained Quadratic Binary Optimization Problems. The repository implements a direct semidefinite programming (SDP) approach for constrained quadratic binary optimization, designed to obtain strong bounds for exact optimization. The SDP relaxation is strengthened using quadratized linear constraints and triangle (hypermetric) inequalities. To address the numerical infeasibility of SDP solutions obtained from numerical solvers such as MOSEK, the framework includes a correction procedure that converts approximate SDP solutions into mathematically certified bounds suitable for use in Branch-and-Bound algorithms. The repository also implements an adaptation of the Goemans–Williamson randomized hyperplane rounding scheme to constrained binary optimization, together with problem-specific feasibility restoration. Computational experiments are provided for the Sparsest k-Subgraph and Maximum Independent Set problems. The work presented in this repository was funded and developed under the QBIQ project (project no. 644), funded by the Slovenian Research and Innovation Agency (ARIS) through the Applied Projects programme. The code and accompanying data are intended to facilitate reproducibility of the computational results and provide a foundation for further research on exact SDP-based methods for constrained quadratic binary optimization.