This article presents a new approach for constructing convex enclosures of reachable sets of parametric ordinary differential equations (ODEs), for use in deterministic methods for global dynamic optimization. In our new approach, we modify an established ODE relaxation framework by Scott and Barton (2013), using kinematic intuition to replace certain discontinuous transitions between discrete modes with tighter, smoother transitions, and ultimately producing tighter, smoother relaxations of the original ODE solution that are more amenable to integration by off-the-shelf numerical ODE solvers. We refer to our new relaxation approach as “kinematic smoothing”. Our new ODE relaxations are straightforward to construct automatically based on established tools, and we present several numerical examples based on a proof-of-concept implementation in Julia.

In this article, a new integer linear programming (ILP) formulation is presented for nonogram/crucipixel/paint-by-number puzzles, which involve coloring cells in a grid according to provided clues about how many cells in each row and column ought to be colored. Compared to prior ILP formulations, this new formulation involves far fewer constraints and decision variables. This new formulation was implemented in the modeling language GAMS; this implementation was found in many instances to approximately halve the CPU time required to identify a solution compared to prior ILP-based approaches. Multicolored nonograms are also permitted in this formulation. Counterintuitively, the new formulation does not make direct reference to cell colors at all, unlike typical by-hand approaches for solving simple instances. A new method is also presented to check the uniqueness of a nonogram solution, again without direct reference to cell colors, by employing a result by Besicovitch concerning integer linear independence.

Bundle methods for nonsmooth optimization and semismooth Newton methods for nonsmooth equation solving both require computation of elements of the (Clarke) generalized Jacobian, which provides slope information for locally Lipschitz continuous functions. Since the generalized Jacobian does not obey sharp calculus rules, this computation can be difficult. In this article, methods are developed for evaluating generalized Jacobian elements for a nonsmooth function that is expressed as a finite composition of known elemental piecewise differentiable functions. In principle, these elemental functions can include any piecewise differentiable function whose analytical directional derivatives are known. The methods are fully automatable, and are shown to be computationally tractable relative to the cost of a function evaluation. An implementation developed in C++ is discussed, and the methods are applied to several example problems for illustration.