The bound improving sequence algorithm

Paulo Bárcia

doi:10.1016/0167-6377(85)90047-1

The bound improving sequence algorithm

Paulo Bárcia

NOVA School of Business and Economics (NOVA SBE)

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

Abstract

The purpose of this paper is to report on a new tool to help solve 0-1 LP's. It consists of a sequence of bounds that, under proper conditions, bridge the duality gap, i.e., converges in a finite number of steps to the optimal value of the objective function of the problem studied. As a by-product an optimal solution for that problem is produced. Computational experience is reported.

Original language	English
Pages (from-to)	27-30
Number of pages	4
Journal	Operations Research Letters
Volume	4
Issue number	1
DOIs	https://doi.org/10.1016/0167-6377(85)90047-1
Publication status	Published - 1 Jan 1985

Keywords

0-1
integer programs
knapsack problem
Lagrangean relaxation

Access to Document

10.1016/0167-6377(85)90047-1

Cite this

@article{5d451760925b4e389092d551a01fd501,

title = "The bound improving sequence algorithm",

abstract = "The purpose of this paper is to report on a new tool to help solve 0-1 LP's. It consists of a sequence of bounds that, under proper conditions, bridge the duality gap, i.e., converges in a finite number of steps to the optimal value of the objective function of the problem studied. As a by-product an optimal solution for that problem is produced. Computational experience is reported.",

keywords = "0-1, integer programs, knapsack problem, Lagrangean relaxation",

author = "Paulo B{\'a}rcia",

year = "1985",

month = jan,

day = "1",

doi = "10.1016/0167-6377(85)90047-1",

language = "English",

volume = "4",

pages = "27--30",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - The bound improving sequence algorithm

AU - Bárcia, Paulo

PY - 1985/1/1

Y1 - 1985/1/1

N2 - The purpose of this paper is to report on a new tool to help solve 0-1 LP's. It consists of a sequence of bounds that, under proper conditions, bridge the duality gap, i.e., converges in a finite number of steps to the optimal value of the objective function of the problem studied. As a by-product an optimal solution for that problem is produced. Computational experience is reported.

AB - The purpose of this paper is to report on a new tool to help solve 0-1 LP's. It consists of a sequence of bounds that, under proper conditions, bridge the duality gap, i.e., converges in a finite number of steps to the optimal value of the objective function of the problem studied. As a by-product an optimal solution for that problem is produced. Computational experience is reported.

KW - 0-1

KW - integer programs

KW - knapsack problem

KW - Lagrangean relaxation

UR - http://www.scopus.com/inward/record.url?scp=0022067201&partnerID=8YFLogxK

U2 - 10.1016/0167-6377(85)90047-1

DO - 10.1016/0167-6377(85)90047-1

M3 - Article

AN - SCOPUS:0022067201

SN - 0167-6377

VL - 4

SP - 27

EP - 30

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

The bound improving sequence algorithm

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this