We present an exact mixed-integer programming (MIP) solution scheme where a set-covering model is used to find a small set of first-choice branching variables. In a preliminary "sampling" phase, our method q...
详细信息
We present an exact mixed-integer programming (MIP) solution scheme where a set-covering model is used to find a small set of first-choice branching variables. In a preliminary "sampling" phase, our method quickly collects a number of relevant low-cost fractional solutions that qualify as obstacles for the linear programming (LP) relaxation bound improvement. Then a set covering model is solved to detect a small subset of variables (a "backdoor," in the artificial intelligence jargon) that "cover the fractionality" of the collected fractional solutions. These backdoor variables are put in a priority branching list, and a black-box MIP solver is eventually run-in its default mode-by taking this list into account, thus avoiding any other interference with its highly optimized internal mechanisms. Computational results on a large set of instances from the literature are presented, showing that some speedup can be achieved even with respect to a state-of-the-art solver such as IBM ILOG CPLEX 12.2.
We propose mixed-integer programming models for fitting univariate discrete data points with continuous piecewise linear (PWL) functions. The number of approximating function segments and the locations of break points...
详细信息
We propose mixed-integer programming models for fitting univariate discrete data points with continuous piecewise linear (PWL) functions. The number of approximating function segments and the locations of break points are optimized simultaneously. The proposed models include linear constraints and convex objective function and, thus, are computationally more efficient than previously proposed mixed-integer nonlinear programming models. We also show how the proposed models can be extended to approximate univariate functions with PWL functions with the minimum number of segments subject to bounds on the pointwise error.
In this paper, we develop an exact reformulation and a deterministic approximation for distributionally robust joint chance-constrained programmings (DRCCPs) with a general class of convex uncertain constraints under ...
详细信息
In this paper, we develop an exact reformulation and a deterministic approximation for distributionally robust joint chance-constrained programmings (DRCCPs) with a general class of convex uncertain constraints under data-driven Wasserstein ambiguity sets. It is known that robust chance constraints can be conservatively approximated by worst-case conditional value-at-risk (CVaR) constraints. It is shown that the proposed worst-case CVaR approximation model can be reformulated as an optimization problem involving biconvex constraints for joint DRCCP. This approximation is essentially exact under certain conditions. We derive a convex relaxation of this approximation model by constructing new decision variables which allows us to eliminate biconvex terms. Specifically, when the constraint function is affine in both the decision variable and the uncertainty, the resulting approximation model is equivalent to a tractable mixed-integer convex reformulation for joint binary DRCCP. Numerical results illustrate the computational effectiveness and superiority of the proposed formulations.
Common interventions to control the spread of cholera include improving sanitation, hygiene, and access to safe drinking water and providing epidemic regions with sufficient treatment kits and oral vaccines. Due to re...
详细信息
Common interventions to control the spread of cholera include improving sanitation, hygiene, and access to safe drinking water and providing epidemic regions with sufficient treatment kits and oral vaccines. Due to resources limitation, these interventions should be guided by a risk assessment of cholera-affected regions, thereby targeting regions based on their risk level. Cholera risk assessment is very challenging because of the lack of precise and reliable data. This study proposes an approach for cholera risk assessment and vaccine allocation, which consists of two phases: (i) cholera risk assessment, where a fuzzy inference system (FIS) is proposed to evaluate the risk level of cholera-affected regions based on five cholera risk indicators: (1) attack rate, (2) case fatality rate, (3) the number of internally displaced persons, (4) accessibility of water, sanitation and hygiene, and (5) accessibility of cholera treatment;(ii) cholera vaccine allocation, where a mixed-integer programming model is used to optimize the allocation of limited vaccine doses among multiple regions over multiple periods while considering the risk level, population of regions, and vaccine efficacy. The model answers the questions of where, what amounts, and when to send vaccines during a 2-year horizon. Implementation of the proposed approach is illustrated using a case study from Yemen, which is currently experiencing the world's worst cholera outbreak according to the World Health Organization. The results reveal the usefulness of the proposed approach in mapping the cholera risk, which in turn is used as effective guidance for the allocation of cholera vaccine.
It is known from algebraic graph theory that if L is the Laplacian matrix of some tree G with a vertex degree sequence d = (delta(1),..., delta(n)). and D is its distance matrix, then LD + 2I = (2 center dot 1 - d)1(i...
详细信息
It is known from algebraic graph theory that if L is the Laplacian matrix of some tree G with a vertex degree sequence d = (delta(1),..., delta(n)). and D is its distance matrix, then LD + 2I = (2 center dot 1 - d)1(inverted perpendicular), where 1 is an all-ones column vector. We prove the converse proposition: if this identity holds for the Laplacian matrix of some graph G with a degree sequence d and for some matrix D, then G is essentially a tree, and D is its distance matrix. This result immediately generalizes to weighted graphs. Therefore, the above bilinear matrix equation in L, D, and d characterizes trees in terms of their Laplacian and distance matrices, so it can be used as a constraint in mixed-integer formulations of distance-related tree topology design problems (e.g., optimum communication spanning tree or hop-constrained minimum spanning tree problems). If the matrix D is symmetric, the lower triangular part of this matrix identity is redundant and can be omitted, which halves the number of constraints in an optimization problem. Applications to the extremal graph theory (especially, to topological index optimization and to optimal tree problems) and to road topology design are discussed. (C) 2021 Elsevier B.V. All rights reserved.
We consider the problem of minimizing a sum of clipped convex functions. Applications of this problem include clipped empirical risk minimization and clipped control. While the problem of minimizing the sum of clipped...
详细信息
We consider the problem of minimizing a sum of clipped convex functions. Applications of this problem include clipped empirical risk minimization and clipped control. While the problem of minimizing the sum of clipped convex functions is NP-hard, we present some heuristics for approximately solving instances of these problems. These heuristics can be used to find good, if not global, solutions, and appear to work well in practice. We also describe an alternative formulation, based on the perspective transformation, that makes the problem amenable to mixed-integer convex programming and yields computationally tractable lower bounds. We illustrate our heuristic methods by applying them to various examples and use the perspective transformation to certify that the solutions are relatively close to the global optimum. This paper is accompanied by an open-source implementation.
We consider the dynamic facility location problem with generalized modular capacities, a multiperiod facility location problem in which the costs for capacity changes may differ for all pairs of capacity levels. The p...
详细信息
We consider the dynamic facility location problem with generalized modular capacities, a multiperiod facility location problem in which the costs for capacity changes may differ for all pairs of capacity levels. The problem embeds a complex cost structure and generalizes several existing facility location problems, such as those that allow temporary facility closing or capacity expansion and reduction. As the model may become very large, general-purpose mixed-integer programming (MIP) solvers are limited to solving instances of small to medium size. In this paper, we extend the generalized model to the case of multiple commodities. We propose Lagrangian heuristics, based on subgradient and bundle methods, to find good quality solutions for large-scale instances with up to 250 facility locations and 1,000 customers. To improve the final solution quality, a restricted MIP model is solved based on the information collected through the solution of the Lagrangian dual. Computational results show that the Lagrangian-based heuristics provide highly reliable results for all problem variants considered. They produce good quality solutions in short computing times even for instances where state-of-the-art MIP solvers do not find feasible solutions. The strength of the formulation also allows the method to provide tight bounds on the optimal value.
For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Came and Schultz from a computational perspective with the aim of its parallelization. We address an important bottleneck of parall...
详细信息
For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Came and Schultz from a computational perspective with the aim of its parallelization. We address an important bottleneck of parallel execution by identifying a formulation that permits the parallel solution of the master program by using structure-exploiting interior-point solvers. Our results demonstrate the potential for parallel speedup and the importance of regularization (stabilization) in the dual optimization. Load imbalance is identified as a remaining barrier to parallel scalability. (C) 2013 Elsevier B.V. All rights reserved.
We consider nonlinear optimization problems that involve surrogate models represented by neural networks. We demonstrate first how to directly embed neural network evaluation into optimization models, highlight a diff...
详细信息
We consider nonlinear optimization problems that involve surrogate models represented by neural networks. We demonstrate first how to directly embed neural network evaluation into optimization models, highlight a difficulty with this approach that can prevent convergence, and then characterize stationarity of such models. We then present two alternative formulations of these problems in the specific case of feedforward neural networks with ReLU activation: as a mixed-integer optimization problem and as a mathematical program with complementarity constraints. For the latter formulation we prove that stationarity at a point for this problem corresponds to stationarity of the embedded formulation. Each of these formulations may be solved with state-of-the-art optimization methods, and we show how to obtain good initial feasible solutions for these methods. We compare our formulations on three practical applications arising in the design and control of combustion engines, in the generation of adversarial attacks on classifier networks, and in the determination of optimal flows in an oil well network.
Recent technological advances in power electronics and electrical storage have increased interest in the arbitrage business based on Battery Energy Storage Systems. With this objective, the present work develops a Mix...
详细信息
Recent technological advances in power electronics and electrical storage have increased interest in the arbitrage business based on Battery Energy Storage Systems. With this objective, the present work develops a mixed-integer Linear programming model for obtaining optimal electricity sale\purchase strategies with batteries. For each configuration (battery size /inverter size), the model provides an optimal trading strategy. Using this strategy for different configurations and with the current market prices, some financial indicators are calculated in order to select the optimal configuration. Finally, our analysis considers the significant technological progress that has occurred in recent years, the effects on profitability of a reduction in the battery cost, and of an improvement both in the round-trip efficiency and in the battery's lifetime (in terms of the number of cycles). The results indicate that, with current technology, the optimal inverter size for a 10 MWh battery is 3 MW, although, if technological progress continues at the current rate, the arbitrage of electricity by using batteries is expected to be viable from 2024 onwards. Additionally, the effects that different technological improvements (cost, useful life and losses) will have on profitability are calculated,;for example, it is observed that an improvement of 1.6% of the round-trip efficiency and an increase of 1000 life cycles will provide an average increase of 16,000 (sic) and 75,000 (sic), respectively, in terms of Net Present Value.
暂无评论