Piecewise-linear programming: The compact (CPLP) algorithm

A compact algorithm is presented for solving the convex piecewise-linear-programming problem, formulated by means of a separable convex piecewise-linear objective function (to be minimized) and a set of linear constraints. This algorithm consists of a finite sequence of cycles, derived from the simplex method, characteritic of linear programming, and the line search, characteristic of nonlinear programming. Both the required storage and amount of calculation are reduced with respect to the usual approach, based on a linear-programming formulation with an expanded tableau. The tableau dimensions arem×(n+1), wherem is the number of constraints andn the number of the (original) structural variables, and they do not increase with the number of breakpoints of the piecewise-linear terms constituting the objective function.     

A simplex algorithm for piecewise-linear programming I: Derivation and proof

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. This three-part paper develops and analyzes a general, computationally practical simplex algorithm for piecewiselinear programming.Part I derives and justifies the essential steps of the algorithm, by extension from the simplex method for linear programming in bounded variables. The proof employs familiar finite-termination arguments and established piecewise-linear duality theory.Part II considers the relaxation of technical assumptions pertaining to finiteness, feasibility and nondegeneracy of piecewise-linear programs. Degeneracy is found to have broader consequences than in the linear case, and the standard techniques for prevention of cycling are extended accordingly.Part III analyzes the computational requirements of piecewise-linear programming. The direct approach embodied in the piecewise-linear simplex algorithm is shown to be inherently more efficient than indirect approaches that rely on transformation of piecewise-linear programs to equivalent linear programs. A concluding section surveys the many applications of piecewise-linear programming in linear programming,l ₁ estimation, goal programming, interval programming, and nonlinear optimization.This research has been supported in part by the National Science Foundation under grant MCS-8217261.     

Finding all solutions of separable systems of piecewise-linear equations using integer programming

Finding all solutions of nonlinear or piecewise-linear equations is an important problem which is widely encountered in science and engineering. Various algorithms have been proposed for this problem. However, the implementation of these algorithms are generally difficult for non-experts or beginners. In this paper, an efficient method is proposed for finding all solutions of separable systems of piecewise-linear equations using integer programming. In this method, we formulate the problem of finding all solutions by a mixed integer programming problem, and solve it by a high-performance integer programming software such as GLPK, SCIP, or CPLEX. It is shown that the proposed method can be easily implemented without making complicated programs. It is also confirmed by numerical examples that the proposed method can find all solutions of medium-scale systems of piecewise-linear equations in practical computation time.     

On topological types of ordered median functions

An ordered median functions is a continuous piecewise-linear function. It is well known that in finite dimensional spaces every continuous piecewise-linear function admits a max-min representation in terms of its linear functions. An explicit representation of an ordered median function in max-min form is given by the authors and will appear in a forthcoming issue of this journal. Based on this representation, we give a topological classification of ordered median functions through their simplicial complex of ascent (resp. descent) cones.     

Piecewise-Linear Approximations of Multidimensional Functions

We develop explicit, piecewise-linear formulations of functions f(x):ℝ ⁿ ↦ℝ, n≤3, that are defined on an orthogonal grid of vertex points. If mixed-integer linear optimization problems (MILPs) involving multidimensional piecewise-linear functions can be easily and efficiently solved to global optimality, then non-analytic functions can be used as an objective or constraint function for large optimization problems. Linear interpolation between fixed gridpoints can also be used to approximate generic, nonlinear functions, allowing us to approximately solve problems using mixed-integer linear optimization methods. Toward this end, we develop two different explicit formulations of piecewise-linear functions and discuss the consequences of integrating the formulations into an optimization problem.     

A penalty continuation method for the ∓∞ solution of overdetermined linear systems

A new algorithm for the ∓_∞ solution of overdetermined linear systems is given. The algorithm is based on the application of quadratic penalty functions to a primal linear programming formulation of the ∓_∞ problem. The minimizers of the quadratic penalty function generate piecewise-linear non-interior paths to the set of ∓_∞ solutions. It is shown that the entire set of ∓_∞ solutions is obtained from the paths for sufficiently small values of a scalar parameter. This leads to a finite penalty/continuation algorithm for ∓_∞ problems. The algorithm is implemented and extensively tested using random and function approximation problems. Comparisons with the Barrodale-Phillips simplex based algorithm and the more recent predictor-corrector primal-dual interior point algorithm are given. The results indicate that the new algorithm shows a promising performance on random (non-function approximation) problems.     

Integrated circuit generating 3- and 5-scroll attractors

This paper introduces the experimental realization of the first integrated circuit of a multi-scroll continuous chaotic oscillator showing 3- and 5-scroll attractors. It is based on a variant of the Chua’s system. The most relevant issue is the implementation of a saw-tooth-like nonlinear function, which is designed by using floating gate MOS (FGMOS) transistors. Therefore, the realization of a voltage-to-current nonlinear cell by a piecewise-linear approach allows us to have only two external control inputs instead of numerous external voltage references, as usually done in current circuit realizations. Experimental results of the proposed integrated multi-scroll oscillator along with its corner analysis are provided.     

Locally linearized fractional step methods for nonlinear parabolic problems

This work deals with the efficient numerical solution of a class of nonlinear time-dependent reaction-diffusion equations. Via the method of lines approach, we first perform the spatial discretization of the original problem by applying a mimetic finite difference scheme. The system of ordinary differential equations arising from that process is then integrated in time with a linearly implicit fractional step method. For that purpose, we locally decompose the discrete nonlinear diffusion operator using suitable Taylor expansions and a domain decomposition splitting technique. The totally discrete scheme considers implicit time integrations for the linear terms while explicitly handling the nonlinear ones. As a result, the original problem is reduced to the solution of several linear systems per time step which can be trivially decomposed into a set of uncoupled parallelizable linear subsystems. The convergence of the proposed methods is illustrated by numerical experiments.     

Models and solution techniques for production planning problems with increasing byproducts

We consider a production planning problem where the production process creates a mixture of desirable products and undesirable byproducts. In this production process, at any point in time the fraction of the mixture that is an undesirable byproduct increases monotonically as a function of the cumulative mixture production up to that time. The mathematical formulation of this continuous-time problem is nonconvex. We present a discrete-time mixed-integer nonlinear programming (MINLP) formulation that exploits the increasing nature of the byproduct ratio function. We demonstrate that this new formulation is more accurate than a previously proposed MINLP formulation. We describe three different mixed-integer linear programming (MILP) approximation and relaxation models of this nonconvex MINLP, and we derive modifications that strengthen the linear programming relaxations of these models. We also introduce nonlinear programming formulations to choose piecewise-linear approximations and relaxations of multiple functions that share the same domain and use the same set of break points in the domain. We conclude with computational experiments that demonstrate that the proposed formulation is more accurate than the previous formulation, and that the strengthened MILP approximation and relaxation models can be used to obtain provably near-optimal solutions for large instances of this nonconvex MINLP. Experiments also illustrate the quality of the piecewise-linear approximations produced by our nonlinear programming formulations.     

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.     

An efficient nonlinear iteration scheme for nonlinear parabolic-hyperbolic system

A nonlinear iteration method named the Picard-Newton iteration is studied for a two-dimensional nonlinear coupled parabolic-hyperbolic system. It serves as an efficient method to solve a nonlinear discrete scheme with second spatial and temporal accuracy. The nonlinear iteration scheme is constructed with a linearization-discretization approach through discretizing the linearized systems of the original nonlinear partial differential equations. It can be viewed as an improved Picard iteration, and can accelerate convergence over the standard Picard iteration. Moreover, the discretization with second-order accuracy in both spatial and temporal variants is introduced to get the Picard-Newton iteration scheme. By using the energy estimate and inductive hypothesis reasoning, the difficulties arising from the nonlinearity and the coupling of different equation types are overcome. It follows that the rigorous theoretical analysis on the approximation of the solution of the Picard-Newton iteration scheme to the solution of the original continuous problem is obtained, which is different from the traditional error estimate that usually estimates the error between the solution of the nonlinear discrete scheme and the solution of the original problem. Moreover, such approximation is independent of the iteration number. Numerical experiments verify the theoretical result, and show that the Picard-Newton iteration scheme with second-order spatial and temporal accuracy is more accurate and efficient than that of first-order temporal accuracy.     

A simplex algorithm for piecewise-linear programming III: Computational analysis and applications

The first two parts of this paper have developed a simplex algorithm for minimizing convex separable piecewise-linear functions subject to linear constraints. This concluding part argues that a direct piecewiselinear simplex implementation has inherent advantages over an indirect approach that relies on transformation to a linear program. The advantages are shown to be implicit in relationships between the linear and piecewise-linear algorithms, and to be independent of many details of implementation. Two sets of computational results serve to illustarate these arguments; the piecewise-linear simplex algorithm is observed to run 2–6 times faster than a comparable linear algorithm, not including any additional expense that might be incurred in setting up the equivalent linear program. Further support for the practical value of a good piecewise-linear programming algorithm is provided by a survey of many varied applications.This research has been supported in part by the National Science Foundation under grant DMS-8217261.     

A simplex algorithm for piecewise-linear programming II: Finiteness,feasibility and degeneracy

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. Part I of this paper has developed a general and direct simplex algorithm for piecewise-linear programming, under convenient assumptions that guarantee a finite number of basic solutions, existence of basic feasible solutions, and nondegeneracy of all such solutions. Part II now shows how these assumptions can be weakened so that they pose no obstacle to effective use of the piecewise-linear simplex algorithm. The theory of piecewise-linear programming is thereby extended, and numerous features of linear programming are generalized or are seen in a new light. An analysis of the algorithm's computational requirements and a survey of applications will be presented in Part III.This research has been supported in part by the National Science Foundation under grant DMS-8217261.     

Interval solution of nonlinear equations using linear programming

A new computational test is proposed for nonexistence of a solution to a system of nonlinear equations in a convex polyhedral regionX. The basic idea proposed here is to formulate a linear programming problem whose feasible region contains all solutions inX. Therefore, if the feasible region is empty (which can be easily checked by Phase I of the simplex method), then the system of nonlinear equations has no solution inX. The linear programming problem is formulated by surrounding the component nonlinear functions by rectangles using interval extensions. This test is much more powerful than the conventional test if the system of nonlinear equations consists of many linear terms and a relatively small number of nonlinear terms. By introducing the proposed test to interval analysis, all solutions of nonlinear equations can be found very efficently. This work was partially supported by the Japanese Ministry of Education.     

Optimal objective function approximation for separable convex quadratic programming

We present an optimal piecewise-linear approximation method for the objective function of separable convex quadratic programs. The method provides guidelines on how many grid points to use and how to position them for a piecewise-linear approximation if the error induced by the approximation is to be bounded a priori.Corresponding author.     

Relaxation approximation to bed-load sediment transport

In this work we propose and apply a numerical method based on finite volume relaxation approximation for computing the bed-load sediment transport in shallow water flows, in one and two space dimensions. The water flow is modeled by the well-known nonlinear shallow water equations which are coupled with a bed updating equation. Using a relaxation approximation, the nonlinear set of equations (and for two different formulations) is transformed to a semilinear diagonalizable problem with linear characteristic variables. A second order MUSCL-TVD method is used for the advection stage while an implicit–explicit Runge–Kutta scheme solves the relaxation stage. The main advantages of this approach are that neither Riemann problem solvers nor nonlinear iterations are required during the solution process. For the two different formulations, the applicability and effectiveness of the presented scheme is verified by comparing numerical results obtained for several benchmark test problems.     

Feature extraction algorithms for constrained global optimization I. Mathematical foundation

Nonconvex mixed integer nonlinear programming problems arise quite frequently in engineering decision problems, in general, and in chemical process design synthesis and process scheduling applications, in particular. These problems are characterized by high dimensionality and multiple local optimal solutions. In this work, a novel approach is developed for determining the global optimum in nonlinear continuous and discrete domains. The mathematical foundations of the feature extraction algorithm are presented and the properties of the algorithm discussed in detail. The algorithm uses a partition and search strategy in which the problem domain is successively partitioned and a statistical approximation approach is used to characterize the objective function values and the constraint feasibility over a partition. Specifically, the general joint distribution function representing the objective function values is relaxed to a separable form and approximated using an expansion in terms of Bernstein functions. The coefficients of the expansion are determined by solving a small linear program. Feasibility is established by computing upper and lower bounds for the inequality constraint functions, while equality constraints are explicitly or numerically eliminated. Estimates of the volume averaged values of objective function and constraint feasibility are used to select efficient partitions for further investigation. These are refined successively so as to focus the search on the most promising decision regions. An alternative, constant resolution partitioning strategy is also developed using a suitably modified genetic search algorithm. Illustrative examples are used to demonstrate the key computational features of the method.     

Unconstrained 0–1 nonlinear programming: A nondifferentiable approach

The purpose of this paper is to give new formulations for the unconstrained 0–1 nonlinear problem. The unconstrained 0–1 nonlinear problem is reduced to nonlinear continuous problems where the objective functions are piecewise linear. In the first formulation, the objective function is a difference of two convex functions while the other formulations lead to concave problems. It is shown that the concave problems we obtain have fewer integer local minima than has the classical concave formulation of the 0–1 unconstrained 0–1 nonlinear problem.     

Monotone multigrid methods for elliptic variational inequalities II

Summary. We derive globally convergent multigrid methods for discrete elliptic variational inequalities of the second kind as obtained from the approximation of related continuous problems by piecewise linear finite elements. The coarse grid corrections are computed from certain obstacle problems. The actual constraints are fixed by the preceding nonlinear fine grid smoothing. This new approach allows the implementation as a classical V-cycle and preserves the usual multigrid efficiency. We give estimates for the asymptotic convergence rates. The numerical results indicate a significant improvement as compared with previous multigrid approaches. Received March 26, 1994 / Revised version received September 22, 1994     

A method for generating a well-distributed Pareto set in nonlinear multiobjective optimization

A method is presented for generating a well-distributed Pareto set in nonlinear multiobjective optimization. The approach shares conceptual similarity with the Physical Programming-based method, the Normal-Boundary Intersection and the Normal Constraint methods, in its systematic approach investigating the objective space in order to obtain a well-distributed Pareto set. The proposed approach is based on the generalization of the class functions which allows the orientation of the search domain to be conducted in the objective space. It is shown that the proposed modification allows the method to generate an even representation of the entire Pareto surface. The generation is performed for both convex and nonconvex Pareto frontiers. A simple algorithm has been proposed to remove local Pareto solutions. The suggested approach has been verified by several test cases, including the generation of both convex and concave Pareto frontiers.