자료유형  

 학위논문

Control Number  

0016934953

International Standard Book Number  

9798380142410

Dewey Decimal Classification Number  

510

Main Entry-Personal Name  

Soni, Akhilesh.

Publication, Distribution, etc. (Imprint  

[S.l.] : The University of Wisconsin - Madison., 2023

Publication, Distribution, etc. (Imprint  

Ann Arbor : ProQuest Dissertations & Theses, 2023

Physical Description  

1 online resource(172 p.)

General Note  

Source: Dissertations Abstracts International, Volume: 85-02, Section: B.

General Note  

Advisor: Linderoth, Jeffrey;Luedtke, James.

Dissertation Note  

Thesis (Ph.D.)--The University of Wisconsin - Madison, 2023.

Restrictions on Access Note  

This item must not be sold to any third party vendors.

Summary, Etc.  

요약The thesis consists of research in mixed integer linear programming with applications to scheduling and matrix completion. We first study the problem of scheduling drilling and fracturing of pads in the development of an unconventional oil field. We propose a novel MILP formulation for solving this scheduling problem which considers capacity, operational, precedence, and interference constraints. We also propose a formulation that uses more decision variables, but which provides a stronger linear programming relaxation. Due to the large problem size, solving the full MILP model for instances with many pads and a large number of time periods is intractable. Thus, we also derive a MILP-based rolling horizon framework that solves a sequence of limited horizon, coarser-scale MILP instances in a rolling forward fashion to obtain a solution to the full horizon problem on the daily time scale. We benchmark this approach against a baseline scheduling algorithm that approximates current practice of scheduling pads in the order of discounted production profit with limited lookahead. Our results show that our proposed MILP-based rolling horizon approach can improve the net present value of a field by 4-6%.Next, we present new integer programming approaches to matrix completion problems, both in the real field and in the finite field GF(2). First, we study an integer programming approach for subspace clustering with missing data problem in real field with an assumption that underlying data comes from a union of subspaces. Subspace clustering with missing data is the task of identifying clusters of vectors belonging to the same subspace in a partially observed data matrix whose columns are assumed to lie in a union of K subspaces. We propose a novel mixed-integer linear programming solution framework (MISS-DSG) for this problem that is based on dynamically determining a set of candidate subspaces and optimally assigning data points to the closest selected subspace. MISS-DSG handles a large number of candidate subspaces through its use of Benders decomposition and dynamically generates new candidate subspaces through its use of column generation. We cast the subspace generation problem as a nonlinear, nonconvex optimization problem and propose a gradient-based approximate solution approach. The model has the advantage of integrating the subspace generation and clustering in a single, unified optimization framework without requiring any hyperparameter tuning when number of subspaces and subspaces dimensions are known. Our computational results reveal that the proposed method can achieve higher clustering accuracy than state-of-the-art methods when data is of high-rank, the percentage of missing data is high, or subspaces are close to each other.We next discuss binary matrix completion methods in GF(2) where the arithmetic is done with respect to modulo-2 operations. We give integer linear programming formulations for matrix factorization and completion in GF(2). We first derive formulations making use of McCormick envelopes for the product of two binary variables: a base formulation using a general integer variable and an extended formulation using ideas from disjunctive programming and parity polytopes. The latter formulation characterizes the convex hull of the dot product of two vectors in an extended space. We then derive a novel formulation based on a new class of valid inequalities that also characterizes the convex hull of the dot product in the original space of variables. Our computational results reveal that the proposed formulation results in smaller branch-and-bound trees. Furthermore, we also derive additional classes of valid inequalities linking dot products between two matrix elements.

Subject Added Entry-Topical Term  

Mathematics.

Subject Added Entry-Topical Term  

Computer science.

Index Term-Uncontrolled  

Benders decomposition

Index Term-Uncontrolled  

Column generation

Index Term-Uncontrolled  

Integer programming

Index Term-Uncontrolled  

Matrix completion

Index Term-Uncontrolled  

Scheduling

Index Term-Uncontrolled  

Valid inequalities

Added Entry-Corporate Name  

The University of Wisconsin - Madison Industrial Engineering

Host Item Entry  

Dissertations Abstracts International. 85-02B.

Host Item Entry  

Dissertation Abstract International

Electronic Location and Access  

로그인을 한후 보실 수 있는 자료입니다.

Control Number  

joongbu:640640