The Lagrangian dual of an integer program can be formulated as a min-max problem where the objective function is convex, piecewise affine and, hence, nonsmooth. It is usually tackled by means of subgradient algorithms, or multiplier adjustment techniques, or even more sophisticated nonsmooth optimization methods such as bundle-type algorithms. Recently a new approach to solving unconstrained convex finite min-max problems has been proposed, which has the nice property of working almost independently of the exact evaluation of the objective function at every iterate-point. In the paper we adapt the method, which is of the descent type, to the solution of the Lagrangian dual. Since the Lagrangian relaxation need not be solved exactly, the approach appears suitable whenever the Lagrangian dual must be solved many times (e.g., to improve the bound at each node of a branch-and-bound tree), and effective heuristic algorithms at low computational cost are available for solving the Lagrangian relaxation. We present an application to the Generalized Assignment Problem (GAP) and discuss the results of our numerical experimentation on a set of standard test problems.

On solving the Lagrangian dual of integer programs via an incremental approach

GAUDIOSO, Manlio;GIALLOMBARDO, Giovanni;Miglionico G.
2009

Abstract

The Lagrangian dual of an integer program can be formulated as a min-max problem where the objective function is convex, piecewise affine and, hence, nonsmooth. It is usually tackled by means of subgradient algorithms, or multiplier adjustment techniques, or even more sophisticated nonsmooth optimization methods such as bundle-type algorithms. Recently a new approach to solving unconstrained convex finite min-max problems has been proposed, which has the nice property of working almost independently of the exact evaluation of the objective function at every iterate-point. In the paper we adapt the method, which is of the descent type, to the solution of the Lagrangian dual. Since the Lagrangian relaxation need not be solved exactly, the approach appears suitable whenever the Lagrangian dual must be solved many times (e.g., to improve the bound at each node of a branch-and-bound tree), and effective heuristic algorithms at low computational cost are available for solving the Lagrangian relaxation. We present an application to the Generalized Assignment Problem (GAP) and discuss the results of our numerical experimentation on a set of standard test problems.
Incremental algorithms; Convex minimization; Finite min-max
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/139755
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? 16
social impact