Refine
Document Type
- Article (2)
Language
- English (2)
Has Fulltext
- yes (2)
Keywords
- Software (1)
- Theoretical Computer Science (1)
Subgradient methods (SM) have long been the preferred way to solve the large-scale Nondifferentiable Optimization problems arising from the solution of Lagrangian Duals (LD) of Integer Programs (IP). Although other methods can have better convergence rate in practice, SM have certain advantages that may make them competitive under the right conditions. Furthermore, SMhave significantly progressed in recent years, and new versions have been proposed with better theoretical and practical performances in some applications.We computationally evaluate a large class of SM in order to assess if these improvements carry over to the IP setting. For this we build a unified scheme that covers many of the SMproposed in the literature, comprised some often overlooked features like projection and dynamic generation of variables. We fine-tune the many algorithmic parameters of the resulting large class of SM, and we test them on two different LDs of the Fixed-Charge Multicommodity Capacitated Network Design problem, in order to assess the impact of the characteristics of the problem on the optimal algorithmic choices. Our results show that, if extensive tuning is performed, SM can be competitive with more sophisticated approaches when the tolerance required for solution is not too tight, which is the case when solving LDs of IPs.
In this paper, we address the problem of approximating and over/under-estimating
univariate functions with piecewise linear (PWL) functions with the minimum num-
ber of linear segments given a bound on the allowed pointwise approximation error.
Through a new geometric approach and building on the work of Ngueveu (Eur J Oper
Res 275:1058–1071, 2019), we develop new algorithms that can solve the problem in
quasi-logarithmic time on a very broad class of error types. Such algorithms find many
applications, mostly related to solving certain classes of (mixed-integer) nonlinear and
nonconvex programming (MINLP) problems by mixed-integer linear programming
(MILP) techniques. An efficient implementation of our algorithms is available as a
Julia package. Benchmarks are also provided to showcase how our method outper-
forms the state-of-the-art for this problem. Finally, we show how our algorithms can
be used to efficiently solve certain classes of MINLP problems through a case study
on multicommodity network design problems with congestion.