isotonic regression – Optimization Online

A dynamic programming approach to segmented isotonic regression

Published: 2020/12/08

Data-Mining, Dynamic Programming, Energy cardinality-constrained shortest path problem, consumers' price-response, data clustering, inverse problems, isotonic regression, segmented regression

This paper proposes a polynomial-time algorithm to construct the monotone stepwise curve that minimizes the sum of squared errors with respect to a given cloud of data points. The fitted curve is also constrained on the maximum number of steps it can be composed of and on the minimum step length. Our algorithm relies on … Read more

Dual constrained single machine sequencing to minimize total weighted completion time

Published: 2005/03/30, Updated: 2006/08/10

Yunpeng Pan

Leyuan Shi

Scheduling Branch-and-Bound, isotonic regression, scheduling, timetabling, weighted completion time

We study a single-machine sequencing problem with both release dates and deadlines to minimize the total weighted completion time. We propose a branch-and-bound algorithm for this problem. The algorithm exploits an effective lower bound and a dynamic programming dominance technique. As a byproduct of the lower bound, we have developed a new algorithm for the … Read more