Exponential distribution-based genetic algorithm for solving mixed-integer bilevel programming problems

Two classes of mixed-integer nonlinear bilevel programming problems are discussed. One is that the follower＇s functions are separable with respect to the follower＇s variables, and the other is that the follower＇s functions are convex if the follower＇s variables are not restricted to integers. A genetic algorithm based on an exponential distribution is proposed for the aforementioned problems. First, for each fixed leader＇s variable x, it is proved that the optimal solution y of the follower＇s mixed-integer programming can be obtained by solving associated relaxed problems, and according to the convexity of the functions involved, a simplified branch and bound approach is given to solve the follower＇s programming for the second class of problems. Furthermore, based on an exponential distribution with a parameter λ, a new crossover operator is designed in which the best individuals are used to generate better offspring of crossover. The simulation results illustrate that the proposed algorithm is efficient and robust.

Computation of an Emptiable Minimal Siphon in a Subclass of Petri Nets Using Mixed-Integer Programming

Deadlock resolution strategies based on siphon control are widely investigated.Their computational efficiency largely depends on siphon computation.Mixed-integer programming(MIP)can be utilized for the computation of an emptiable siphon in a Petri net(PN).Based on it,deadlock resolution strategies can be designed without requiring complete siphon enumeration that has exponential complexity.Due to this reason,various MIP methods are proposed for various subclasses of PNs.This work proposes an innovative MIP method to compute an emptiable minimal siphon(EMS)for a subclass of PNs named S^(4)PR.In particular,many particular structural characteristics of EMS in S4 PR are formalized as constraints,which greatly reduces the solution space.Experimental results show that the proposed MIP method has higher computational efficiency.Furthermore,the proposed method allows one to determine the liveness of an ordinary S^(4)PR.

Continuity of the optimal value function and optimal solutions of parametric mixed-integer quadratic programs

To properly describe and solve complex decision problems, research on theoretical properties and solution of mixed-integer quadratic programs is becoming very important. We establish in this paper different Lipschitz-type continuity results about the optimal value function and optimal solutions of mixed-integer parametric quadratic programs with parameters in the linear part of the objective function and in the right-hand sides of the linear constraints. The obtained results extend some existing results for continuous quadratic programs, and, more importantly, lay the foundation for further theoretical study and corresponding algorithm analysis on mixed-integer quadratic programs.

Optimal Micro-PMU Placement for Improving State Estimation Accuracy via Mixed-integer Semidefinite Programming

Micro-phasor measurement units(μPMUs)with a micro-second resolution and milli-degree accuracy capability are expected to play an important role in improving the state estimation accuracy in the distribution network with increasing penetration of distributed generations.Therefore,this paper investigates the problem of how to place a limited number ofμPMUs to improve the state estimation accuracy.Combined with pseudo-measurements and supervisory control and data acquisition(SCADA)measurements,an optimalμPMU placement model is proposed based on a two-step state estimation method.The E-optimal experimental criterion is utilized to measure the state estimation accuracy.The nonlinear optimization problem is transformed into a mixed-integer semidefinite programming(MISDP)problem,whose optimal solution can be obtained by using the improved Benders decomposition method.Simulations on several systems are carried out to evaluate the effective performance of the proposed model.

TACKLING INDUSTRIAL-SCALE SUPPLY CHAIN PROBLEMS BY MIXED-INTEGER PROGRAMMING

The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems.The complexity of industrial-scale supply chain optimization,however,often poses limits to the application of general mixed-integer programming solvers.In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice.Our computational evaluation is based on a diverse set,modeling real-world scenarios supplied by our industry partner SAP.

An efficient approach for solving mixed-integer programming problems under the monotonic condition

Many important integer and mixed-integer programming problems are difficult to solve.A representative example is unit commitment with combined cycle units and transmission capacity constraints.Complicated transitions within combined cycle units are difficult to follow,and system-wide coupling transmission capacity constraints are difficult to handle.Another example is the quadratic assignment problem.The presence of cross-products in the objective function leads to nonlinearity.In this study,building upon the novel integration of surrogate Lagrangian relaxation and branch-and-cut,such problems will be solved by relaxing selected coupling constraints.Monotonicity of the relaxed problem will be assumed and exploited and nonlinear terms will be dynamically linearised.The linearity of the resulting problem will be exploited using branch-and-cut.To achieve fast convergence,guidelines for selecting stepsizing parameters will be developed.The method opens up directions for solving nonlinear mixed-integer problems,and numerical results indicate that the new method is efficient.

A Quantum Computing Based Numerical Method for Solving Mixed-Integer Optimal Control Problems

Mixed-integer optimal control problems(MIOCPs) usually play important roles in many real-world engineering applications. However, the MIOCP is a typical NP-hard problem with considerable computational complexity, resulting in slow convergence or premature convergence by most current heuristic optimization algorithms. Accordingly, this study proposes a new and effective hybrid algorithm based on quantum computing theory to solve the MIOCP. The algorithm consists of two parts:(i) Quantum Annealing(QA) specializes in solving integer optimization with high efficiency owing to the unique annealing process based on quantum tunneling, and(ii) Double-Elite Quantum Ant Colony Algorithm(DEQACA) which adopts double-elite coevolutionary mechanism to enhance global searching is developed for the optimization of continuous decisions. The hybrid QA/DEQACA algorithm integrates the strengths of such algorithms to better balance the exploration and exploitation abilities. The overall evolution performs to seek out the optimal mixed-integer decisions by interactive parallel computing of the QA and the DEQACA. Simulation results on benchmark functions and practical engineering optimization problems verify that the proposed numerical method is more excel at achieving promising results than other two state-of-the-art heuristics.

Numerical Computation of a Mixed-Integer Optimal Control Problem Based on Quantum Annealing

It is extremely challenging to solve the mixed-integer optimal control problems(MIOCPs)due to the complex computation in solving the integer decision variables.This paper presents a new method based on quantum annealing(QA)to solve MIOCP.The QA is a metaheuristic which applies quantum tunneling in the annealing process.It has a faster convergence speed in optimal-searching and is less likely to run into local minima.Hence,QA is applied to deal with this kind of optimization problems.First,MIOCP is transformed into a mixed-integer nonlinear programming(MINLP).Then,a method based on QA is adopted to solve the MINLP and acquire the optimal solution.At last,two benchmark examples including Lotka-Volterra type fishing problem and distillation column are presented and solved.The effectiveness of the metliodology is verified by the acquired optimal schemes.

Unmanned Aerial Vehicle Inspection Routing and Scheduling for Engineering Management

Technological advancements in unmanned aerial vehicles(UAVs)have revolutionized various industries,enabling the widespread adoption of UAV-based solutions.In engineering management,UAV-based inspection has emerged as a highly efficient method for identifying hidden risks in high-risk construction environments,surpassing traditional inspection techniques.Building on this foundation,this paper delves into the optimization of UAV inspection routing and scheduling,addressing the complexity introduced by factors such as no-fly zones,monitoring-interval time windows,and multiple monitoring rounds.To tackle this challenging problem,we propose a mixed-integer linear programming(MILP)model that optimizes inspection task assignments,monitoring sequence schedules,and charging decisions.The comprehensive consideration of these factors differentiates our problem from conventional vehicle routing problem(VRP),leading to a mathematically intractable model for commercial solvers in the case of large-scale instances.To overcome this limitation,we design a tailored variable neighborhood search(VNS)metaheuristic,customizing the algorithm to efficiently solve our model.Extensive numerical experiments are conducted to validate the efficacy of our proposed algorithm,demonstrating its scalability for both large-scale and real-scale instances.Sensitivity experiments and a case study based on an actual engineering project are also conducted,providing valuable insights for engineering managers to enhance inspection work efficiency.

Green resource allocation for mobile edge computing

We investigate the green resource allocation to minimize the energy consumption of the users in mobile edge computing systems,where task offloading decisions,transmit power,and computation resource allocation are jointly optimized.The considered energy consumption minimization problem is a non-convex mixed-integer nonlinear programming problem,which is challenging to solve.Therefore,we develop a joint search and Successive Convex Approximation(SCA)scheme to optimize the non-integer variables and integer variables in the inner loop and outer loop,respectively.Specifically,in the inner loop,we solve the optimization problem with fixed task offloading decisions.Due to the non-convex objective function and constraints,this optimization problem is still non-convex,and thus we employ the SCA method to obtain a solution satisfying the Karush-Kuhn-Tucker conditions.In the outer loop,we optimize the offloading decisions through exhaustive search.However,the computational complexity of the exhaustive search method is greatly high.To reduce the complexity,a heuristic scheme is proposed to obtain a sub-optimal solution.Simulation results demonstrate the effectiveness of the developed schemes.

Energy Management of Networked Smart Railway Stations Considering Regenerative Braking, Energy Storage System, and Photovoltaic Units

The networking of microgrids has received significant attention in the form of a smart grid.In this paper,a set of smart railway stations,which is assumed as microgrids,is connected together.It has been tried to manage the energy exchanged between the networked microgrids to reduce received energy from the utility grid.Also,the operational costs of stations under various conditions decrease by applying the proposed method.The smart railway stations are studied in the presence of photovoltaic(PV)units,energy storage systems(ESSs),and regenerative braking strategies.Studying regenerative braking is one of the essential contributions.Moreover,the stochastic behaviors of the ESS’s initial state of energy and the uncertainty of PV power generation are taken into account through a scenario-based method.The networked microgrid scheme of railway stations(based on coordinated operation and scheduling)and independent operation of railway stations are studied.The proposed method is applied to realistic case studies,including three stations of Line 3 of Tehran Urban and Suburban Railway Operation Company(TUSROC).The rolling stock is simulated in the MATLAB environment.Thus,the coordinated operation of networked microgrids and independent operation of railway stations are optimized in the GAMS environment utilizing mixed-integer linear programming(MILP).

A Method for Crude Oil Selection and Blending Optimization Based on Improved Cuckoo Search Algorithm

Refineries often need to find similar crude oil to replace the scarce crude oil for stabilizing the feedstock property. We introduced the method for calculation of crude blended properties firstly, and then created a crude oil selection and blending optimization model based on the data of crude oil property. The model is a mixed-integer nonlinear programming(MINLP) with constraints, and the target is to maximize the similarity between the blended crude oil and the objective crude oil. Furthermore, the model takes into account the selection of crude oils and their blending ratios simultaneously, and transforms the problem of looking for similar crude oil into the crude oil selection and blending optimization problem. We applied the Improved Cuckoo Search(ICS) algorithm to solving the model. Through the simulations, ICS was compared with the genetic algorithm, the particle swarm optimization algorithm and the CPLEX solver. The results show that ICS has very good optimization efficiency. The blending solution can provide a reference for refineries to find the similar crude oil. And the method proposed can also give some references to selection and blending optimization of other materials.

A two-stage optimization method for unmanned aerial vehicle inspection of an oil and gas pipeline network

Oil and gas pipeline networks are a key link in the coordinated development of oil and gas both upstream and downstream.To improve the reliability and safety of the oil and gas pipeline network, inspections are implemented to minimize the risk of leakage, spill and theft, as well as documenting actual incidents. In recent years, unmanned aerial vehicles have been recognized as a promising option for inspection due to their high efficiency. However, the integrated optimization of unmanned aerial vehicle inspection for oil and gas pipeline networks, including physical feasibility, the performance of mission, cooperation, real-time implementation and three-dimensional(3-D) space, is a strategic problem due to its large-scale,complexity as well as the need for efficiency. In this work, a novel mixed-integer nonlinear programming model is proposed that takes into account the constraints of the mission scenario and the safety performance of unmanned aerial vehicles. To minimize the total length of the inspection path, the model is solved by a two-stage solution method. Finally, a virtual pipeline network and a practical pipeline network are set as two examples to demonstrate the performance of the optimization schemes. Moreover, compared with the traditional genetic algorithm and simulated annealing algorithm, the self-adaptive genetic simulated annealing algorithm proposed in this paper provides strong stability.

Optimization operation model of electricity market considering renewable energy accommodation and flexibility requirement

The renewable portfolio standard has been promoted in parallel with the reform of the electricity market,and the flexibility requirement of the power system has rapidly increased.To promote renewable energy consumption and improve power system flexibility,a bi-level optimal operation model of the electricity market is proposed.A probabilistic model of the flexibility requirement is established,considering the correlation between wind power,photovoltaic power,and load.A bi-level optimization model is established for the multi-markets;the upper and lower models represent the intra-provincial market and inter-provincial market models,respectively.To efficiently solve the model,it is transformed into a mixed-integer linear programming model using the Karush–Kuhn–Tucker condition and Lagrangian duality theory.The economy and flexibility of the model are verified using a provincial power grid as an example.

An MILP approach for detailed scheduling of oil depots along a multi-product pipeline

Oil depots along products pipelines are important components of the pipeline transportation system and down-stream markets.The operating costs of oil depots account for a large proportion of the total system’s operating costs.Meanwhile,oil depots and pipelines form an entire system,and each operation in a single oil depot may have influence on others.It is a tough job to make a scheduling plan when considering the factors of delivering contaminated oil and batches migration.So far,studies simultaneously considering operating constraints and contaminated oil issues are rare.Aiming at making a scheduling plan with the lowest operating costs,the paper establishes a mixed-integer linear programming model,considering a sequence of operations,such as delivery, export, blending,fractionating and exchanging operations,and batch property differences of the same oil as well as influence of batch migration on contaminated volume.Moreover,the paper verifies the linear relationship between oil concentration and blending capability by mathematical deduction.Finally,the model is successfully applied to one of the product pipelines in China and proved to be practical.

Connected Vehicle-Based Traffic Signal Coordination

This study presents a connected vehicles(CVs)-based traffic signal optimization framework for a coordinated arterial corridor.The signal optimization and coordination problem are first formulated in a centralized scheme as a mixed-integer nonlinear program(MINLP).The optimal phase durations and offsets are solved together by minimizing fuel consumption and travel time considering an individual vehicle’s trajectories.Due to the complexity of the model,we decompose the problem into two levels:an intersection level to optimize phase durations using dynamic programming(DP),and a corridor level to optimize the offsets of all intersections.In order to solve the two-level model,a prediction-based solution technique is developed.The proposed models are tested using traffic simulation under various scenarios.Compared with the traditional actuated signal timing and coordination plan,the signal timing plans generated by solving the MINLP and the two-level model can reasonably improve the signal control performance.When considering varies vehicle types under high demand levels,the proposed two-level model reduced the total system cost by 3.8%comparing to baseline actuated plan.MINLP reduced the system cost by 5.9%.It also suggested that coordination scheme was beneficial to corridors with relatively high demand levels.For intersections with major and minor street,coordination conducted for major street had little impacts on the vehicles at the minor street.

A Novel MILP Model Based on the Topology of a Network Graph for Process Planning in an Intelligent Manufacturing System

Intelligent process planning(PP)is one of the most important components in an intelligent manufacturing system and acts as a bridge between product designing and practical manufacturing.PP is a nondeterministic polynomial-time(NP)-hard problem and,as existing mathematical models are not formulated in linear forms,they cannot be solved well to achieve exact solutions for PP problems.This paper proposes a novel mixed-integer linear programming(MILP)mathematical model by considering the network topology structure and the OR nodes that represent a type of OR logic inside the network.Precedence relationships between operations are discussed by raising three types of precedence relationship matrices.Furthermore,the proposed model can be programmed in commonly-used mathematical programming solvers,such as CPLEX,Gurobi,and so forth,to search for optimal solutions for most open problems.To verify the effectiveness and generality of the proposed model,five groups of numerical experiments are conducted on well-known benchmarks.The results show that the proposed model can solve PP problems effectively and can obtain better solutions than those obtained by the state-ofthe-art algorithms.

Nonlinear Model-Based Process Operation under UncertaintyUsing Exact Parametric Programming

In the present work, two new, （multi-）parametric programming （mp-P）-inspired algorithms for the solutionof mixed-integer nonlinear programming （MINLP） problems are developed, with their main focus being onprocess synthesis problems. The algorithms are developed for the special case in which the nonlinearitiesarise because of logarithmic terms, with the first one being developed for the deterministic case, and thesecond for the parametric case （p-MINLP）. The key idea is to formulate and solve the square system of thefirst-order Karush-Kuhn-Tucker （KKT） conditions in an analytical way, by treating the binary variables and/or uncertain parameters as symbolic parameters. To this effect, symbolic manipulation and solution tech-niques are employed. In order to demonstrate the applicability and validity of the proposed algorithms, twoprocess synthesis case studies are examined. The corresponding solutions are then validated using state-of-the-art numerical MINLP solvers. For p-MINLP, the solution is given by an optimal solution as an explicitfunction of the uncertain parameters.

Resource-constrained maximum network throughput on space networks

This paper investigates the maximum network through- put for resource-constrained space networks based on the delay and disruption-tolerant networking （DTN） architecture. Specifically, this paper proposes a methodology for calculating the maximum network throughput of multiple transmission tasks under storage and delay constraints over a space network. A mixed-integer linear programming （MILP） is formulated to solve this problem. Simula- tions results show that the proposed methodology can successfully calculate the optimal throughput of a space network under storage and delay constraints, as well as a clear, monotonic relationship between end-to-end delay and the maximum network throughput under storage constraints. At the same time, the optimization re- sults shine light on the routing and transport protocol design in space communication, which can be used to obtain the optimal network throughput.

Big-M based MILP method for SCUC considering allowable wind power output interval and its adjustable conservativeness

In contrast to most existing works on robust unit commitment(UC),this study proposes a novel big-M-based mixed-integer linear programming(MILP)method to solve security-constrained UC problems considering the allowable wind power output interval and its adjustable conservativeness.The wind power accommodation capability is usually limited by spinning reserve requirements and transmission line capacity in power systems with large-scale wind power integration.Therefore,by employing the big-M method and adding auxiliary 0-1 binary variables to describe the allowable wind power output interval,a bilinear programming problem meeting the security constraints of system operation is presented.Furthermore,an adjustable confidence level was introduced into the proposed robust optimization model to decrease the level of conservatism of the robust solutions.This can establish a trade-off between economy and security.To develop an MILP problem that can be solved by commercial solvers such as CPLEX,the big-M method is utilized again to represent the bilinear formulation as a series of linear inequality constraints and approximately address the nonlinear formulation caused by the adjustable conservativeness.Simulation studies on a modified IEEE 26-generator reliability test system connected to wind farms were performed to confirm the effectiveness and advantages of the proposed method.