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
Dynamic programming, branch-and-bound, and constraint programming are the standard solution principles for finding optimal solutions to machine scheduling problems. We propose a new hybrid optimization framework that integrates all three methodologies. The hybrid framework leads to powerful solution procedures. We demonstrate our approach through the optimal solution of the single-machine total weighted completion time scheduling … Read more
I have been working for quite awhile with the treatment of experimental results in chemical thermodynamics. I have tried to organize my archives and make them available for others. There are several experimental datasets in computer readable format and I hope that they can be used as useful benchmarks for data fitting and nonlinear optimization. … Read more
New observations are made about two lower bound schemes for single-machine min-sum scheduling problems. We find that the strongest bound of those provided by transportation problem relaxations can be computed by solving a linear program. We show the equivalence of this strongest bound and the bound provided by the LP relaxation of the time-indexed integer … Read more
In [1] several conditions are described which imply the closedness of linear images of convex sets. Here we combine two such theorems into a common generalization. We give a proof of the general theorem which is simpler than the proof obtained by combining the proofs of the two theorems. The paper is almost self-contained as … Read more
The Primal-Dual Second Order Corrector (PDSOC) algorithm that we investigate computes on each iteration a corrector direction in addition to the direction of the standard primal-dual path-following interior point method (Kojima et al., 1989) for Linear Programming (LP), in an attempt to improve performance. The corrector is multiplied by the square of the stepsize in … Read more
In this report, we propose a new partitioned variable metric method for minimization of nonsmooth partially separable functions. After a short introduction, the complete algorithm is introduced and some implementation details are given. We prove that this algorithm is globally convergent under standard mild assumptions. Computational experiments given confirm efficiency and robustness of the new … Read more
In this paper we analyze the rate of local convergence of the Newton primal-dual interior-point method when the iterates are kept strictly feasible with respect to the inequality constraints. It is shown under the classical conditions that the rate is q-quadratic when the functions associated to the inequality constraints define a locally concave feasible region. … Read more
We propose a perturbed gradient algorithm with stochastic noises to solve a general class of optimization problems. We provide a convergence proof for this algorithm, under classical assumptions on the descent direction, and new assumptions on the stochastic noises. Instead of requiring the stochastic noises to correspond to martingale increments, we only require these noises … Read more
In this paper, we study wavelength assignment problems in multi-fiber WDM networks. We focus on the special case that all lightpaths have at most two links. This in particular holds in case the network topology is a star. As the links incident to a specific node in a meshed topology form a star subnetwork, results … Read more