A simplex-based algorithm for 0-1 mixed integer programming

Jean Philippe P. Richard; Ismael R. De Farias; George L. Nemhauser

doi:10.1007/3-540-36478-1_15

A simplex-based algorithm for 0-1 mixed integer programming

Jean Philippe P. Richard, Ismael R. De Farias, George L. Nemhauser

Research output: Chapter in Book/Report/Conference proceeding › Chapter

2 Scopus citations

Abstract

We present a finitely convergent cutting plane algorithm for 0-1 mixed integer programming. The algorithm is a hybrid between a strong cutting plane and a Gomory-type algorithm that generates violated facet-defining inequalities of a relaxation of the simplex tableau and uses them as cuts for the original problem. We show that the cuts can be computed in polynomial time and can be embedded in a finitely convergent algorithm.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Michael Junger, Gerhard Reinelt, Giovanni Rinaldi
Publisher	Springer Verlag
Pages	158-170
Number of pages	13
ISBN (Print)	3540005803, 9783540005803
DOIs	https://doi.org/10.1007/3-540-36478-1_15
State	Published - 2003
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2570
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access

10.1007/3-540-36478-1_15

OpenUrl availability

Full text

Cite this

Richard, J. P. P., De Farias, I. R., & Nemhauser, G. L. (2003). A simplex-based algorithm for 0-1 mixed integer programming. In M. Junger, G. Reinelt, & G. Rinaldi (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 158-170). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2570). Springer Verlag. https://doi.org/10.1007/3-540-36478-1_15

A simplex-based algorithm for 0-1 mixed integer programming. / Richard, Jean Philippe P.; De Farias, Ismael R.; Nemhauser, George L.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Michael Junger; Gerhard Reinelt; Giovanni Rinaldi. Springer Verlag, 2003. p. 158-170 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2570).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Richard, JPP, De Farias, IR & Nemhauser, GL 2003, A simplex-based algorithm for 0-1 mixed integer programming. in M Junger, G Reinelt & G Rinaldi (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2570, Springer Verlag, pp. 158-170. https://doi.org/10.1007/3-540-36478-1_15

Richard JPP, De Farias IR, Nemhauser GL. A simplex-based algorithm for 0-1 mixed integer programming. In Junger M, Reinelt G, Rinaldi G, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 158-170. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-36478-1_15

Richard, Jean Philippe P. ; De Farias, Ismael R. ; Nemhauser, George L. / A simplex-based algorithm for 0-1 mixed integer programming. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Michael Junger ; Gerhard Reinelt ; Giovanni Rinaldi. Springer Verlag, 2003. pp. 158-170 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{7cdca75820db4d528e3b1a735de41859,

title = "A simplex-based algorithm for 0-1 mixed integer programming",

abstract = "We present a finitely convergent cutting plane algorithm for 0-1 mixed integer programming. The algorithm is a hybrid between a strong cutting plane and a Gomory-type algorithm that generates violated facet-defining inequalities of a relaxation of the simplex tableau and uses them as cuts for the original problem. We show that the cuts can be computed in polynomial time and can be embedded in a finitely convergent algorithm.",

author = "Richard, {Jean Philippe P.} and {De Farias}, {Ismael R.} and Nemhauser, {George L.}",

year = "2003",

doi = "10.1007/3-540-36478-1_15",

language = "English (US)",

isbn = "3540005803",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "158--170",

editor = "Michael Junger and Gerhard Reinelt and Giovanni Rinaldi",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - CHAP

T1 - A simplex-based algorithm for 0-1 mixed integer programming

AU - Richard, Jean Philippe P.

AU - De Farias, Ismael R.

AU - Nemhauser, George L.

PY - 2003

Y1 - 2003

N2 - We present a finitely convergent cutting plane algorithm for 0-1 mixed integer programming. The algorithm is a hybrid between a strong cutting plane and a Gomory-type algorithm that generates violated facet-defining inequalities of a relaxation of the simplex tableau and uses them as cuts for the original problem. We show that the cuts can be computed in polynomial time and can be embedded in a finitely convergent algorithm.

AB - We present a finitely convergent cutting plane algorithm for 0-1 mixed integer programming. The algorithm is a hybrid between a strong cutting plane and a Gomory-type algorithm that generates violated facet-defining inequalities of a relaxation of the simplex tableau and uses them as cuts for the original problem. We show that the cuts can be computed in polynomial time and can be embedded in a finitely convergent algorithm.

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

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

U2 - 10.1007/3-540-36478-1_15

DO - 10.1007/3-540-36478-1_15

M3 - Chapter

AN - SCOPUS:35248812555

SN - 3540005803

SN - 9783540005803

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 158

EP - 170

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Junger, Michael

A2 - Reinelt, Gerhard

A2 - Rinaldi, Giovanni

PB - Springer Verlag

ER -

A simplex-based algorithm for 0-1 mixed integer programming

Abstract

Publication series

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this