Evaluation Of MixedInteger Nonlinear Programming

5m ago
37 Views
0 Downloads
631.91 KB
40 Pages
Transcription

Evaluation of Mixed IntegerNonlinear ProgrammingroutinesJ. De Wits436710DCT 2005.42Traineeship reportCoaches:ir. M.W.T. Kootdr. ir. A.G. de JagerSupervisor:prof. dr. ir. M. SteinbuchTechnische Universiteit EindhovenDepartment of Mechanical EngineeringDynamics and Control Technology GroupEindhoven, September, 2005

Abstra tIn future road vehicles an increase in electric power consumption will occur. To prevent an similar increase in fuel consumption, smart strategies for the generation, storage/retrieval, distribution and consumption of electric power are needed. This report considers a dual storage powernet, where a genarator is connected to a discrete switching device. This switch divides the electricpower to the battery or to a super capacitor. These two storage devices are connected through aDC/DC converter. The optimization problem, which finds the minimal fuel consumption andthe switch position for a given trajectory, result in a Mixed Integer NonLinear Programming problem (MINLP).Mixed Integer NonLinear Programming problems are difficult to solve for large numbers of variables, in particular for large numbers of discrete variables. This report deals with three MINLPtechniques, Branch and Bound (BNB), Outer Approximation (OA) and Generalized Benders Decomposition (GBD). These techniques are tested on a vehicle model, which uses a switch, a battery and a supercap to store electrical power.The BNB technique is able to solve the MINLP problem for a certain problem size, whereas theother techniques are not able to solve the problem within limited iteration and time. But even theBNB technique requires a lot of iterations and time to solve larger problems.Therefore other techniques, other implementations or solvers should be considered to solve largeMINLP problems.2

ContentsAbstract315Introduction2 The model2.1 The vehicle model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2 The optimization problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .638Mixed integer nonlinear programming routines3.1 MINLP . . . . . . . . . . . . . . . . . . .3.2 Branch and Bound . . . . . . . . . . . . .3.3 Outer Approximation . . . . . . . . . . .3.4 Generalized Benders Decomposition . . .3.5 Conclusion . . . . . . . . . . . . . . . . .4 Comparison of the optimization routines4.1 The drive cycle and loads . . . . . . . . . . .4.2 Implementation of the routines . . . . . . . .4.2.1 Branch and Bound . . . . . . . . . . .4.2.2 Outer Approximation . . . . . . . . .4.2.3 Generalized Benders Decomposition .4.3 Results of the routines . . . . . . . . . . . . .4.3.1 Branch and Bound . . . . . . . . . . .4.3.2 Outer Approximation . . . . . . . . .4.3.3 Generalized Benders Decomposition .4.3.4 Conclusion . . . . . . . . . . . . . . .4.4 Different models . . . . . . . . . . . . . . . .4.4.1 Model with a continuous switch . . .4.4.2 Model without the supercap . . . . . .4.4.3 Conclusion . . . . . . . . . . . . . . .4.5 Other Solvers . . . . . . . . . . . . . . . . . .4.5.1 TOMLAB . . . . . . . . . . . . . . . .4.5.2 LINDO API . . . . . . . . . . . . . .4.5.3 AMPL . . . . . . . . . . . . . . . . . .5Conclusions and 7171818181919203

Bibliography21A MINLP model of the dual storage power netA.1 Components . . . . . . . . . . . . . .A.2 Power flow . . . . . . . . . . . . . . .A.3 Cost function . . . . . . . . . . . . . .A.4 Constraints . . . . . . . . . . . . . . .22B FiguresB.1 Loads . . . . . . . . . . . . . . . . .B.2 Outer Approximation . . . . . . . .B.3 Generalized Benders DecompositionB.4 The variables . . . . . . . . . . . . .B.4.1 Power stored in the battery .B.4.2 Power stored in the supercapB.4.3 The position of the switch . .2324252526.427293235353739

Chapter 1Introdu tionPresent day consumers demand more performance, comfort and safety from a road vehicle. Tosatisfy the consumers, future vehicles will be increasingly equipped with electronic devices. Suchdevices are air conditioning or climate control, electronic windows, sound systems, electronicsteering, drive by wire, cruise control, driving assistance, stability programs et cetera. These electronics consume electric power. Over the past twenty years the electric power consumption instandard road vehicles has increased approximately four percent every year. In the near futureeven higher power demands are expected [1], [2].To keep up with future power demands, the automobile industry has suggested new 42 V powernet topologies, which should replace the traditional 14 V, which are used currently [1], [2]. Thesepower nets will be able to meet the future demands, but this will coincide with an increase infuel consumption. Future vehicles have to meet strict requirements about exhaust emissions.With the rising prices of fuel, costumers will demand fuel economic vehicles. Therefore smartstrategies for the generation, storage/retrieval, distribution and consumption of electric powerare needed. But the driver should not experience different vehicle behavior as a result of suchstrategy. This implies that the available torque and power should be present when the driverwants it.In this report a vehicle power net is considered, where a generator is connected to a switchingdevice that divides the electric power between a super capacitor (supercap) and a battery. Thisswitch is discrete. The battery and the supercap are connected to a DC/DC converter.When the speed trajectory of the car is known, the minimal fuel consumption can be calculatedusing optimization. To solve this problem, a mixed integer nonlinear optimization routine isneeded.The aim of this internship is to find available techniques and select the most suitable for the givenproblem. This is done by implementation and testing these techniques in a Matlab environment.Literature will provide existing techniques, these techniques will be adapted to be able to solvethe problem.The remainder of this report is build up as follows: Chapter 2 describes the model of the vehicle and the loads a vehicle is subjected to. Chapter 3 gives an overview of the mixed integernonlinear programming techniques. In Chapter 4 these techniques will be implemented andcompared. Chapter 5 will summarize the results of this research.5

Chapter 2The modelThe strategy, discussed in this report, is focussed on the generation, storage/retrieval and distribution of the electronic power. It considers an advanced dual storage net. In the next section thevehicle model and the advanced dual storage net will be described.2.1 The vehi le modelThe advanced dual storage net consists of a generator, a battery, a supercap, a DC/DC converterand an internal combustion engine (ICE). The power flow starts with the combustion of fuel.The mechanical power is split in two directions: one part goes to the drive train (DT) and theother part is used by a generator (GEN), which generates electrical power. The electrical poweris connected to a discrete switch (S). The power can be sent to the supercap (C) or to the battery(B). The load (Load), the electric power that is needed, is connected to the battery. The supercapand the battery are connected to a DC/DC converter (DC). A schematic drawing can be seen inFigure 2.1.PpfuelICEPcDTs·PePmPgGENPeS(1-s)·P eCEcsPdcDCPdbPbBPlLoadFigure 2.1: Power ow in a dual storage power net6PcsPbsEbs

A supercap can be considered as a very large capacitor. A battery can operate between 20%and 100% SOC ( State Of Charge, the relative energy level), while maintaining an acceptableboard net voltage, whereas a supercap can only be operated between 80% and 100% SOC. Theopen cell voltage is linear with the energy level for the supercap. The open cell voltage of the battery is assumed to be linear between 20% and 100% SOC. The battery has a much bigger storagecapacity, but the losses of the supercap are much smaller, than the losses of the battery. Theselosses will be assumed to be quadratic with the power. Therefore the losses will be less, when lowpower is delivered for a long period of time, then a high power for a shorter period.When the generator delivers high powers (mainly during deceleration phases), the energy will bestored in the supercap. From there the energy will be transferred at a lower power through theDC/DC converter to the battery or the load. With this strategy the energy losses will be reduced.The model structure and the component models can be found in [4]. The report describes themathematical formulation of the model and its constraints. This report is summarized in Appendix A.2.2 The optimization problemThe mechanical power needed for the drive train and the electric load will be prescribed. Therefore the model can structured such that there will be three design variables: Pcs , the power storedin the supercap, Pbs , the power stored in the battery and s, the position of the switch.These three variables will be the input of the cost function. The output of the cost function willreflect the fuel consumption, which has to be minimized.The cost function becomes a high order polynomial. This polynomial is a smooth, nonlinearfunction, which is most likely to be nonconvex. Because the cost function contains both continuous and discrete variables, the optimization problem becomes a NonLinear Mixed IntegerProgramming problem:min f (Pbs , Pcs , s)x,y(2.1)s.t. Ax 6 bAeq x beq(Pbs , Pcs ) ǫ ℜ2n , s ǫ {0, 1}n7

Chapter 3Mixed integer nonlinear programmingroutinesThis chapter describes three mixed integer nonlinear programming (MINLP) techniques: Branchand Bound (BNB), Outer Approximation (OA) and Generalized Benders Decomposition (GBD).The overview is restricted to solvers for convex MINLP. These techniques are used to solve thenonlinear discrete optimization problem described in the previous Chapter. A unified overviewand derivation of the MINLP techniques can be found in [3], [6] and [7].3.1 MINLPThe basic mathematical description of a MINLP problem is as follows:min f (x, y)x,y(3.1)s.t. gj (x, y) 6 0, j ǫ Jnmxǫℜ , yǫZwhere f (·), g(·) are convex, differentiable functions, J is the index set of inequalities and x andy are the continuous and discrete variables, respectively.3.2 Bran h and BoundThis method first solves the continuous nonlinear programming (NLP) relaxation, the discretevariables are considered continuous (the NLP subproblem). After this the program generatedsubproblems, where the domain of the variable (still continuous) is being restricted. This iscalled branching. Then it solves these subproblems. This process continues until the variable isfixed to a (integer) value.The advantage of this approach (when compared with explicit enumeration) lies in the fact thatnot all subproblems have to be solved.The BNB method is generally only attractive, if the NLP subproblems are relative inexpensiveto solve or when only a few of them need to be solved. This could be either because of the lowdimensionality of the discrete variables or because the integrality gap of the continuous NLPrelaxation of the NLP subproblem is small. If possible it is recommended to approximate the8

nonlinear cost function by a quadratic cost function, this will reduce the calculation effort offinding the local minimum [6] [8].3.3 Outer ApproximationThe OA method solves in a cycle of iterations a mixed integer linear programming (MILP) problem and a relaxed NLP, with fixed integer variables. The local minimum of the NLP gives asolution (xk ,yk ) for the continuous variables. The corresponding cost function and the nonlinearconstraints are then linearized around this solution. α Is the value of the linearized cost function.This will result in a linear inequality constraint for the MILP.min αx,y x xks.t. α k· y yk x xgj (xk , y k ) gj (xk , y k )T 0, j ǫ Jy ykf (xk , y k ) f (xk , y k )T·xk ǫ ℜn , y k ǫ Zm k 1, 2, . . .(3.2) Rearranging this constraint, results in an linear inequality constraint, that can be used to solvethe MILP subproblem:· k · xkkkkT· x f (x , y ) f (x , y ) f (xk , y k )T 1 yk ·y (3.3) gj (xk , y k )T0xkkkTkkα gj (x , y ) gj (x , y )ykThis can be written as:(3.4)Ax bAn updated version of this constraint is added at every cycle to the MILP subproblem. Thereforeat every cycle one linear constraint from the linearized cost function and j linearized nonlinearconstraints are addded. The cost function and the nonlinear constraints, used in the MILP subproblem, are linearized functions in the minimum of the NLP subproblem [6].The cycle of iterations will start with the MILP subproblem. The cost function is linearizedaround the initial conditions. The output of this optimization is the intersection between thelinear bounds and the linearized function. After the MILP subproblem the relaxed NLP subproblem is solved. At this subproblem feasible solutions are found, whereas the MILP subproblemonly results in feasible solutions with regard to the discrete variables. The resulting variables areused as the starting points for the next iteration.The OA method should reduce the number of NLP problems, that have to be solved.3.4 Generalized Benders De ompositionThe GBD method is similar to the OA met