Demand for earth observation satellite imagery is pervasive and increasing rapidly across multiple domains, highlighting the key problem to optimally schedule satellite image acquisition/collection, subject to ground ...
详细信息
Demand for earth observation satellite imagery is pervasive and increasing rapidly across multiple domains, highlighting the key problem to optimally schedule satellite image acquisition/collection, subject to ground and on-board constraints. Despite the variety of reported approaches to solving the NP-hard multi-satellite scheduling problem (m-SatSP), serious limitations still prevail, largely overlooking problem structure exploitation and/or domain knowledge. Assuming a few constraints, problem modelling-or scope-is often confined to a simple trailing satellite constellation composition perspective and tends to conveniently oversimplify footprint coverage intricacies. As a result, adequate problem task decomposition properly reflecting complex kinematic behaviour for an ad hoc satellite constellation remains elusive. Known approaches also fail to provide valuable solution optimality gap estimations to objectively qualify best computed solution and/or to control run-time execution in solving hard problem instances. In this paper, a novel approach to solving the single objective static m-SatSP is proposed. It is based on network flow optimization using mathematical programming. Unlike previous methods, QUEST (quadratically constrainEd program Solver Technology) relies on a sound alternative approximate objective function and, the exploitation of exact problem-solving techniques. Derived from domain knowledge and problem structure considerations, QUEST generalizes problem modelling to successfully handle virtual constellation, avoiding unsuitable utilization of traditional area coverage decomposition scheme. The proposed decision model concurrently captures coverage approximation, imaging success uncertainty and quality for a variety of tasks. It also includes new and optional constraints while embracing an acceptable upper bound on collection value. A QUEST variant alternatively relying on "delayed reward" to bridge promising search regions on move selection, furthe
We propose a state-smoothing algorithm for hybrid systems based on moving-horizon estimation (MHE) by exploiting the equivalence between hybrid systems modeled in the mixed logic dynamical form and piecewise affine sy...
详细信息
We propose a state-smoothing algorithm for hybrid systems based on moving-horizon estimation (MHE) by exploiting the equivalence between hybrid systems modeled in the mixed logic dynamical form and piecewise affine systems. We provide sufficient conditions on the time horizon and the penalties on the state at the beginning of the estimation horizon to guarantee asymptotic convergence of the MHE scheme. Moreover, we propose two practical algorithms for the computation of penalties that allow to implement MHE by solving a mixed-integerquadratic program.
Thermal unit commitment (UC) is a nonlinear combinatorial optimization problem that minimizes total operating costs while considering system load balance, on/off restrictions and other constraints. Successfully solvin...
详细信息
Thermal unit commitment (UC) is a nonlinear combinatorial optimization problem that minimizes total operating costs while considering system load balance, on/off restrictions and other constraints. Successfully solving the thermal UC problem contributes to a more reliable power system and reduces thermal costs. This paper presents an exact mixed-integer quadratic programming (EMIQP) method for large-scale thermal UC problems. EMIQP revolutionizes the landscape by seamlessly translating the intricate nonlinear combinatorial optimization problem of UC into an exact mixed-integerquadratic formulation. This approach also elegantly reimagines on/off constraints as mixed-integer linear equations, employing both the sum and respective approaches. Our case studies unequivocally demonstrate the exceptional prowess of the EMIQP method, consistently securing the global optimum. Moreover, the mathematical-based EMIQP method produces identical results at each run, which is extremely important for UC in the real world.
作者：
Bertsimas, DimitrisShioda, RomyUniv Waterloo
Dept Combinator & Optimizat Fac Math Waterloo ON N2L 3G1 Canada MIT
Alfred P Sloan Sch Management Cambridge MA 02139 USA MIT
Ctr Operat Res Cambridge MA 02139 USA
This paper describes an algorithm for cardinality-constrained quadratic optimization problems, which are convex quadraticprogramming problems with a limit on the number of non-zeros in the optimal solution. In partic...
详细信息
This paper describes an algorithm for cardinality-constrained quadratic optimization problems, which are convex quadraticprogramming problems with a limit on the number of non-zeros in the optimal solution. In particular, we consider problems of subset selection in regression and portfolio selection in asset management and propose branch-and-bound based algorithms that take advantage of the special structure of these problems. We compare our tailored methods against CPLEX's quadraticmixed-integer solver and conclude that the proposed algorithms have practical advantages for the special class of problems we consider.
We derive new mixed-integerquadratic, quadratically constrained, and second-order cone programming models of distribution system reconfiguration, which are to date the first formulations of the ac problem that have c...
详细信息
We derive new mixed-integerquadratic, quadratically constrained, and second-order cone programming models of distribution system reconfiguration, which are to date the first formulations of the ac problem that have convex, continuous relaxations. Each model can be reliably and efficiently solved to optimality using standard commercial software. In the course of deriving each model, we obtain original quadratically constrained and second-order cone approximations to power flow in radial networks.
In a recent paper [6] we suggested an algorithm for solving complicated mixed-integerquadratic programs, based on an equivalent formulation that employs a nonsingular transformation of variables. The objectives of th...
详细信息
In a recent paper [6] we suggested an algorithm for solving complicated mixed-integerquadratic programs, based on an equivalent formulation that employs a nonsingular transformation of variables. The objectives of the present paper are two. First, to present an improved version of this algorithm, which reduces substantially its computational requirements; second, to report on the results of a computational study with the revised algorithm.
Detection of critical nodes in complex networks has recently received extensive attention. Currently, studies of the critical nodes problem (CNP) mainly focus on two problem types: "critical nodes problem/positiv...
详细信息
Detection of critical nodes in complex networks has recently received extensive attention. Currently, studies of the critical nodes problem (CNP) mainly focus on two problem types: "critical nodes problem/positive" (CNP-Pos) and "critical nodes problem/negative" (CNP-Neg). However, to the best of our knowledge, few studies have been conducted on CNP-Neg for weighed networks. In this paper, we investigate CNP-Neg in undirected weighted networks. We first propose a novel metric D-FW to evaluate network fragmentation. Then, we formulate a new nonconvex mixed-integer quadratic programming model, named MIQPM, that aims to simultaneously minimize pairwise connectivity and maximize the weights between the nodes. After that, a general greedy algorithm is employed to solve the corresponding optimization problem. Finally, comparison experiments are carried out for several synthetic networks and four real-world networks to demonstrate the effectiveness of the proposed approaches. (C) 2019 Elsevier B.V. All rights reserved.
Planning infrastructure networks such as roads, pipelines, waterways, power lines and telecommunication systems, require estimations on the future demand as well as other uncertain factors such as operating costs, deg...
详细信息
Planning infrastructure networks such as roads, pipelines, waterways, power lines and telecommunication systems, require estimations on the future demand as well as other uncertain factors such as operating costs, degradation rates, or the like. When trying to construct infrastructure that is either optimal from a social welfare or profit perspective (depending on a public or private sector focus), typically researchers treat the uncertainties in the problem by using robust optimization methods. The goal of robust optimization is to find optimal solutions that are relatively insensitive to uncertain factors. This paper presents an efficient and tractable approach for finding robust optimum solutions to linear and, more importantly, quadraticprogramming problems with interval uncertainty using a worst case analysis. For linear, mixed-integer linear, and mixed-integer problems with quadratic objective and constraint functions, our robust formulations have the same complexity and tractability as their deterministic counterparts. Numerous examples with differing difficulties and complexities, especially with selected ones on network planning/operations problems, have been tested to demonstrate the viability of the proposed approach. The results show that the computational effort of the proposed approach, in terms of the number of function calls, for the robust problems is comparable to or even better than that of deterministic problems in some cases.
There are usually many sources for the supply of raw material to a pulp or paper mill in Sweden. Optimization of this supply is therefore a challenging task, and can only be managed properly if all aspects of risk are...
详细信息
There are usually many sources for the supply of raw material to a pulp or paper mill in Sweden. Optimization of this supply is therefore a challenging task, and can only be managed properly if all aspects of risk are considered. In our study, these risks are related to when the weather reduces the load-bearing capacity of the ground or the roads. A stochastic and a deterministic model have been formulated, and they have been solved with mixed-integer quadratic programming and tested with data from a Swedish forest company. The results of this study show that the option value is greater than zero and that both the optimal policy and the option value change whenever the storage cost is altered. This shows that the optimal planning policy obtained from the stochastic model differs from the solution of the deterministic model.
A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown-by several authors using different techniques-t...
详细信息
A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown-by several authors using different techniques-that the convex hull of the intersection of an ellipsoid, , and a split disjunction, with , equals the intersection of with an additional second-order-cone representable (SOCr) set. In this paper, we study more general intersections of the form and , where is a SOCr cone, is a nonconvex cone defined by a single homogeneous quadratic, and H is an affine hyperplane. Under several easy-to-verify conditions, we derive simple, computable convex relaxations and , where is a SOCr cone. Under further conditions, we prove that these two sets capture precisely the corresponding conic/convex hulls. Our approach unifies and extends previous results, and we illustrate its applicability and generality with many examples.
暂无评论