Topics in convex and mixed binary linear optimization

Abstract

This thesis concerns theory, algorithms, and applications for two problem classes within the realm of mathematical optimization; convex optimization and mixed binary linear optimization. To the thesis is appended five papers containing its main contributions. In the first paper a subgradient optimization method is applied to the Lagrangian dual of a general convex and (possibly) nonsmooth optimization problem. The classic dual subgradient method produces primal solutions that are, however, neither optimal nor feasible. Yet, convergence to the set of optimal primal solutions can be obtained by constructing a class of ergodic sequences of the Lagrangian subproblemsolutions.We generalize previous convergence results for such ergodic sequences by proposing a new set of rules for choosing the convexity weights defining the sequences. Numerical results indicate that by applying our new set of rules primal feasible solutions of higher quality than those created by the previously developed rules are achieved. The second paper analyzes the properties of a subgradient method when applied to the Lagrangian dual of an infeasible convex program. The primal-dual pair of programs corresponding to an associated homogeneous dual function is shown to be in turn associated with a saddle-point problem, in which the primal part amounts to finding a solution such that the Euclidean norm of the infeasibility in the relaxed constraints is minimized. Convergence results for a conditional dual subgradient optimization method applied to the Lagrangian dual problem is presented. The sequence of ergodic primal iterates is shown to converge to the set of solutions to the primal part of the associated saddle-point problem. The third paper applies a dual subgradientmethod to a general mixed binary linear program (MBLP). The resulting sequence of primal ergodic iterates is shown to converge to the set of solutions to a convexified version of the original MBLP, and three procedures for utilizing the primal ergodic iterates for constructing feasible solutions to the MBLP are proposed: a Lagrangian heuristic, the construction of a so-called core problem, and a framework for utilizing the ergodic primal iterates within a branch-and-bound algorithm. Numerical results for samples of uncapacitated facility location problems and set covering problems indicate that the proposed procedures are practically useful for solving structured MBLPs. In the fourth paper, the preventive maintenance scheduling problem with interval costs is studied. This problem considers the scheduling of maintenance of the components in a multicomponent system with the objective to minimize the sum of the set-up and interval costs for the system over a finite time period. The problem is shown to be NP-hard, and an MBLP model is introduced and utilized in three case studies from the railway, aircraft, and wind power industries. In the fifth paper an MBLP model for the optimal scheduling of tamping operations on ballasted rail tracks is introduced. The objective is to minimize the total maintenance costs while maintaining an acceptable condition on the ballasted tracks. The model is thoroughly analyzed and the scheduling problem considered is shown to be NP-hard. A computational study shows that the total cost for maintenance can be reduced by up to 10% as compared with the best policy investigated.