Algorithms for network piecewise-linear programs: A comparative study

Piecewise-Linear Programming (PLP) is an important area of Mathematical Programming and concerns the minimisation of a convex separable piecewise-linear objective function, subject to linear constraints. In this paper a subarea of PLP called Network Piecewise-Linear Programming (NPLP) is explored. The paper presents four specialised algorithms for NPLP: (Strongly Feasible) Primal Simplex, Dual Method, Out-of-Kilter and (Strongly Polynomial) Cost-Scaling and their relative efficiency is studied. A statistically designed experiment is used to perform a computational comparison of the algorithms. The response variable observed in the experiment is the CPU time to solve randomly generated network piecewise-linear problems classified according to problem class (Transportation, Transshipment and Circulation), problem size, extent of capacitation, and number of breakpoints per arc. Results and conclusions on performance of the algorithms are reported.

Dynamics of a piecewise-linear oscillator with limited power supply

We discuss dynamics of a vibro-impact system consisting of a cart with an piecewise-linear restoring force, which vibrates under driving by a source with limited power supply. From the point of view of dynamical systems, vibro-impact systems exhibit a rich variety of phenomena, particularly chaotic motion. In our analyzes, we use bifurcation diagrams, basins of attractions, identifying several non-linear phenomena, such as chaotic regimes, crises, intermittent mechanisms, and coexistence of attractors with complex basins of attraction. © 2009 by ASME.

Mather invariants in groups of piecewise-linear homeomorphisms

We describe the relation between two characterizations of conjugacy in groups of piecewise-linear homeomorphisms, discovered by Brin and Squier in [2] and Kassabov and Matucci in [5]. Thanks to the interplay between the techniques, we produce a simplified point of view of conjugacy that allows ua to easily recover centralizers and lends itself to generalization.

The simultaneous conjugacy problem in groups of piecewise linear functions

Guba and Sapir asked, in their joint paper [8], if the simultaneous conjugacy problem was solvable in Diagram Groups or, at least, for Thompson's group F. We give an elementary proof for the solution of the latter question. This relies purely on the description of F as the group of piecewise linear orientation-preserving homeomorphisms of the unit. The techniques we develop allow us also to solve the ordinary conjugacy problem as well, and we can compute roots and centralizers. Moreover, these techniques can be generalized to solve the same questions in larger groups of piecewise-linear homeomorphisms.

On the tractability of the piecewise-linear approximation for general discrete-choice network revenue management

The choice network revenue management (RM) model incorporates customer purchase behavioras customers purchasing products with certain probabilities that are a function of the offeredassortment of products, and is the appropriate model for airline and hotel network revenuemanagement, dynamic sales of bundles, and dynamic assortment optimization. The underlyingstochastic dynamic program is intractable and even its certainty-equivalence approximation, inthe form of a linear program called Choice Deterministic Linear Program (CDLP) is difficultto solve in most cases. The separation problem for CDLP is NP-complete for MNL with justtwo segments when their consideration sets overlap; the affine approximation of the dynamicprogram is NP-complete for even a single-segment MNL. This is in contrast to the independentclass(perfect-segmentation) case where even the piecewise-linear approximation has been shownto be tractable. In this paper we investigate the piecewise-linear approximation for network RMunder a general discrete-choice model of demand. We show that the gap between the CDLP andthe piecewise-linear bounds is within a factor of at most 2. We then show that the piecewiselinearapproximation is polynomially-time solvable for a fixed consideration set size, bringing itinto the realm of tractability for small consideration sets; small consideration sets are a reasonablemodeling tradeoff in many practical applications. Our solution relies on showing that forany discrete-choice model the separation problem for the linear program of the piecewise-linearapproximation can be solved exactly by a Lagrangian relaxation. We give modeling extensionsand show by numerical experiments the improvements from using piecewise-linear approximationfunctions.

Toplological Entropy in the Syncronization of Piecewise Linear and Monotone Maps. Coupled Duffing Oscillators

In this paper is presented a relationship between the synchronization and the topological entropy. We obtain the values for the coupling parameter, in terms of the topological entropy, to achieve synchronization of two unidirectional and bidirectional coupled piecewise linear maps. In addition, we prove a result that relates the synchronizability of two m-modal maps with the synchronizability of two conjugated piecewise linear maps. An application to the unidirectional and bidirectional coupled identical chaotic Duffing equations is given. We discuss the complete synchronization of two identical double-well Duffing oscillators, from the point of view of symbolic dynamics. Working with Poincare cross-sections and the return maps associated, the synchronization of the two oscillators, in terms of the coupling strength, is characterized.

Conjugacy of piecewise linear Lorenz map that expand on average

For piecewise linear Lorenz map that expand on average, we show that it admits a dichotomy: it is either periodic renormalizable or prime. As a result, such a map is conjugate to a ß-transformation.

Equivalence of piecewise-linear approximation and Lagrangian relaxation for network revenue management

The network revenue management (RM) problem arises in airline, hotel, media,and other industries where the sale products use multiple resources. It can be formulatedas a stochastic dynamic program but the dynamic program is computationallyintractable because of an exponentially large state space, and a number of heuristicshave been proposed to approximate it. Notable amongst these -both for their revenueperformance, as well as their theoretically sound basis- are approximate dynamic programmingmethods that approximate the value function by basis functions (both affinefunctions as well as piecewise-linear functions have been proposed for network RM)and decomposition methods that relax the constraints of the dynamic program to solvesimpler dynamic programs (such as the Lagrangian relaxation methods). In this paperwe show that these two seemingly distinct approaches coincide for the network RMdynamic program, i.e., the piecewise-linear approximation method and the Lagrangianrelaxation method are one and the same.

LIMIT CYCLES of DISCONTINUOUS PIECEWISE LINEAR DIFFERENTIAL SYSTEMS

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Bifurcation of limit cycles from an n-dimensional linear center inside a class of piecewise linear differential systems

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

On the limit cycles of a class of piecewise linear differential systems in R-4 with two zones

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Piecewise linear perturbations of a linear center

This paper is mainly devoted to the study of the limit cycles that can bifurcate from a linear center using a piecewise linear perturbation in two zones. We consider the case when the two zones are separated by a straight line Σ and the singular point of the unperturbed system is in Σ. It is proved that the maximum number of limit cycles that can appear up to a seventh order perturbation is three. Moreover this upper bound is reached. This result confirms that these systems have more limit cycles than it was expected. Finally, center and isochronicity problems are also studied in systems which include a first order perturbation. For the latter systems it is also proved that, when the period function, defined in the period annulus of the center, is not monotone, then it has at most one critical period. Moreover this upper bound is also reached.

Bifurcations Leading to Nonlinear Oscillations in a 3D Piecewise Linear Memristor Oscillator

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Piecewise Linear Systems with Closed Sliding Poly-Trajectories

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

On the number of limit cycles in discontinuous piecewise linear differential systems with two pieces separated by a straight line

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)