Bivalent quadratic programming problem - A computational study (Q801811)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3880438
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Bivalent quadratic programming problem - A computational study |
scientific article; zbMATH DE number 3880438 |
Statements
Bivalent quadratic programming problem - A computational study (English)
0 references
1984
0 references
Consider the problem of minimizing a quadratic function of n zero-one variables, i.e. minimize \(x^ tQx\), subject to \(x\in B^ n_ 2\), where Q is an \(n\times n\) symmetric matrix and \(B_ 2=\{0,1\}\). A branch-and- bound algorithm is proposed. Problems which are difficult to solve by this method are identified and a heuristic algorithm for their solution is suggested. Computational experience relating to the effectiveness of the two algorithms is indicated.
0 references
branch-and-bound algorithm
0 references
heuristic algorithm
0 references
Computational experience
0 references
0.8998896479606628
0 references
0.8744405508041382
0 references
0.8544695973396301
0 references
0.8381890654563904
0 references
0.8274142146110535
0 references
