Search

Many operation optimization problems such as scheduling and assignment of interest to the automation community are mixed-integer linear programming (MILP) problems. Because of their combinatorial nature, the effort required to obtain optimal solutions increases drastically as the problem size increases. Such operation optimization problems typically need to be solved several times a day and require short solving times (e.g., 5, 10, or 20 min). The goal is, therefore, to obtain near-optimal solutions with quantifiable quality in a computationally efficient manner. Existing MILP methods, however, suffer from slow convergence and may not efficiently achieve this goal. In this paper, motivated by fast convergence of augmented Lagrangian relaxation (LR), a novel advanced price-based decomposition and coordination “surrogate absolute-value LR” (SAVLR) approach is developed. Within the method, convergence of our recent surrogate LR (SLR), which has overcome all major difficulties of traditional LR, is significantly improved by penalizing constraint violations by adding “absolute-value” penalties. Moreover, such penalties are efficiently linearized in a standard way, thereby enabling the use of MILP solvers. By exploiting the beautiful property of exponential reduction of complexity of subproblems upon decomposition, subproblems are efficiently solved and their solutions are efficiently coordinated by updating Lagrangian multipliers. Convergence is then proved under novel adjustment of penalty coefficients. A series of generalized assignment problems is considered, and for these problems, superior performance of SAVLR over other state-of-the-art and state-of-the-practice methods is demonstrated. Accompanying CPLEX codes, whereby SAVLR is implemented, are also included. Note to Practitioners —Examples of important problems that arise in automation community include scheduling and assignment problems. Because of their combinatorial nature, the effort required to obtain optimal solutions increases drastically as the problem size increases. Existing mixed-integer linear programming (MILP) methods, however, may suffer from slow convergence and may not efficiently achieve this goal. The new method revolutionizes the way such problems can be solved with major improvements on the overall performance. It is based on our recent breakthrough “surrogate Lagrangian relaxation” (LR), which has overcome all major difficulties of traditional LR while exploiting the beautiful property of exponential reduction of complexity upon decomposition. To significantly improve convergence while maintaining linearity so as to use MILP solvers, our idea is to penalize violations of relaxed constraints by the infrequently used “absolute-value” penalty functions. Although not differentiable, absolute-value penalties have the advantage of being exactly linearizable through extra variables and constraints. The difficulties caused by those extra constraints, which couple subproblems, are resolved by adaptive adjustment of penalty coefficients. A series of generalized assignment problems is considered and superior performance of the new method against state-of-the-art and state-of-the-practice methods is demonstrated. Accompanying CPLEX codes whereby the new method is implemented are also included.

Day-Ahead Unit Commitment (UC) is an important problem faced by Independent System Operators (ISOs). Midcontinent ISO as the largest ISO in US, solves a complicated UC problem involving over 45,000 buses and 1,400 generation resources. With the increasing number of combined cycle units (CCs) represented by configuration-based modeling, solving the problem becomes more challenging. The state-of-the-practice branch-and-cut method suffers from poor performance when there are a large number of CCs. The goal of this paper is to solve such large UC problems with near-optimal solutions within time limits. In this paper, our recently developed Surrogate Lagrangian Relaxation, which overcomes major difficulties of Lagrangian Relaxation by not requiring dual optimal costs, is significantly enhanced through adding quadratic penalties on constraint violations to accelerate convergence. Quadratic penalty terms are linearized through a novel use of absolute value functions. Therefore, resource-level subproblems can be formulated and solved by branch-and-cut. Complicated constraints within a CC unit are thus handled within a subproblem. Subproblem solutions are then effectively coordinated. Computational improvements on key aspects are also incorporated to fine tune the algorithm. As demonstrated by MISO cases, the method provides near-optimal solutions within a time limit, and significantly outperforms branch-and-cut.

Short-term load forecasting at the distribution level predicts the load of substations, feeders, transformers, and possibly customers from half an hour to one week ahead. Effective forecasting is important for the planning and operation of distribution systems. The problem, however, is difficult in view of complicated load features, the large number of distribution-level nodes, and possible switching operations. In this paper, a new forecasting approach within the hierarchical structure is presented to solve these difficulties. Load of the root node at any user-defined subtree is first forecast by a wavelet neural network with appropriate inputs. Child nodes categorized as “regular” and “irregular” based on load pattern similarities are then forecast separately. Load of a regular child node is simply forecast as the proportion from the parent node load forecast while the load of an irregular child node is forecast by an individual neural network model. Switching operation detection and follow-up adjustments are also performed to capture abnormal changes and improve the forecasting accuracy. This new approach captures load characteristics of nodes at different levels, takes advantage of pattern similarities between a parent node and its child nodes, detects abnormalities, and provides high quality forecasts as demonstrated by two practical datasets.

In this paper, flight-path deviation in the navigation of unmanned space vehicles by global positioning system (GPS) is analyzed. A new method to calculate flight-path deviation by means of coordinate transforming is presented and the software of navigation and control is designed. This software is practical and effective for navigation by GPS with some characteristics including high-speed, high accuracy, real-time positioning and the use of digital mapping technique.