B&B method for discrete partial order optimization

Vladimir I. Norkin ()
Additional contact information
Vladimir I. Norkin: National Academy of Sciences of Ukraine

Computational Management Science, 2019, vol. 16, issue 4, No 3, 577-592

Abstract: Abstract The paper extends the branch and bound (B&B) method, primarily developed for the solution of global, discrete, and vector programming problems, to finding nondominated points in a partially ordered space/set. The framework of the generalized B&B method is standard, it includes partition, estimation, and pruning steps, but bounds are different, they are set-valued, and, as a particular case, the bounds may be singletons. For bounding, the method uses a set ordering in the following sense. One set is “less or equal” than the other if for any element of the first set there is a “greater or equal” element in the second one. The defined set ordering is a partial order in the space of sets consisting of mutually nondominated elements. In the B&B method, partitioning is applied to the parts of the original space with nondominated upper bounds. Parts with small upper bounds (less than some lower bound) are pruned. Convergence of the method to the set of all nondominated points is established. The acceleration with respect to the enumerative search is achieved through group evaluation of elements of the original space. Further, the developed B&B method is extended to vector partial order optimization. In the latter case, several partial orders are defined in the decision space. Finally, we develop a B&B method for a so-called constrained partial order optimization problem, where the feasible set is defined by a family of partial orders.

Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10287-019-00346-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:comgts:v:16:y:2019:i:4:d:10.1007_s10287-019-00346-4

Ordering information: This journal article can be ordered from
http://www.springer. ... ch/journal/10287/PS2

DOI: 10.1007/s10287-019-00346-4

Access Statistics for this article

Computational Management Science is currently edited by Ruediger Schultz

More articles in Computational Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().