Abstract In 1998, the paper Sergeyev (Math Program 81(1):127–146, 1998) has been published where a smooth piece-wise quadratic minorant has been proposed for multiextremal functions f ( x ) with the first derivative $$f'(x)$$ f ′ ( x ) satisfying the Lipschitz condition with a constant L , i.e., $$f'(x)$$ f ′ ( x ) cannot increase with the slope higher than L and decrease with the slope smaller than $$-L$$ - L . This minorant has been successfully applied in several efficient global optimization algorithms and used in engineering applications. In the present paper, it is supposed that the first derivative $$f'(x)$$ f ′ ( x ) cannot increase with the slope higher than a constant $$\beta $$ β and decrease with the slope smaller than $$\alpha $$ α . The interval $$[\alpha ,\beta ]$$ [ α , β ] is called the Lipschitz interval (clearly, in this case the Lipschitz constant $$L = \max \{|\alpha |, |\beta | \}$$ L = max { | α | , | β | } ). For this class of functions, smooth piece-wise estimators (minorants and majorants) have been proposed and applied in global optimization. Both theoretically and experimentally (on 200 randomly generated test problems) it has been shown that in cases where $$ |\alpha | \ne |\beta |$$ | α | ≠ | β | the new estimators can give a significant improvement w.r.t. those proposed in Sergeyev (Math Program 81(1):127–146, 1998), for example, in the framework of branch-and-bound global optimization methods.

Abstract In this paper, we propose a deterministic approach for finding the first zero-crossing point of a differentiable, possibly multiextremal univariate function, that combines a Branch-and-Bound framework with piece-wise linear under- and overestimators derived from Lipschitz intervals. Two algorithms are presented: a baseline algorithm and a version enhanced with interval reduction techniques. Theoretical guarantees of correctness and finite termination of the introduced methods are established. Extensive numerical experiments on 27 benchmark problems demonstrate that the proposed methods outperform the existing interval Branch-and-Bound approach both in terms of running time and accuracy.

Summary In the paper, we compute some lower bounds on time of parallel solving of the subset sum problem on a big number of processors by several versions of dynamic programming algorithm Balsub proposed before by Pisinger. Based on these lower bounds, we propose a version of Balsub which could be possibly effectively parallelized.