Bilevel parameter optimization for nonlocal image denoising models

Abstract: We propose a bilevel optimization approach for the determination of parameters in nonlocal image denoising. We consider both spatial weights in front of the fidelity term, as well as weights within the kernel of the nonlocal operator. In both cases we investigate the differentiability of the solution operator in function spaces and derive a first order optimality system that characterizes local minima. For the numerical solution of the problems, we propose a second-order optimization algorithm in combination with a finite element discretization of the nonlocal denoising models and a computational strategy for the solution of the resulting dense linear systems. Several experiments are run in order to show the suitability of our approach.

Leer

Multi-weight graph partitioning problem

Abstract: In this work a multi-weight graph partitioning problem is introduced. This problem consists in partitioning an undirected graph in a fixed number of subgraphs such that multiple node weight constraints over each partition are satisfied and the total distance between nodes in the same subgraph induced by the partition is minimized. This problem generalizes several graph partitioning problems like $k$-way equipartition, and bisection. It arises as a subproblem of an integrated vehicle and pollster problem from a real world application. Two Integer Programming formulations are provided and several families of valid inequalities associated to the respective polyhedra are proved. An exact algorithm based on branch and bound and cutting planes is proposed and it is tested on real-world instances.

Leer

University timetabling with heterogeneous lectures and compactness constraints

Abstract: A variant of the Curriculum-Based Course Timetabling (CB-CTT)Problem arising from a practical application is studied. This variant includes twokey features: lectures with heterogeneous durations and a compactness soft con-straint for curricula. Each course lecture has a specific duration, indicating a num-ber of consecutive time periods required for the lecture to take place. Moreover,each day in the schedule of any curriculum should not exceed a prescribed max-imum length, where the length of a working day is defined as the time elapsedbetween the start of the first lecture until the end of the last lecture on that day.Finally, some soft constraints of the standard CB-CTT, such as minimum numberof working days or room capacity, are considered as hard constraints in the variantstudied here.An integer programming model and a two-stage solution algorithm are pro-posed for this problem. At first, a reduced model obtained by discarding schedulecompactness constraints is solved to optimality. The solution is then extended toan initial feasible solution of the original model, which is then improved using astandard branch-and-cut procedure. Three classes of symmetry-breaking inequal-ities are described for this integer program and tested on real-world instances.

Leer

Integrated Vehicle and Pollster Routing

Abstract: The National Statistics Bureau of Ecuador carries out monthly polls to monitor the evolution of an economic indicator called “Consumer Price Index”, which measures the consumer prices of basic commodities. A set of stores is selected to apply these polls. A set of vehicles transport pollsters from the headquarters of the bureau to the stores to perform this activity. Moreover, pollsters move between stores using pedestrian paths or using a vehicle to shorten the travel time between far away stores. This paper introduces an integer programming model for the integrated task of scheduling visits of pollsters to selected stores, as well as routing the vehicle fleet used to transport them. Results on the computational complexity of the aforementioned problem, a three-phase algorithm, and computational experience based on real-world instances are provided.

Leer

Primal-dual proximal splitting and generalized conjugation in non-smooth non-convex optimization

Abstract: We demonstrate that difficult non-convex non-smooth optimization problems, such as Nash equilibrium problems and anisotropic as well as isotropic Potts segmentation model, can be written in terms of generalized conjugates of convex functionals. These, in turn, can be formulated as saddle-point problems involving convex non-smooth functionals and a general smooth but non-bilinear coupling term. We then show through detailed convergence analysis that a conceptually straightforward extension of the primal--dual proximal splitting method of Chambolle and Pock is applicable to the solution of such problems. Under sufficient local strong convexity assumptions of the functionals -- but still with a non-bilinear coupling term -- we even demonstrate local linear convergence of the method. We illustrate these theoretical results numerically on the aforementioned example problems.

Leer

Block-proximal methods with spatially adapted acceleration

Abstract: We study and develop (stochastic) primal--dual block-coordinate descent methods for convex problems based on the method due to Chambolle and Pock. Our methods have known convergence rates for the iterates and the ergodic gap: O(1/N2) if each block is strongly convex, O(1/N) if no convexity is present, and more generally a mixed rate O(1/N2)+O(1/N) for strongly convex blocks, if only some blocks are strongly convex. Additional novelties of our methods include blockwise-adapted step lengths and acceleration, as well as the ability to update both the primal and dual variables randomly in blocks under a very light compatibility condition. In other words, these variants of our methods are doubly-stochastic. We test the proposed methods on various image processing problems, where we employ pixelwise-adapted acceleration.

Leer