서브메뉴
검색
Generalized Submodular Optimization: Theory, Algorithms and Applications- [electronic resource]
Generalized Submodular Optimization: Theory, Algorithms and Applications- [electronic resource]
상세정보
- 자료유형
- 학위논문파일 국외
- 최종처리일시
- 20240214101638
- ISBN
- 9798380145183
- DDC
- 621.3
- 저자명
- Yu, Qimeng.
- 서명/저자
- Generalized Submodular Optimization: Theory, Algorithms and Applications - [electronic resource]
- 발행사항
- [S.l.]: : Northwestern University., 2023
- 발행사항
- Ann Arbor : : ProQuest Dissertations & Theses,, 2023
- 형태사항
- 1 online resource(264 p.)
- 주기사항
- Source: Dissertations Abstracts International, Volume: 85-02, Section: B.
- 주기사항
- Advisor: Kucukyavuz, Simge.
- 학위논문주기
- Thesis (Ph.D.)--Northwestern University, 2023.
- 사용제한주기
- This item must not be sold to any third party vendors.
- 초록/해제
- 요약Submodularity is a well-known concept in integer programming and combinatorial optimization. Submodular set functions capture the diminishing returns phenomenon, which has wide-ranging applications in various domains. Typically, a submodular set function models the utility of homogenous items selected from a single ground set. Selecting an item or not is naturally represented by one or zero. Therefore, optimizing submodular set functions is a class of interesting mixed-integer programming (MIP) problems with binary variables. In practice, many problem contexts call for extensions of submodularity-we may select multiple copies of homogenous items or choose heterogenous items from distinct ground sets. We refer to the optimization problems arising from such extensions of submodularity as Generalized Submodular Optimization (GSO). In GSO, the objective function is usually highly nonlinear, and the decision space is mixed-integer. These challenges make GSO a broad subclass of mixed-integer nonlinear programming (MINLP) problems. In this dissertation, we present theory, algorithms, and applications of GSO. Specifically, we explore the optimization problems with classical submodular set functions and two classes of generalized submodular functions, under constraints. We provide polyhedral theory for the underlying mixed-integer structures in these problems. Our theoretical results lead to efficient and versatile exact solution methods, which have demonstrated their effectiveness in practical problems using real-world datasets.
- 일반주제명
- Computer engineering.
- 키워드
- Convex hull
- 키워드
- Polyhedral
- 기타저자
- Northwestern University Industrial Engineering and Management Sciences
- 기본자료저록
- Dissertations Abstracts International. 85-02B.
- 기본자료저록
- Dissertation Abstract International
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008240612s2023 us |||||||||||||||c||eng d■001000016934651
■00520240214101638
■006m o d
■007cr#unu||||||||
■020 ▼a9798380145183
■035 ▼a(MiAaPQ)AAI30632166
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a621.3
■1001 ▼aYu, Qimeng.
■24510▼aGeneralized Submodular Optimization: Theory, Algorithms and Applications▼h[electronic resource]
■260 ▼a[S.l.]:▼bNorthwestern University. ▼c2023
■260 1▼aAnn Arbor :▼bProQuest Dissertations & Theses, ▼c2023
■300 ▼a1 online resource(264 p.)
■500 ▼aSource: Dissertations Abstracts International, Volume: 85-02, Section: B.
■500 ▼aAdvisor: Kucukyavuz, Simge.
■5021 ▼aThesis (Ph.D.)--Northwestern University, 2023.
■506 ▼aThis item must not be sold to any third party vendors.
■520 ▼aSubmodularity is a well-known concept in integer programming and combinatorial optimization. Submodular set functions capture the diminishing returns phenomenon, which has wide-ranging applications in various domains. Typically, a submodular set function models the utility of homogenous items selected from a single ground set. Selecting an item or not is naturally represented by one or zero. Therefore, optimizing submodular set functions is a class of interesting mixed-integer programming (MIP) problems with binary variables. In practice, many problem contexts call for extensions of submodularity-we may select multiple copies of homogenous items or choose heterogenous items from distinct ground sets. We refer to the optimization problems arising from such extensions of submodularity as Generalized Submodular Optimization (GSO). In GSO, the objective function is usually highly nonlinear, and the decision space is mixed-integer. These challenges make GSO a broad subclass of mixed-integer nonlinear programming (MINLP) problems. In this dissertation, we present theory, algorithms, and applications of GSO. Specifically, we explore the optimization problems with classical submodular set functions and two classes of generalized submodular functions, under constraints. We provide polyhedral theory for the underlying mixed-integer structures in these problems. Our theoretical results lead to efficient and versatile exact solution methods, which have demonstrated their effectiveness in practical problems using real-world datasets.
■590 ▼aSchool code: 0163.
■650 4▼aComputer engineering.
■653 ▼aConvex hull
■653 ▼aMixed-integer programming
■653 ▼aNonlinear optimization
■653 ▼aPolyhedral
■653 ▼aGeneralized Submodular Optimization
■690 ▼a0796
■690 ▼a0464
■71020▼aNorthwestern University▼bIndustrial Engineering and Management Sciences.
■7730 ▼tDissertations Abstracts International▼g85-02B.
■773 ▼tDissertation Abstract International
■790 ▼a0163
■791 ▼aPh.D.
■792 ▼a2023
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T16934651▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
■980 ▼a202402▼f2024
