Movatterモバイル変換

[0]ホーム
URL:

×

zbMATH Open — the first resource for mathematics

from until
Reset all

Examples

GeometrySearch for the termGeometry inany field. Queries arecase-independent.
Funct*Wildcard queries are specified by* (e .g.functions,functorial, etc.). Otherwise the search isexact.''Topological group'':Phrases (multi - words) should be set in''straight quotation marks''.
au: Bourbaki & ti: AlgebraSearch forauthorBourbaki andtitleAlgebra. Theand-operator & is default and can be omitted.
Chebyshev | TschebyscheffTheor-operator| allows to search forChebyshev orTschebyscheff.
Quasi* map* py: 1989The resulting documents havepublicationyear1989.
so:Eur* J* Mat* Soc* cc:14Search for publications in a particularsource with aMathematics SubjectClassificationcode in14.
cc:*35 ! any:ellipticSearch for documents about PDEs (prefix with * to search only primary MSC); the not-operator ! eliminates all results containing the wordelliptic.
dt: b & au: HilbertThedocumenttype is set tobooks; alternatively:j forjournal articles,a forbookarticles.
py: 2000 - 2015 cc:(94A | 11T)Numberranges when searching forpublicationyear are accepted . Terms can be grouped within( parentheses).
la: chineseFind documents in a givenlanguage .ISO 639 - 1 (opens in new tab) language codes can also be used.
st: c r sFind documents that arecited, havereferences and are from asingle author.

Fields

ab Text from the summary or review (for phrases use “. ..”)
an zbMATH ID, i.e.: preliminary ID, Zbl number, JFM number, ERAM number
any Includes ab, au, cc, en, rv, so, ti, ut
arxiv arXiv preprint number
au Name(s) of the contributor(s)
br Name of a person with biographic references (to find documents about the life or work)
cc Code from the Mathematics Subject Classification (prefix with* to search only primary MSC)
ci zbMATH ID of a document cited in summary or review
db Database: documents in Zentralblatt für Mathematik/zbMATH Open (db:Zbl), Jahrbuch über die Fortschritte der Mathematik (db:JFM), Crelle's Journal (db:eram), arXiv (db:arxiv)
dt Type of the document: journal article (dt:j), collection article (dt:a), book (dt:b)
doi Digital Object Identifier (DOI)
ed Name of the editor of a book or special issue
en External document ID: DOI, arXiv ID, ISBN, and others
in zbMATH ID of the corresponding issue
la Language (use name, e.g.,la:French, orISO 639-1, e.g.,la:FR)
li External link (URL)
na Number of authors of the document in question. Interval search with “-”
pt Reviewing state: Reviewed (pt:r), Title Only (pt:t), Pending (pt:p), Scanned Review (pt:s)
pu Name of the publisher
py Year of publication. Interval search with “-”
rft Text from the references of a document (for phrases use “...”)
rn Reviewer ID
rv Name or ID of the reviewer
se Serial ID
si swMATH ID of software referred to in a document
so Bibliographical source, e.g., serial title, volume/issue number, page range, year of publication, ISBN, etc.
st State: is cited (st:c), has references (st:r), has single author (st:s)
sw Name of software referred to in a document
ti Title of the document
ut Keywords

Operators

a & bLogical and (default)
a | bLogical or
!abLogical not
abc*Right wildcard
ab cPhrase
(ab c)Term grouping

See also ourGeneral Help.

Lagrangean decomposition: A model yielding stronger Lagrangean bounds.(English)Zbl 0638.90074

Given a mixed-integer programming problem with two matrix constraints, it is possible to define a Lagrangean relaxation such that the relaxed problem decomposes additively into two subproblems, each having one of the two matrices of the original problem as its constraints. There is one Lagrangean multiplier per variable. We prove that the optimal value of this new Lagrangean dual dominates the optimal value of the Lagrangean dual obtained by relaxing one set of constraints and give a necessary condition for a strict improvement. We show on an example that the resulting bound improvement can be substantial. We show on a complex practical problem how Lagrangean decomposition may help uncover hidden special structures and thus yield better solution methodology.

MSC:

90C11 Mixed integer programming
49M27 Decomposition methods
65K05 Numerical mathematical programming methods

Cite

References:

[1]O. Bilde and J. Krarup, ”Bestemmelse af optimal beliggenhed af produktionssteder” Research Report, IMSOR, The Technical University of Denmark (1967).
[2]O. Bilde and J. Krarup, ”Sharp Lower Bounds and Efficient Algorithms for the Simple Plant Location Problem,”Annals of Discrete Mathematics 1 (1977) 79–97. ·Zbl 0364.90068 ·doi:10.1016/S0167-5060(08)70728-3
[3]M.E. Dyer, ”Calculating Surrogate Constraints,”Mathematical Programming 19 (1980) 255–278. ·Zbl 0464.90067 ·doi:10.1007/BF01581647
[4]D. Erlenkotter, ”A Dual-Based Procedure for Uncapacitated Facility Location,”Operations Research 26 (1978) 992–1009. ·Zbl 0422.90053 ·doi:10.1287/opre.26.6.992
[5]M.L. Fisher, R. Jaikumar and L. Van Wassenhove, ”A Multiplier Adjustment Method for the Generalized Assignment Problem,”Management Science 32 (1986) 1095–1103. ·Zbl 0626.90036 ·doi:10.1287/mnsc.32.9.1095
[6]A. Frank, ”A Weighted Matroid Intersection Algorithm,”Journal of Algorithms 2 (1981) 328–336. ·Zbl 0484.05025 ·doi:10.1016/0196-6774(81)90032-8
[7]B. Gavish and H. Pirkul, ”Efficient Algorithms for Solving Multiconstraint Zero-One Knapsack Problems to Optimality,”Mathematical Programming 31 (1985) 78–105. ·Zbl 0571.90065 ·doi:10.1007/BF02591863
[8]A. Geoffrion, ”Lagrangean Relaxation and its Uses in Integer Programming,”Mathematical Programming Study 2 (1974) 82–114. ·Zbl 0395.90056
[9]F. Glover and J. Mulvey, ”The Equivalence of the 0–1 Integer Programming Problem to Discrete Generalized and Pure Network Models,” Report HBS 75-46, Harvard University (1975), alsoOperations Research 28 (1980) 829–933. ·Zbl 0443.90064
[10]F. Glover and D. Klingman, ”Layering Strategies for Creating Exploitable Structure in Linear and Integer Programs,” Center for Business Decision Analysis Report 119 (1984, revised 1985). ·Zbl 0667.90070
[11]H.J. Greenberg and W.P. Pierskalla, ”Surrogate Mathematical Programming,”Operations Research 18 (1970) 924–939. ·Zbl 0232.90059 ·doi:10.1287/opre.18.5.924
[12]M. Guignard, ”A Lagrangean Dual Ascent Method Based on (Separable) Relaxation Strengthened by Valid Inequalities (Illustrated for the Matching Problem),” Department of Statistics Report #54, University of Pennsylvania (1983).
[13]M. Guignard, ”A Lagrangean Dual Ascent Method for Simple Plant Location Problems,” Department of Statistics Report #59, University of Pennsylvania (1984a), to appear inEuropean J. Oper. Res. ·Zbl 0696.90025
[14]M. Guignard, ”Lagrangean Decomposition: An Improvement over Lagrangean and Surrogate Duals,” Department of Statistics Report #62, University of Pennsylvania (1984b).
[15]M. Guignard and S. Kim, ”A Strong Lagrangean Relaxation for Capacitated Plant Locations Problems,” Department of Statistics Report #56, University of Pennsylvania (1983).
[16]M. Guignard and K. Opaswongkarn, ”Lagrangean Ascent for the Capacitated Plant Location Problem,” Department of Statistics Report #57, University of Pennsylvania (1984). ·Zbl 0719.90051
[17]M. Guignard and M. Rosenwein, ”An Application of Lagrangean Decomposition to the Resource Constrained Minimum Weighted Arborescence Problem,” AT&T Bell Laboratories Report (1987). ·Zbl 0701.90064
[18]M. Guignard and K. Spielberg ”Separable Lagrangean Relaxation for Weakly-Linked Mixed Integer Programming Problems,”Methods of Operations Research 49 (1985) 239–253. ·Zbl 0564.90048
[19]G.Y. Handler and I. Zang, ”A Dual Algorithm for the Constrained Shortest Path Problem,”Networks 10 (1980) 293–310. ·Zbl 0453.68033 ·doi:10.1002/net.3230100403
[20]K.O. Jörnsten, M. Näsberg and P.A. Smeds, ”Variable splitting–A New Lagrangean Relaxation Approach to Some Mathematical Programming Models,” Department of Mathematics Report LiTHMAT-R-85-04, Linköping Institute of Technology, Sweden (1985).
[21]M.H. Karwan and R.L. Rardin, ”Some Relationships between Lagrangean and Surrogate Duality in Integer Programming,”Mathematical Programming 18 (1979) 320–334. ·Zbl 0421.90056 ·doi:10.1007/BF01588253
[22]S. Kim, oral communication (1984).
[23]S. Kim, ”Solving Single Side Constraint Problems in Integer Programming: the Inequality Case,” Department of Statistics, Report #60, University of Pennsylvania (1984).
[24]S. Kim, ”Primal Interpretation of Lagrangean Decomposition” Department of Statistics Report #72, University of Pennsylvania (1985).
[25]M. Minoux, ”Plus courts chemins avec contraintes: algorithmes et applications,”Annales des Télécommunications 30 (1975) 383–394. ·Zbl 0347.90065
[26]M. Minoux, ”Lagrangean Decomposition,” oral communication (1983).
[27]C. Ribeiro, ”Algorithmes de Recherche de Plus Courts Chemins avec Contraintes: Etude Théorique, Implémentation et Parallélisation,” Doctoral Dissertation, Paris (1983).
[28]C. Ribeiro and M. Minoux, ”Solving Hard Constrained Shortest Path Problems,” ORSA-TIMS Meeting, Dallas (1984). ·Zbl 0549.90073
[29]C. Ribeiro and M. Minoux, ”Solving Hard Constrained Shortest Path Problems by Lagrangean Relaxation and Branch and Bound Algorithms,”Methods of Operations Research 53 (1986) 303–316. ·Zbl 0596.90091
[30]F. Shepardson and R. Marsten, ”A Lagrangean Relaxation Algorithm for the Two-Duty Period Scheduling Problem,”Management Science 26 (1980) 274–281. ·Zbl 0448.90042 ·doi:10.1287/mnsc.26.3.274
[31]R. Wong, ”A Dual Ascent Approach for Steiner Tree Problems on a Directed Graph,”Mathematical Programming 28 (1984) 271–287. ·Zbl 0532.90092 ·doi:10.1007/BF02612335
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
© 2025FIZ Karlsruhe GmbHPrivacy PolicyLegal NoticesTerms & Conditions
  • Mastodon logo
 (opens in new tab)
[8]ページ先頭
©2009-2025 Movatter.jp