Pipeline transport is the major means for large-scale and long-distance CO2 transport in a CO2 capture and sequestration (CCS) project. But optimal design of the pipeline network remains a challenging problem, especia...
详细信息
Pipeline transport is the major means for large-scale and long-distance CO2 transport in a CO2 capture and sequestration (CCS) project. But optimal design of the pipeline network remains a challenging problem, especially when considering allocation of intermediate sites, like pump stations, and selection of pipeline routes. A superstructure-based mixed-integer programming approach for optimal design of the pipeline network, targeting on minimizing the overall cost in a CCS project is presented. A decomposition algorithm to solve the computational difficulty caused by the large size and nonlinear nature of a real-life design problem is also presented. To illustrate the capability of our models. A real-life case study in North China, with 45 emissions sources and four storage sinks, is provided. The result shows that our model and decomposition algorithm is a practical and cost-effective method for pipeline networks design. (c) 2014 American Institute of Chemical Engineers
Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming. A decomposition method with wide applicability is Benders...
详细信息
Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming. A decomposition method with wide applicability is Benders' decomposition, which has been applied to both stochastic programming as well as integerprogramming problems. However, this method of decomposition relies on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s) is not convex, and new approaches must be designed. In this paper, we discuss alternative decomposition methods in which the second-stage integer subproblems are solved using branch-and-cut methods. One of the main advantages of our decomposition scheme is that Stochastic mixed-integer programming (SMIP) problems can be solved by dividing a large problem into smaller MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage stochastic mixed-integer programs.
Significance Important advances in modeling chemical production scheduling problems have been made in recent years, yet effective solution methods are still required. We use an algorithm that uses process network and ...
详细信息
Significance Important advances in modeling chemical production scheduling problems have been made in recent years, yet effective solution methods are still required. We use an algorithm that uses process network and customer demand information to formulate powerful valid inequalities that substantially improve the solution process. In particular, we extend the ideas recently developed for discrete-time formulations to continuous-time models and show that these tightening methods lead to a significant decrease in computational time, up to more than three orders of magnitude for some instances. (c) 2013 American Institute of Chemical Engineers AIChE J, 59: 4461-4467, 2013
We present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions due to Yarotsky...
详细信息
We present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions due to Yarotsky (Neural Netw 94:103-114, 2017), formulating this (simple) approximation using mixed-integer programming (MIP). Notably, the number of constraints, binary variables, and auxiliary continuous variables used in this formulation grows logarithmically in the approximation error. Combining this with a diagonal perturbation technique to convert a nonseparable quadratic function into a separable one, we present a mixed-integer convex quadratic relaxation for nonconvex quadratic optimization problems. We study the strength (or sharpness) of our formulation and the tightness of its approximation. Further, we show that our formulation represents feasible points via a Gray code. We close with computational results on problems with quadratic objectives and/or constraints, showing that our proposed method (i) across the board outperforms existing MIP relaxations from the literature, and (ii) on hard instances produces better bounds than exact solvers within a fixed time budget.
This article considers the problem of maximizing the lifetime of a wireless sensor network with a mobile sink. The sink travels at finite speed among a subset of possible sink locations to collect data from a stationa...
详细信息
This article considers the problem of maximizing the lifetime of a wireless sensor network with a mobile sink. The sink travels at finite speed among a subset of possible sink locations to collect data from a stationary set of sensor nodes. The considered problem chooses a subset of sink locations for the sink to visit, finds a tour for the sink among the selected sink locations, and prescribes an optimal data routing scheme from the sensor nodes to each location visited by the sink. The sink's tour is constrained by the time it spends at each location collecting data. Two variations of this problem are examined based on assumptions regarding delay tolerance. Exact mixed-integer programming formulations to model this problem are provided along with cutting planes, preprocessing techniques, and a Benders decomposition algorithm to improve its solvability. Computational results demonstrate the effectiveness of the proposed methods.
We give an explicit geometric way to build mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of spanning hyperplanes in an r-dimensional linear space. ...
详细信息
We give an explicit geometric way to build mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of spanning hyperplanes in an r-dimensional linear space. The resulting MIP formulation is ideal, and uses exactly r integer variables and 2 x (#of spanning hyperplanes) general inequality constraints. We use this result to derive novel logarithmic-sized ideal MIP formulations for discontinuous piecewise linear functions and structures appearing in robotics and power systems problems. (C) 2019 Elsevier B.V. All rights reserved.
Fast computation of valid linear programming (LP) bounds serves as an important subroutine for solving mixed-integer programming problems exactly. We introduce a new method for computing valid LP bounds designed for t...
详细信息
Fast computation of valid linear programming (LP) bounds serves as an important subroutine for solving mixed-integer programming problems exactly. We introduce a new method for computing valid LP bounds designed for this application. The algorithm corrects approximate LP dual solutions to be exactly feasible, giving a valid bound. Solutions are repaired by performing a projection and a shift to ensure all constraints are satisfied;bound computations are accelerated by reusing structural information through the branch-and-bound tree. We demonstrate this method to be widely applicable and faster than solving a sequence of exact LPs. Several variations of the algorithm are described and computationally evaluated in an exact branch-and-bound algorithm within the mixed-integer programming framework SCIP (Solving Constraint integerprogramming).
As the development and population of North America continues to grow, the demand for environmentally friendly or clean energy generation is becoming more of an issue. We present a model that addresses the energy techn...
详细信息
As the development and population of North America continues to grow, the demand for environmentally friendly or clean energy generation is becoming more of an issue. We present a model that addresses the energy technologies that may continue to be used and new clean energy technologies that should be introduced in energy generation. The approach involves a Stochastic mixed-integer Program (SMIP) that minimizes cost and emission levels associated with energy generation while meeting energy demands of a given region. The results provide encouraging outcomes with respect to cost, emission levels, and energy-technologies that should be utilized for future generation. (C) 2011 Elsevier Ltd. All rights reserved.
This paper considers the class scheduling and timetabling problem faced at Kuwait University (KU). The principal focus is to design efficient class offering patterns while taking into consideration newly imposed gende...
详细信息
This paper considers the class scheduling and timetabling problem faced at Kuwait University (KU). The principal focus is to design efficient class offering patterns while taking into consideration newly imposed gender policies. We formulate a mathematical programming model that assigns offered classes to time-slots and addresses gender issues by defining appropriate surrogate constraints along with objective penalty terms. The model aims to enhance existing manual scheduling and timetabling approaches that are often accompanied with arduous combinatorial tasks such as resolving class conflicts, dealing with parking and traffic congestion, and ensuring an efficient utilization of facility and human resources. This modeling approach emphasizes the generation of flexible class timetables for students, and the efficient utilization of available facility resources. Computational results based on a number of case studies related to Kuwait University reveal that this approach yields improved schedules in terms of offering patterns and class conflicts. (c) 2006 Elsevier B.V. All rights reserved.
An exact algorithm is developed for the chance-constrained multi-area reserve sizing problem in the presence of transmission network constraints. The problem can be cast as a two-stage stochastic mixedinteger linear ...
详细信息
An exact algorithm is developed for the chance-constrained multi-area reserve sizing problem in the presence of transmission network constraints. The problem can be cast as a two-stage stochastic mixedinteger linear program using sample approximation. Due to the complicated structure of the problem, existing methods attempt to find a feasible solution based on heuristics. Existing mixed-integer algorithms that can be applied directly to a two-stage stochastic program can only address small-scale problems that are not practical. We have found a minimal description of the projection of our problem onto the space of the first-stage variables. This enables us to directly apply more general integerprogramming techniques for mixing sets, that arise in chance-constrained problems. Combining the advantages of the minimal projection and the strengthening reformulation from IP techniques, our method can tackle real-world problems. We specifically consider a case study of the 10-zone Nordic network with 100,000 scenarios where the optimal solution can be found in approximately 5 minutes.
暂无评论