An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem

The well-known Shortest Path problem (SP) consists in finding a shortest path from a source to a destination such that the total cost is minimized. The SP models practical and theoretical problems. However, several shortest path applications rely on uncertain data. The Robust Shortest Path problem (RSP) is a generalization of SP. In the former, the cost of each arc is defined by an interval of possible values for the arc cost. The objective is to minimize the maximum relative regret of the path from the source to the destination. This problem is known as the minmax relative regret RSP and it is NP-Hard. We propose a mixed integer linear programming formulation for this problem. The CPLEX branch-and-bound algorithm based on this formulation is able to find optimal solutions for all instances with 100 nodes, and has an average gap of 17 % on the instances with up to 1,500 nodes. We also develop heuristics with emphasis on providing efficient and scalable methods for solving large instances for the minmax relative regret RSP, based on Pilot method and random-key genetic algorithms. To the best of our knowledge, this is the first work to propose a linear formulation, an exact algorithm and metaheuristics for the minmax relative regret RSP.     

Formulation and a two-phase matheuristic for the roaming salesman problem: Application to election logistics

In this paper we investigate a novel logistical problem. The goal is to determine daily tours for a traveling salesperson who collects rewards from activities in cities during a fixed campaign period. We refer to this problem as the Roaming Salesman Problem (RSP) motivated by real-world applications including election logistics, touristic trip planning and marketing campaigns. RSP can be characterized as a combination of the traditional Periodic TSP and the Prize-Collecting TSP with static arc costs and time-dependent node rewards. Commercial solvers are capable of solving small-size instances of the RSP to near optimality in a reasonable time. To tackle large-size instances we propose a two-phase matheuristic where the first phase deals with city selection while the second phase focuses on route generation. The latter capitalizes on an integer program to construct an optimal route among selected cities on a given day. The proposed matheuristic decomposes the RSP into as many subproblems as the number of campaign days. Computational results show that our approach provides near-optimal solutions in significantly shorter times compared to commercial solvers.     

Design and optimal tuning of nonlinear PI compensators

In this paper, linear time-invariant single-input single-output (SISO) systems that are stabilizable by linear proportional and integral (PI) compensators are considered. For such systems, a five-parameter nonlinear PI compensator is proposed. The parameters of the proposed compensator are tuned by solving an optimization problem. The optimization problem always has a solution.Additionally, a general nonlinear PI compensator is proposed and is approximated by easy-to-compute compensators, for instance, a six-parameter nonlinear PI compensator. The parameters of the approximate compensators are tuned to satisfy an optimality condition. The superiority of the proposed nonlinear PI compensators over linear PI compensators is discussed and is demonstrated for two feedback systems.     

Lead with closed-loop system compensation of a radically rotating elastic rod attached to a rigid body part I: A unified approach to the design of Llnear control system

Due to difficulties in modeling and poor knowledge of parameters, the behavior of flexible structures is subject to significant uncertainty. Hence it is essential that the control system provide an absolutely stable property in the presence of large variations. Over the years, many control laws—proportion and derivative (PD) control, nonlinear, linear-quadratic, adaptive, and linear quadratic Gaussian (LQG)—have been synthesized for flexible structures. The most commonly applied are the LQG controllers. In spite of its attractive qualities, the LQG controller is sensitive to parameter variations, and therefore its performance will deteriorate when the payload or typical parameters of the system vary with time. At the same time, the LQG controller does not guarantee general stability margins, and this is, perhaps, its main drawback. On the other hand, the PD is one kind of controller that ensures system stability to parameter variations within a certain bound. But a problem with the PD controller is evident; when high-frequency noise is present in the system, this noise will be amplified by the PD controller, which is generally unacceptable. In this paper, instead of using a PD controller, a passive lead compensator is employed, so that

• 1.(1) no additional power supplies are required and
• 2.(2) noise due to differentiation is reduced.

This lead compensator, together with a composite control strategy designed by the most popularly used sensors, potentiometer and tachometer, for the corresponding closed-loop system, has been shown with very good agreement in terms of system performance requirement. For the design of control system, it is practical to first design the controller based on the linear system model by neglecting the nonlinearities of the system. In Part I, the lead compensator, together with complementary control strategy and computer simulation modeling for a rotating flexible structure, with particular application to elastic rod system, is presented for the linear control system. Then the designed controller is applied to the nonlinear system model for evaluation and redesigned by computer simulation. This will be presented in Part II.     

Indefinite stochastic linear-quadratic optimal control problems with random jumps and related stochastic Riccati equations

We discuss the stochastic linear-quadratic (LQ) optimal control problem with Poisson processes under the indefinite case. Based on the wellposedness of the LQ problem, the main idea is expressed by the definition of relax compensator that extends the stochastic Hamiltonian system and stochastic Riccati equation with Poisson processes (SREP) from the positive definite case to the indefinite case. We mainly study the existence and uniqueness of the solution for the stochastic Hamiltonian system and obtain the optimal control with open-loop form. Then, we further investigate the existence and uniqueness of the solution for SREP in some special case and obtain the optimal control in close-loop form.     

EQUIVALENCE BETWEEN NONNEGATIVE SOLUTIONS TO PARTIAL SPARSE AND WEIGHTED l1-NORM MINIMIZATIONS

Based on the range space property (RSP), the equivalent conditions between nonnegative solutions to the partial sparse and the corresponding weighted l₁-norm minimization problem are studied in this paper. Different from other conditions based on the spark property, the mutual coherence, the null space property (NSP) and the restricted isometry property (RIP), the RSP-based conditions are easier to be verified. Moreover, the proposed conditions guarantee not only the strong equivalence, but also the equivalence between the two problems. First, according to the foundation of the strict complementarity theorem of linear programming, a sufficient and necessary condition, satisfying the RSP of the sensing matrix and the full column rank property of the corresponding sub-matrix, is presented for the unique nonnegative solution to the weighted l₁-norm minimization problem. Then, based on this condition, the equivalence conditions between the two problems are proposed. Finally, this paper shows that the matrix with the RSP of order k can guarantee the strong equivalence of the two problems.     

Mixed sensitivity minimization problems with rationall 1-optimal solutions

Up to this time, the only known method to solve the discrete-time mixed sensitivity minimization problem inl ¹ has been to use a certain infinite-dimensional linear programming approach, presented by Dahleh and Pearson in 1988 and later modified by Mendlovitz. That approach does not give in general true optimal solutions; only suboptimal ones are obtained. Here, for the first time, the truel ¹-optimal solutions are found for some mixed sensitivity minimization problems. In particular, Dahleh and Pearson construct an 11h order suboptimal compensator for a certain second-order plan with first-order weight functions; it is shown that the unique optimal compensator for that problem is rational and of order two. The author discovered this fact when trying out a new scheme of solving the infinite-dimensional linear programming system. This scheme is of independent interest, because when it is combined with the Dahleh-Pearson-Mendlovitz scheme, it gives both an upper bound and a lower bound on the optimal performance; hence, it provides the missing error bound that enables one to truncate the solution. Of course, truncation is appropriate only if the order of the optimal compensator is too high. This may indeed be the case, as is shown with an example where the order of the optimal compensator can be arbitrarily high.     

A fully polynomial time approximation scheme for the Replenishment Storage problem

The Replenishment Storage problem (RSP) is to minimize the storage capacity requirement for a deterministic demand, multi-item inventory system with specified individual reorder cycle lengths. The reorders can only take place at integer time units. This problem was shown to be weakly NP-hard for constant joint cycle length (the least common multiple of all individual cycle lengths). We devise here the first known FPTAS for the RSP with different individual cycle lengths and constant joint cycle length.     

Semidefinite Programming Techniques for Reduced Order Systems with Guaranteed Stability Margins

In this paper, the compensator based reduced order control design framework of Burns and King (J. Vibrations and Control, vol. 4, pp. 297–323, 1998) is modified to yield low order systems with guaranteed stability margins. This result is achieved through use of a logarithmic barrier function. In addition, a reduced basis method is formulated in which the compensator equations are approximated on uneven grids; guaranteed stability margins are also included. The methods are tested numerically on a one dimensional, nonlinear, damped, hyperbolic structural control problem. Examples are provided to illustrate differences between systems designed by both reduced basis methods.     

The impedance boundary value problem for the time harmonic Maxwell equations

The existence of a unique solution to Maxwell's equations defined in an exterior domain with impedance boundary condition is established for all frequencies. This is accomplished by reducing this problem to that of solving a system of singular integral equations and then regularizing this system such that the Riesz theory is applicable. We also consider the inverse problem in which it is desired to determine the impedance from a knowledge of the far field pattern. By restricting the impedance to lie a priori in a compact set results are obtained on the existence, uniqueness, and stability of the solution to this inverse scattering problem.     

Numerical solution of constant coefficient linear delay differential equations as abstract Cauchy problems

Summary. In this paper we present an approach for the numerical solution of delay differential equations where , and , different from the classical step-by-step method. We restate (1) as an abstract Cauchy problem and then we discretize it in a system of ordinary differential equations. The scheme of discretization is proved to be convergent. Moreover the asymptotic stability is investigated for two significant classes of asymptotically stable problems (1). Received May 4, 1998 / Revised version received January 25, 1999 / Published online November 17, 1999     

Numerical analysis for a conservative difference scheme to solve the Schrödinger-Boussinesq equation

In this paper, we present a finite difference scheme for the solution of an initial-boundary value problem of the Schrödinger-Boussinesq equation. The scheme is fully implicit and conserves two invariable quantities of the system. We investigate the existence of the solution for the scheme, give computational process for the numerical solution and prove convergence of iteration method by which a nonlinear algebra system for unknown Vⁿ⁺¹ is solved. On the basis of a priori estimates for a numerical solution, the uniqueness, convergence and stability for the difference solution is discussed. Numerical experiments verify the accuracy of our method.     

Forward dynamics simulation of human body under tilting perturbations

Human body uses different strategies to maintain its stability and these strategies vary from fixed-foot strategies to strategies which foot is moved in order to increase the support base. Tilting movement of foot is one type of the perturbations usually is exposed to human body. In the presence of such perturbations human body must employ appropriate reactions to prevent threats like falling. But it is not clear that how human body maintains its stability by central nervous system (CNS). At present study it is tried that by presenting a musculoskeletal model of human lower extremity with four links, three degrees of freedom (DOF) and eight skeletal muscles, the level of muscle activations causes the maintenance of stability, be investigated. Using forward dynamics solution, leads to a more general problem, rather than inverse dynamics. Hence, forward dynamics solution by forward optimization has been used for solving this highly nonlinear problem. To this end, first the system’s equations of motion has been derived using lagrangian dynamics. Eight Hill-type muscles as actuators of the system were modeled. Because determination of muscle forces considering their number is an undetermined problem, optimization of an appropriate goal function should be practiced. For optimization problem, the characteristics of genetic algorithms as a method based on direct search, and the direct collocation method, has been profited. Also by considering requirements of problem, some constraints such as conservation of model stability are entered into optimization procedure. Finally to investigate validation of model, the results from optimization and experimental data are compared and good agreements are obtained.     

广义双线性系统的输出变结构控制

首次利用广义Lyapunov函数方法针对不确定广义双线性系统的输出变结构控制问题进行研究.首先,选取设计了带有滑动模动态补偿器的切换函数,保证了系统在准切换流形上的渐近稳定性.其次,在不确定参数和扰动范数有界的条件下,设计了变结构控制器,使得在控制下闭环系统在有限时间内实现滑模运动.最后,通过数值算例说明了设计方法的合理性和有效性.     

A new convergence proof of the Adomian decomposition method for a mixed hyperbolic elliptic system of conservation laws

In this paper, we propose a new convergence proof of the Adomian’s decomposition method (ADM), applied to the generalized nonlinear system of partial differential equations (PDE’s) based on new formula for Adomian polynomials. The decomposition scheme obtained from the ADM yields an analytical solution in the form of a rapidly convergent series for a system of conservation laws. Systems of conservation laws is presented, we obtain the stability of the approximate solution when the system changes type. We show with an explicit example that the latter property is true for general Cauchy problem satisfying convergence hypothesis. The results indicate that the ADM is effective and promising.     

A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs

Let G be a labeled directed graph with arc labels drawn from alphabet Σ, R be a regular expression over Σ, and x and y be a pair of nodes from G. The regular simple path (RSP) problem is to determine whether there is a simple path p in G from x to y, such that the concatenation of arc labels along p satisfies R. Although RSP is known to be NP-hard in general, we show that it is solvable in polynomial time when G is outerplanar. The proof proceeds by presenting an algorithm which gives a polynomial-time reduction of RSP for outerplanar graphs to RSP for directed acyclic graphs, a problem which has been shown to be solvable in polynomial time.     

Pattern-forming systems for control of large arrays of actuators

Summary. We consider an approach for coordinating the activity of a large array of microactuators via diffusive (i.e., nearest-neighbor) coupling combined with reactive growth and decay, implemented via interconnection templates which have been artificially engineered into the system (for example, in collocated microelectronic circuitry, or through the formulation of active material layers). Such coupled systems can support interesting spatiotemporal patterns, which in turn determine the actuation patterns. Generating such spatiotemporal patterns typically involves stressing the interconnections by raising or lowering a parameter resulting in the crossing of stability thresholds. The possibility of making such parametric adjustments via feedback on a slower timescale offers a solution to the problem of communicating effectively within a large array: The communication is achieved through the interconnection template. The mathematics behind this idea leads us into the rich domain of nonlinear partial differential equations (PDEs) with spatiotemporal pattern solutions. We present a global nonlinear stability analysis that applies to certain model pattern-forming systems. The nonlinear stability analysis could serve as a starting point for control system design for systems containing large microactuator arrays. Received August 1, 2000; accepted August 16, 2001 Online publication November 5, 2001     

Stability improvement of multimachine power system via new coordinated design of PSSs and SVC

In this article, the assessment of new coordinated design of power system stabilizers (PSSs) and static var compensator (SVC) in a multimachine power system via statistical method is proposed. The coordinated design problem of PSSs and SVC over a wide range of loading conditions is handled as an optimization problem. The bacterial swarming optimization (BSO), which synergistically couples the bacterial foraging with the particle swarm optimization (PSO), is used to seek for optimal controllers parameters. By minimizing the proposed objective function, in which the speed deviations between generators are involved; stability performance of the system is enhanced. To compare the capability of PSS and SVC, both are designed independently, and then in a coordinated manner. Simultaneous tuning of the BSO‐based coordinated controller gives robust damping performance over wide range of operating conditions and large disturbance in compare to optimized PSS controller based on BSO (BSOPSS) and optimized SVC controller based on BSO (BSOSVC). Moreover, a statistical T test is executed to validate the robustness of coordinated controller versus uncoordinated one. © 2014 Wiley Periodicals, Inc. Complexity 21: 256–266, 2015     

Quantitative stability analysis of stochastic quasi-variational inequality problems and applications

We consider a parametric stochastic quasi-variational inequality problem (SQVIP for short) where the underlying normal cone is defined over the solution set of a parametric stochastic cone system. We investigate the impact of variation of the probability measure and the parameter on the solution of the SQVIP. By reformulating the SQVIP as a natural equation and treating the orthogonal projection over the solution set of the parametric stochastic cone system as an optimization problem, we effectively convert stability of the SQVIP into that of a one stage stochastic program with stochastic cone constraints. Under some moderate conditions, we derive Hölder outer semicontinuity and continuity of the solution set against the variation of the probability measure and the parameter. The stability results are applied to a mathematical program with stochastic semidefinite constraints and a mathematical program with SQVIP constraints.     

Dynamics and control of a system of two non‐interacting preys with common predator

In this paper, we consider a Holling type model, which describes the interaction between two preys with a common predator. First, we give some sufficient conditions for the globally asymptotic stability and prove that local stability implies global stability. Then, we present a set of sufficient conditions for the existence of a positive periodic solution with strictly positive components. Finally, the optimal control strategy is developed to minimize the number of predator and maximize the number of preys. We also show the existence of an optimal control for the optimal control problem and derive the optimality system. The technical tool used to determine the optimal strategy is the Pontryagin Maximum Principle. Finally, the numerical simulations of global stability and the optimal problem are given as the conclusion of this paper. Copyright © 2011 John Wiley & Sons, Ltd.