Mixed-integer convex model for VAr expansion planning

This paper presents a mixed-integer convex-optimization-based approach for optimum investment reactive power sources in transmission systems. Unlike some convex-optimization techniques for the reactive power planning solution, in the proposed approach the taps settings of under-load tap-changing of transformers are modeled as a mixed-integer linear set equations. Are also considered the continuous and discrete variables for the existing and new capacitive and reactive power sources. The problem is solved for three significant demand scenarios (low demand, average demand and peak demand). Numerical results are presented for the CIGRE-32 electric power system.

Generating cluster submodels from a multistage stochastic mixed integer optimization model using break stage

We present a scheme to generate clusters submodels with stage ordering from a (symmetric or a nonsymmetric one) multistage stochastic mixed integer optimization model using break stage. We consider a stochastic model in compact representation and MPS format with a known scenario tree. The cluster submodels are built by storing first the 0-1 the variables, stage by stage, and then the continuous ones, also stage by stage. A C++ experimental code has been implemented for reordering the stochastic model as well as the cluster decomposition after the relaxation of the non-anticipativiy constraints until the so-called breakstage. The computational experience shows better performance of the stage ordering in terms of elapsed time in a randomly generated testbed of multistage stochastic mixed integer problems.

A mixed-integer LP model for the reconfiguration of radial electric distribution systems considering distributed generation

The problem of reconfiguration of distribution systems considering the presence of distributed generation is modeled as a mixed-integer linear programming (MILP) problem in this paper. The demands of the electric distribution system are modeled through linear approximations in terms of real and imaginary parts of the voltage, taking into account typical operating conditions of the electric distribution system. The use of an MILP formulation has the following benefits: (a) a robust mathematical model that is equivalent to the mixed-integer non-linear programming model; (b) an efficient computational behavior with exiting MILP solvers; and (c) guarantees convergence to optimality using classical optimization techniques. Results from one test system and two real systems show the excellent performance of the proposed methodology compared with conventional methods. © 2012 Published by Elsevier B.V. All rights reserved.

A mixed-integer LP model for the optimal allocation of voltage regulators and capacitors in radial distribution systems

This paper presents a mixed-integer linear programming model to solve the problem of allocating voltage regulators and fixed or switched capacitors (VRCs) in radial distribution systems. The use of a mixed-integer linear model guarantees convergence to optimality using existing optimization software. In the proposed model, the steady-state operation of the radial distribution system is modeled through linear expressions. The results of one test system and one real distribution system are presented in order to show the accuracy as well as the efficiency of the proposed solution technique. An heuristic to obtain the Pareto front for the multiobjective VRCs allocation problem is also presented. © 2012 Elsevier Ltd. All rights reserved.

A unified mixed-integer programming model for simultaneous fluence weight and aperture optimization in VMAT, tomotherapy, and cyberknife

All rights reserved. In this paper, we propose and study a unified mixed-integer programming model that simultaneously optimizes fluence weights and multi-leaf collimator (MLC) apertures in the treatment planning optimization of VMAT, Tomotherapy, and CyberKnife. The contribution of our model is threefold: (i) Our model optimizes the fluence and MLC apertures simultaneously for a given set of control points. (ii) Our model can incorporate all volume limits or dose upper bounds for organs at risk (OAR) and dose lower bound limits for planning target volumes (PTV) as hard constraints, but it can also relax either of these constraint sets in a Lagrangian fashion and keep the other set as hard constraints. (iii) For faster solutions, we propose several heuristic methods based on the MIP model, as well as a meta-heuristic approach. The meta-heuristic is very efficient in practice, being able to generate dose- and machinery-feasible solutions for problem instances of clinical scale, e.g., obtaining feasible treatment plans to cases with 180 control points, 6750 sample voxels and 18,000 beamlets in 470 seconds, or cases with 72 control points, 8000 sample voxels and 28,800 beamlets in 352 seconds. With discretization and down-sampling of voxels, our method is capable of tackling a treatment field of 8000-64,000cm3, depending on the ratio of critical structure versus unspecified tissues.

Reactive power planning under conditional-value-at-risk assessment using chance-constrained optimisation

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Optimal conductor size selection and reconductoring in radial distribution systems using a mixed-integer LP approach

This paper presents a mixed-integer linear programming model to solve the conductor size selection and reconductoring problem in radial distribution systems. In the proposed model, the steady-state operation of the radial distribution system is modeled through linear expressions. The use of a mixed-integer linear model guarantees convergence to optimality using existing optimization software. The proposed model and a heuristic are used to obtain the Pareto front of the conductor size selection and reconductoring problem considering two different objective functions. The results of one test system and two real distribution systems are presented in order to show the accuracy as well as the efficiency of the proposed solution technique. © 1969-2012 IEEE.

Managing daily surgery schedules in a teaching hospital: a mixed-integer optimization approach

Background: This study examined the daily surgical scheduling problem in a teaching hospital. This problem relates to the use of multiple operating rooms and different types of surgeons in a typical surgical day with deterministic operation durations (preincision, incision, and postincision times). Teaching hospitals play a key role in the health-care system; however, existing models assume that the duration of surgery is independent of the surgeon's skills. This problem has not been properly addressed in other studies. We analyze the case of a Spanish public hospital, in which continuous pressures and budgeting reductions entail the more efficient use of resources. Methods: To obtain an optimal solution for this problem, we developed a mixed-integer programming model and user-friendly interface that facilitate the scheduling of planned operations for the following surgical day. We also implemented a simulation model to assist the evaluation of different dispatching policies for surgeries and surgeons. The typical aspects we took into account were the type of surgeon, potential overtime, idling time of surgeons, and the use of operating rooms. Results: It is necessary to consider the expertise of a given surgeon when formulating a schedule: such skill can decrease the probability of delays that could affect subsequent surgeries or cause cancellation of the final surgery. We obtained optimal solutions for a set of given instances, which we obtained through surgical information related to acceptable times collected from a Spanish public hospital. Conclusions: We developed a computer-aided framework with a user-friendly interface for use by a surgical manager that presents a 3-D simulation of the problem. Additionally, we obtained an efficient formulation for this complex problem. However, the spread of this kind of operation research in Spanish public health hospitals will take a long time since there is a lack of knowledge of the beneficial techniques and possibilities that operational research can offer for the health-care system.

A mixed-integer quadratically-constrained programming model for the distribution system expansion planning

This paper presents a mixed-integer quadratically-constrained programming (MIQCP) model to solve the distribution system expansion planning (DSEP) problem. The DSEP model considers the construction/reinforcement of substations, the construction/reconductoring of circuits, the allocation of fixed capacitors banks and the radial topology modification. As the DSEP problem is a very complex mixed-integer non-linear programming problem, it is convenient to reformulate it like a MIQCP problem; it is demonstrated that the proposed formulation represents the steady-state operation of a radial distribution system. The proposed MIQCP model is a convex formulation, which allows to find the optimal solution using optimization solvers. Test systems of 23 and 54 nodes and one real distribution system of 136 nodes were used to show the efficiency of the proposed model in comparison with other DSEP models available in the specialized literature. (C) 2014 Elsevier Ltd. All rights reserved.

Convex model predictive control for vehicular systems

In this work, the author presents a method called Convex Model Predictive Control (CMPC) to control systems whose states are elements of the rotation matrices SO(n) for n = 2, 3. This is done without charts or any local linearization, and instead is performed by operating over the orbitope of rotation matrices. This results in a novel model predictive control (MPC) scheme without the drawbacks associated with conventional linearization techniques such as slow computation time and local minima. Of particular emphasis is the application to aeronautical and vehicular systems, wherein the method removes many of the trigonometric terms associated with these systems’ state space equations. Furthermore, the method is shown to be compatible with many existing variants of MPC, including obstacle avoidance via Mixed Integer Linear Programming (MILP).

Application-oriented Mixed Integer Non-Linear Programming

In the most recent years there is a renovate interest for Mixed Integer Non-Linear Programming (MINLP) problems. This can be explained for different reasons: (i) the performance of solvers handling non-linear constraints was largely improved; (ii) the awareness that most of the applications from the real-world can be modeled as an MINLP problem; (iii) the challenging nature of this very general class of problems. It is well-known that MINLP problems are NP-hard because they are the generalization of MILP problems, which are NP-hard themselves. However, MINLPs are, in general, also hard to solve in practice. We address to non-convex MINLPs, i.e. having non-convex continuous relaxations: the presence of non-convexities in the model makes these problems usually even harder to solve. The aim of this Ph.D. thesis is to give a flavor of different possible approaches that one can study to attack MINLP problems with non-convexities, with a special attention to real-world problems. In Part 1 of the thesis we introduce the problem and present three special cases of general MINLPs and the most common methods used to solve them. These techniques play a fundamental role in the resolution of general MINLP problems. Then we describe algorithms addressing general MINLPs. Parts 2 and 3 contain the main contributions of the Ph.D. thesis. In particular, in Part 2 four different methods aimed at solving different classes of MINLP problems are presented. Part 3 of the thesis is devoted to real-world applications: two different problems and approaches to MINLPs are presented, namely Scheduling and Unit Commitment for Hydro-Plants and Water Network Design problems. The results show that each of these different methods has advantages and disadvantages. Thus, typically the method to be adopted to solve a real-world problem should be tailored on the characteristics, structure and size of the problem. Part 4 of the thesis consists of a brief review on tools commonly used for general MINLP problems, constituted an integral part of the development of this Ph.D. thesis (especially the use and development of open-source software). We present the main characteristics of solvers for each special case of MINLP.

A Mixed Integer Quadratic Programming Model for the Low Autocorrelation Binary Sequence Problem

In this paper the low autocorrelation binary sequence problem (LABSP) is modeled as a mixed integer quadratic programming (MIQP) problem and proof of the model’s validity is given. Since the MIQP model is semidefinite, general optimization solvers can be used, and converge in a finite number of iterations. The experimental results show that IQP solvers, based on this MIQP formulation, are capable of optimally solving general/skew-symmetric LABSP instances of up to 30/51 elements in a moderate time. ACM Computing Classification System (1998): G.1.6, I.2.8.

Hydrocarbon field size distributions: a case study in mixed integer nonlinear programming

Of key importance to oil and gas companies is the size distribution of fields in the areas that they are drilling. Recent arguments suggest that there are many more fields yet to be discovered in mature provinces than had previously been thought because the underlying distribution is monotonic not peaked. According to this view the peaked nature of the distribution for discovered fields reflects not the underlying distribution but the effect of economic truncation. This paper contributes to the discussion by analysing up-to-date exploration and discovery data for two mature provinces using the discovery-process model, based on sampling without replacement and implicitly including economic truncation effects. The maximum likelihood estimation involved generates a high-dimensional mixed-integer nonlinear optimization problem. A highly efficient solution strategy is tested, exploiting the separable structure and handling the integer constraints by treating the problem as a masked allocation problem in dynamic programming.

Polyhedral study of mixed integer sets arising from inventory problems

“Branch-and-cut” algorithm is one of the most efficient exact approaches to solve mixed integer programs. This algorithm combines the advantages of a pure branch-and-bound approach and cutting planes scheme. Branch-and-cut algorithm computes the linear programming relaxation of the problem at each node of the search tree which is improved by the use of cuts, i.e. by the inclusion of valid inequalities. It should be taken into account that selection of strongest cuts is crucial for their effective use in branch-and-cut algorithm. In this thesis, we focus on the derivation and use of cutting planes to solve general mixed integer problems, and in particular inventory problems combined with other problems such as distribution, supplier selection, vehicle routing, etc. In order to achieve this goal, we first consider substructures (relaxations) of such problems which are obtained by the coherent loss of information. The polyhedral structure of those simpler mixed integer sets is studied to derive strong valid inequalities. Finally those strong inequalities are included in the cutting plane algorithms to solve the general mixed integer problems. We study three mixed integer sets in this dissertation. The first two mixed integer sets arise as a subproblem of the lot-sizing with supplier selection, the network design and the vendor-managed inventory routing problems. These sets are variants of the well-known single node fixed-charge network set where a binary or integer variable is associated with the node. The third set occurs as a subproblem of mixed integer sets where incompatibility between binary variables is considered. We generate families of valid inequalities for those sets, identify classes of facet-defining inequalities, and discuss the separation problems associated with the inequalities. Then cutting plane frameworks are implemented to solve some mixed integer programs. Preliminary computational experiments are presented in this direction.

Multi-choice mixed integer goal programming optimization for real problems in a sugar and ethanol milling company

Goal Programming (GP) is an important analytical approach devised to solve many realworld problems. The first GP model is known as Weighted Goal Programming (WGP). However, Multi-Choice Aspirations Level (MCAL) problems cannot be solved by current GP techniques. In this paper, we propose a Multi-Choice Mixed Integer Goal Programming model (MCMI-GP) for the aggregate production planning of a Brazilian sugar and ethanol milling company. The MC-MIGP model was based on traditional selection and process methods for the design of lots, representing the production system of sugar, alcohol, molasses and derivatives. The research covers decisions on the agricultural and cutting stages, sugarcane loading and transportation by suppliers and, especially, energy cogeneration decisions; that is, the choice of production process, including storage stages and distribution. The MCMIGP allows decision-makers to set multiple aspiration levels for their problems in which the more/higher, the better and the less/lower, the better in the aspiration levels are addressed. An application of the proposed model for real problems in a Brazilian sugar and ethanol mill was conducted; producing interesting results that are herein reported and commented upon. Also, it was made a comparison between MCMI GP and WGP models using these real cases. © 2013 Elsevier Inc.