A special ordered set approach for optimizing a discontinuous separable piecewise linear function

We give a special ordered set (SOS) approach that optimizes a discontinuous separable piecewise linear function, even when a mixed-integer programming (MIP) model is not available for it. When a MIP model is available, our SOS model gives a linear programming relaxation bound that is as good as the MIPs.     

A piecewise linear upper bound on the network recourse function

We consider the optimal value of a pure minimum cost network flow problem as a function of supply, demand and arc capacities. We present a new piecewise linear upper bound on this function, which is called the network recourse function. The bound is compared to the standard Madansky bound, and is shown computationally to be a little weaker, but much faster to find. The amount of work is linear in the number of stochastic variables, not exponential as is the case for the Madansky bound. Therefore, the reduction in work increases as the number of stochastic variables increases. Computational results are presented.     

Utility function assessment on a micro-computer: An interactive procedure

The procedure UFAP is presented which allows a decision maker to interactively assess his von Neumann/Morgenstern single attribute utility function. UFAP puts special emphasis on potential biases in the assessment process. In the first part of the procedure three different assessment methods are used to derive ranges for the utility function. Using different methods enables us to point out a possible bias in the elicitation process. In the second part a consistent class of utility functions is derived based on the ranges assessed in the first part. In case inconsistencies between methods arise the decision maker has to reconsider selected preference statements previously given.     

An algorithm for the estimation of a regression function by continuous piecewise linear functions

The problem of the estimation of a regression function by continuous piecewise linear functions is formulated as a nonconvex, nonsmooth optimization problem. Estimates are defined by minimization of the empirical L ₂ risk over a class of functions, which are defined as maxima of minima of linear functions. An algorithm for finding continuous piecewise linear functions is presented. We observe that the objective function in the optimization problem is semismooth, quasidifferentiable and piecewise partially separable. The use of these properties allow us to design an efficient algorithm for approximation of subgradients of the objective function and to apply the discrete gradient method for its minimization. We present computational results with some simulated data and compare the new estimator with a number of existing ones.     

Planar piecewise linear random motions with jumps

In this paper, we study persistent piecewise linear multidimensional random motions. Their velocities, switching at Poisson times, are uniformly distributed on a sphere. The changes of direction are accompanied with subsequent jumps of random length and of uniformly distributed orientation. In this paper, we obtain some useful properties and formulae of distributions of these processes. In particular, we get these distributions in the cases of jumps with Gaussian and exponential distributions of jump magnitudes.     

Computational complexity of a piecewise linear homotopy algorithm

We give a bound on the number of steps required by the piecewise linear algorithm based on component wise homotopy (proposed by the author for structured problems) when solving a linear problem. When the coefficient matrix is symmetric and positive definite, this bound is polynomial inn and linear in the condition number of the matrix. We also investigate the expected value of the bound for a particular distribution of such matrices. This research has been partially supported by the grant MCS 80-05154 from the National Science Foundation.     

An example of a piecewise linear ergodic polymorphism

We consider dynamical systems introduced by Vershik and called polymorphisms. In particular, such systems encompass the class of multivalued mappings of a closed interval onto itself which have an invariant measure. Polymorphisms arise in different areas of mathematics and mechanics, for example, in the problem of the destruction of the adiabatic invariant. We are concerned with the ergodic properties of polymorphisms. The first section deals with the main notions. In Secs. 2 and 3, we consider an example of a three-parameter family of ergodic polymorphisms formed by piecewise linear mappings.     

A constitutive model for polymers with a piecewise linear yield surface

Reliable prediction of the behaviour of structures made from polymers, especially under high dynamic loading, is a topic under considerable investigation in engineering practice. A constitutive model is derived including important phenomena like necking, crazing and strain rate dependency. In particular, different yield surfaces in compression and tension are taken into account using a piecewise linear formulation. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Special modes in a two-sector economy model with an integral utility function

In this work, we study a two-sector economic model with the Cobb–Douglas production function on an infinite planning horizon where the utility function is a functional of an integral form and a Lagrangian of a logarithmic type. A one-dimensional equation is obtained that depends only on the coefficients of elasticity and amortization, and determines the possible special modes. The special modes are described in analytical form.     

Global stability of a two-species piecewise linear volterra ecosystem

This paper extends the results of Goh [1], and Takeuchi and Adachi [2,3] concerning the generalized linear Volterra model. We introduce a piecewise linear Volterra model for a two- species system. The solution of the steady-state problem is then shown to be equivalent to finding the solution to the Generalized Linear Complementarity Problem. We show when this nonnegative equilibrium is unique and globally asymptotically stable in the sense of Goh [1].     

Complex behaviour in a piecewise linear dynamic macroeconomic model with endogenous discontinuity

This paper examines the dynamic property of a macroeconomic model developed by Matsuyama [Am. Econ. Rev. 97(2007), pp. 503–516] in detail. It is shown that the model can be transformed into a version of the neuron model analysed by Hata [J. Math. Kyoto Univ. 22(1982), pp. 155–173, Chaos in Neural Network Models (in Japanese), Asakura, Tokyo 1998] and that the system can exhibit either periodic fluctuations or non-periodic (chaotic) fluctuations.     

All invariant densities of piecewise linear Markov maps are piecewise constant

Let τ: [0,1] → [0,1] be a piecewise linear Markov map. It is shown that all density functions invariant under τ must be piecewise constant. This has useful application to solutions of functional equations.     

Pseudo-criteria versus linear utility function in stochastic multi-criteria acceptability analysis

Stochastic multi-criteria acceptability analysis (SMAA) is a multi-criteria decision support method for multiple decision-makers (DMs) in discrete problems. SMAA does not require explicit or implicit preference information from the DMs. Instead, the method is based on exploring the weight space in order to describe the valuations that would make each alternative the preferred one. Partial preference information can be represented in the weight space analysis through weight distributions. In this paper we compare two variants of the SMAA method using randomly generated test problems with 2–12 criteria and 4–12 alternatives. In the original SMAA, a utility or value function models the DMs' preference structure, and the inaccuracy or uncertainty of the criteria is represented by probability distributions. In SMAA-3, ELECTRE III-type pseudo-criteria are used instead. Both methods compute for each alternative an acceptability index measuring the variety of different valuations that supports this alternative, and a central weight vector representing the typical valuations resulting in this decision. We seek answers to three questions: (1) how similar are the results provided by the decision models, (2) what kind of systematic differences exists between the models, and (3) how could one select indifference and preference thresholds of the pseudo-criteria model to match a utility model with given probability distributions?     

Transiently chaotic neural networks with piecewise linear output functions

Admitting both transient chaotic phase and convergent phase, the transiently chaotic neural network (TCNN) provides superior performance than the classical networks in solving combinatorial optimization problems. We derive concrete parameter conditions for these two essential dynamic phases of the TCNN with piecewise linear output function. The confirmation for chaotic dynamics of the system results from a successful application of the Marotto theorem which was recently clarified. Numerical simulation on applying the TCNN with piecewise linear output function is carried out to find the optimal solution of a travelling salesman problem. It is demonstrated that the performance is even better than the previous TCNN model with logistic output function.     

Preemptive scheduling with staircase and piecewise linear resource availability

Some variations are presented for the preemptive scheduling problem on unrelated processors, one shows how nonrenewable resources with a time-varying supply may be taken into account in an extension of the two-phase method; phase 1 consists in solving an LP problem and phase 2 is the construction of the schedule; such a construction reduces to the determination of integral vectors in polyhedra defined by totally unimodular matrices. In special cases, this is simply a compatible flow problem.

---

Zusammenfassung Es werden Variationen für Reihenfolgeprobleme mit Unterbrechungen betrachtet bei denen die Aufgaben mit unterschiedlicher Bearbeitungszeit auf den einzelnen Maschinen gelöst werden können. Insbesondere wird ein Problem mit nichterneuerbaren Resourcen und zeitabhängigen Nachfragen behandelt und es wird gezeigt, daß dieses Problem durch eine Erweiterung der 2-Phasenmethode gelöst werden kann. In Phase 1 wird ein LP gelöst, während in Phase 2 ein zugehöriger Schedule konstruiert wird. Diese Konstruktion erfolgt durch die Bestimmung ganzzahliger Vektoren, die Ecken eines Polyeders entsprechen, der durch eine vollständig unimodulare Matrix definiert wird. In Spezialfällen reduziert sich dies auf Flußprobleme.

     

Approximations by the Cauchy-type integrals with piecewise linear densities

The paper is a contribution to the complex variable boundary element method, shortly CVBEM. It is focused on Jordan regions having piecewise regular boundaries without cusps. Dini continuous densities whose modulus of continuity ω(·) satisfies $$\mathop {\lim \sup }\limits_{s \downarrow 0} \omega (s)\ln {1 \over s} = 0$$ are considered on these boundaries. Functions satisfying the Hölder condition of order α, 0 < α ? 1, belong to them. The statement that any Cauchy-type integral with such a density can be uniformly approximated by a Cauchy-type integral whose density is a piecewise linear interpolant of the original one is proved under the assumption that the mesh of the interpolation nodes is sufficiently fine and uniform. This result ensures the existence of approximate CVBEM solutions of some planar boundary value problems, especially of the Dirichlet ones.     

Modeling gene regulatory networks with piecewise linear differential equations

Microarray chips generate large amounts of data about a cell’s state. In our work we want to analyze these data in order to describe the regulation processes within a cell. Therefore, we build a model which is capable of capturing the most relevant regulating interactions and present an approach how to calculate the parameters for the model from time-series data. This approach uses the discrete approximation method of least squares to solve a data fitting modeling problem. Furthermore, we analyze the features of our proposed system, i.e., which kinds of dynamical behaviors the system is able to show.