Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice

In Eurocrypt 2004 Augot and Finiasz presented a coding theoretic public key cryptosystem that suggests a new approach for designing such systems based on the Polynomial Reconstruction Problem (PR). Their cryptosystem is an instantiation of this approach under a specific choice of parameters which, given the state of the art of coding theory, we show in this work to be sub-optimal. Coron showed how to attack the Augot and Finiasz cryptosystem. A question left open is whether the general approach suggested by the cryptosystem works or not. In this work, we show that the general approach (rather than only the instantiation) is broken as well.      

基于样条插值的模糊控制算法

利用三次样条插值函数,直接由控制输入输出数据对建立了控制输入与控制输出之间的映射关系,得到了一元三次样条插值控制算法和二元双三次样条插值控制算法,并将二者分别用于单输入单输出系统和双输入单输出系统的仿真控制.仿真结果表明,上述方法是可行的,并且基于三次样条函数的模糊插值控制,具有响应快,无超调,稳态误差极小等很好的控制效果.其设计简单,不需要过多规则,对稀疏规则库条件下的控制器设计尤为适用.     

A convergence proof for linear mean value cross decomposition

The mean value cross decomposition method for linear programming problems is a modification of ordinary cross decomposition that eliminates the need for using the Benders or Dantzig-Wolfe master problem. It is a generalization of the Brown-Robinson method for a finite matrix game and can also be considered as a generalization of the Kornai-Liptak method. It is based on the subproblem phase in cross decomposition, where we iterate between the dual subproblem and the primal subproblem. As input to the dual subproblem we use the average of a part of all dual solutions of the primal subproblem, and as input to the primal subproblem we use the average of a part of all primal solutions of the dual subproblem. In this paper we give a new proof of convergence for this procedure. Previously convergence has only been shown for the application to a special separable case (which covers the Kornai-Liptak method), by showing equivalence to the Brown-Robinson method.     

Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming

Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming. A decomposition method with wide applicability is Benders' decomposition, which has been applied to both stochastic programming as well as integer programming problems. However, this method of decomposition relies on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s) is not convex, and new approaches must be designed. In this paper, we discuss alternative decomposition methods in which the second-stage integer subproblems are solved using branch-and-cut methods. One of the main advantages of our decomposition scheme is that Stochastic Mixed-Integer Programming (SMIP) problems can be solved by dividing a large problem into smaller MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage stochastic mixed-integer programs.     

A sliding mode control for linear fractional systems with input and state delays

In this paper, a sliding mode control design for fractional order systems with input and state time-delay is proposed. First, we consider a fractional order system without delay for which a sliding surface is proposed based on fractional integration of the state. Then, a stabilizing switching controller is derived. Second, a fractional system with state delay is considered. Third, a strategy including a fractional state predictor input delay compensation is developed. The existence of the sliding mode and the stability of the proposed control design are discussed. Numerical examples are given to illustrate the theoretical developments.     

An ILP based hierarchical global routing approach for VLSI ASIC design

The use of integrated circuits in high-performance computing, telecommunications, and consumer electronics has been growing at a very fast pace. The level of integration as measured by the number of logic gates in a chip has been steadily rising due to the rapid progress in processing and interconnect technology. The interconnect delay in VLSI circuits has become a critical determiner of circuit performance. As a result, circuit layout is starting to play a more important role in today’s chip designs. Global routing is one of the key sub-problems of circuit layout which involves finding an approximate path for the wires connecting the elements of the circuit without violating resource constraints. In this paper, several integer programming (ILP) based global routing models are fully investigated and explored. The resulting ILP problem is relaxed and solved as a linear programming (LP) problem followed by a rounding heuristic to obtain an integer solution. Experimental results obtained show that the proposed combined WVEM (wirelength, via, edge capacity) model can optimize several global routing objectives simultaneously and effectively. In addition, several hierarchical methods are combined with the proposed flat ILP based global router to reduce the CPU time by about 66% on average for edge capacity model (ECM).     

On the formulation of stochastic linear programs using algebraic modelling languages

This paper considers extensions to algebraic modelling languages to support formulation, instantiation and solver integration for stochastic linear programs (SLPs). We present a taxonomy of SLP problem types and analyze formulation requirements including distribution handling by class of problem. We demonstrate suggested formulations for most problem classes, show solver input in the S-MPS standard, and propose consistency checks for constraints involving stochastic data items. Some unresolved difficulties are identified.     

DEA environmental assessment: Measurement of damages to scale with unified efficiency under managerial disposability or environmental efficiency

This study proposes a use of Data Envelopment Analysis (DEA) for environmental assessment. Firms usually produce not only desirable but also undesirable outputs as a result of their economic activities. The concept of disposability on undesirable outputs is separated into natural and managerial disposability. Natural disposability is an environmental strategy in which firms decrease their inputs to reduce a vector of undesirable outputs. Given the reduced input vector, they attempt to increase desirable outputs as much as possible. Managerial disposability involves the opposite strategy of increasing an input vector. The concept of disposability expresses an environmental strategy that considers a regulation change on undesirable outputs as a new business opportunity. Firms attempt to improve their unified (operational and environmental) performance by utilizing new technology and/or new management. Considering the two disposability concepts, this study discusses how to measure unified efficiency under managerial disposability and then discusses how to measure environmental efficiency. The proposed uses of DEA can serve as an empirical basis for measuring new economic concepts such as “Scale Damages (SD)”, corresponding to scale economies for undesirable outputs, and “Damages to Scale (DTS)”, corresponding to returns to scale for undesirable outputs.     

Radial basis function networks for internal model control

In this paper radial basis function (RBF) networks are used in the framework of nonlinear internal model control (IMC). A nonlinear IMC strategy is proposed that includes explicit input weighting. This strategy yields a control law in form of an analytical expression if a control-linear RBF model is used. Important implementation issues such as disturbance modeling and state estimation are discussed and an extended Kalman filter approach is proposed for combined state and model parameter estimation. Simulation studies for a continuous stirred tank reactor with multiple steady states indicate that the proposed control strategy is well suited for the control of unstable nonlinear systems.     

Multi-reservoir production optimization

When a large oil or gas field is produced, several reservoirs often share the same processing facility. This facility is typically capable of processing only a limited amount of commodities per unit of time. In order to satisfy these processing limitations, the production needs to be choked, i.e., scaled down by a suitable choke factor. A production strategy is defined as a vector valued function defined for all points of time representing the choke factors applied to reservoirs at any given time. In the present paper we consider the problem of optimizing such production strategies with respect to various types of objective functions. A general framework for handling this problem is developed. A crucial assumption in our approach is that the potential production rate from a reservoir can be expressed as a function of the remaining recoverable volume. The solution to the optimization problem depends on certain key properties, e.g., convexity or concavity, of the objective function and of the potential production rate functions. Using these properties several important special cases can be solved. An admissible production strategy is a strategy where the total processing capacity is fully utilized throughout a plateau phase. This phase lasts until the total potential production rate falls below the processing capacity, and after this all the reservoirs are produced without any choking. Under mild restrictions on the objective function the performance of an admissible strategy is uniquely characterized by the state of the reservoirs at the end of the plateau phase. Thus, finding an optimal admissible production strategy, is essentially equivalent to finding the optimal state at the end of the plateau phase. Given the optimal state a backtracking algorithm can then used to derive an optimal production strategy. We will illustrate this on a specific example.     

Abstraction-based synthesis for stochastic systems with omega-regular objectives

This paper studies the synthesis of controllers for discrete-time, continuous state stochastic systems subject to omega-regular specifications using finite-state abstractions. Omega-regular properties allow specifying complex behaviors and encompass, for example, linear temporal logic. First, we present a synthesis algorithm for minimizing or maximizing the probability that a discrete-time switched stochastic system with a finite number of modes satisfies an omega-regular property. Our approach relies on a finite-state abstraction of the underlying dynamics in the form of a Bounded-parameter Markov Decision Process arising from a finite partition of the system’s domain. Such Markovian abstractions allow for a range of probabilities of transition between states for each selected action representing a mode of the original system. Our method is built upon an analysis of the Cartesian product between the abstraction and a Deterministic Rabin Automaton encoding the specification of interest or its complement. Specifically, we show that synthesis can be decomposed into a qualitative problem, where the so-called greatest permanent winning components of the product automaton are created, and a quantitative problem, which requires maximizing the probability of reaching this component in the worst-case instantiation of the transition intervals. Additionally, we propose a quantitative metric for measuring the quality of the designed controller with respect to the continuous abstracted states and devise a specification-guided domain partition refinement heuristic with the objective of reaching a user-defined optimality target. Next, we present a method for computing control policies for stochastic systems with a continuous set of available inputs. In this case, the system is assumed to be affine in input and disturbance, and we derive a technique for solving the qualitative and quantitative problems in the resulting finite-state abstractions of such systems. For this, we introduce a new type of abstractions called Controlled Interval-valued Markov Chains. Specifically, we show that the greatest permanent winning component of such abstractions are found by appropriately partitioning the continuous input space in order to generate a bounded-parameter Markov decision process that accounts for all possible qualitative transitions between the finite set of states. Then, the problem of maximizing the probability of reaching these components is cast as a (possibly non-convex) optimization problem over the continuous set of available inputs. A metric of quality for the synthesized controller and a partition refinement scheme are described for this framework as well. Finally, we present a detailed case study.     

Performance evaluation of distribution strategies for the inventory routing problem

Direct shipping strategy is an easy-to-implement distribution strategy frequently used in industrial distribution systems. In this paper, an analytic method is developed for performance evaluation of the strategy for the infinite horizon inventory routing problem with delivery frequency constraint. With the method, the effectiveness of direct shipping strategy can be represented as a function of some system parameters. We demonstrate that the effectiveness of direct shipping is at least the square root of the smallest utilization ratio of vehicle capacity. This implies that the effectiveness of the strategy can reach 100% (respectively, 94.86%) whenever the demand rate of each retailer is 100% (respectively, 90%) of the vehicle capacity multiplied by the upper bound of the delivery frequency. This insight can help a firm answer questions such as: under what conditions direct shipping strategy is effective and why, and how effective the strategy is under a specific condition? In case direct shipping strategy is proven ineffective, a more general Fixed Partition Policy (FPP) that combines direct shipping strategy and multiple-stop shipping strategy must be used. An analytic method is also developed for performance evaluation of general FPPs. We demonstrate that the effectiveness of an FPP depends on the total demand rate of the retailers in each partition (each retailer set) and their closeness level. This insight provides a useful guideline to the design of effective FPPs. The analytic methods make the performance improvement of a distribution system possible through adjusting its system parameters.     

Identifying algorithmic vulnerabilities through simulated annealing

Real-time software systems with tight performance requirements are abundant. These systems frequently use many different algorithms and if any one of these algorithms was to experience behavior that is atypical because of the input, the entire system may not be able to meet its performance requirements. Unfortunately, it is algorithmically intractable, if not unsolvable, to find the inputs which would cause worst-case behavior. If inputs can be identified that make the system take, say, ten times longer compared to the time it usually takes, that information is valuable for some systems. In this paper, we present a method for finding inputs that perform much worse than the average input to different algorithms. We use the simulated annealing heuristic search method and show that this method is successful in finding worst-case inputs to several sorting algorithms, using several measures of an algorithm’s runtime.     

Analysis of a Fork/Join Synchronization Station with Inputs from Coxian Servers in a Closed Queuing Network

Fork/join stations are commonly used to model the synchronization constraints in queuing models of computer networks, fabrication/assembly systems and material control strategies for manufacturing systems. This paper presents an exact analysis of a fork/join station in a closed queuing network with inputs from servers with two-phase Coxian service distributions, which models a wide range of variability in the input processes. The underlying queue length and departure processes are analyzed to determine performance measures such as throughput, distributions of the queue length and inter-departure times from the fork/join station. The results show that, for certain parameter settings, variability in the arrival processes has a significant impact on system performance. The model is also used to study the sensitivity of performance measures such as throughput, mean queue lengths, and variability of inter-departure times for a wide range of input parameters and network populations.     

Sliding mode control of inventory management systems with bounded batch size

In this paper, variable structure control of discrete time systems is considered and the idea of reaching law based sliding mode control is presented. Then the idea is applied to design a control strategy for a class of supply chains with multiple suppliers. In the considered inventory management systems, goods are delivered to a single warehouse with limited capacity. Suppliers themselves have finite manufacturing capabilities, but are also not willing to accept orders of negligible size. The reaching law proposed for such systems ensures full satisfaction of the unpredictable consumers’ demand while adhering to state and input constraints.     

混合动力公交车能量控制策略的优化模型

针对混合动力公交车在循环工况内功率需求的特点,建立了未来功率需求贝叶斯预测模型;利用2-阶段随机动态规划模型将大规模的随机动态规划问题简化为多个小规模的随机动态规划问题和一个确定型动态规划问题;对于随机动态规划模型的求解,给出了稀疏表示的降维方法,将复杂的泛函极值问题转化为常规的随机动态优化问题,并采用分布估计算法和计算资源最优配置算法的计算机仿真优化算法对随机动态优化问题进行求解;给出了基于查表的在线控制策略,为模型的实际应用进行了有益的探索。     

Splitting and composition methods for explicit time dependence in separable dynamical systems

We consider splitting methods for the numerical integration of separable non-autonomous differential equations. In recent years, splitting methods have been extensively used as geometric numerical integrators showing excellent performances (both qualitatively and quantitatively) when applied on many problems. They are designed for autonomous separable systems, and a substantial number of methods tailored for different structures of the equations have recently appeared. Splitting methods have also been used for separable non-autonomous problems either by solving each non-autonomous part separately or after each vector field is frozen properly. We show that both procedures correspond to introducing the time as two new coordinates. We generalize these results by considering the time as one or more further coordinates which can be integrated following either of the previous two techniques. We show that the performance as well as the order of the final method can strongly depend on the particular choice. We present a simple analysis which, in many relevant cases, allows one to choose the most appropriate split to retain the high performance the methods show on the autonomous problems. This technique is applied to different problems and its performance is illustrated for several numerical examples.     

A note on the security of MST 3

In this paper, we study the recently proposed encryption scheme MST ₃, focusing on a concrete instantiation using Suzuki-2-groups. In a passive scenario, we argue that the one wayness of this scheme may not, as claimed, be proven without the assumption that factoring group elements with respect to random covers for a subset of the group is hard. As a result, we conclude that for the proposed Suzuki 2-groups instantiation, impractical key sizes should be used in order to prevent more or less straightforward factorization attacks.