# Learning Individualized Hyperparameter Settings
## 3 Algorithms and Problems
### Lagrangian Heuristic and the GAP  
Lagrangian heuristics, as the name suggests, are rooted in Lagrangian relaxation, a largely used decomposition technique providing bounds to the optimal solution values of combinatorial optimization problems (COP) but also usable as a basis for effective heuristic approaches [3].  
The general structure of a Lagrangian code, whose pseudocode is provided in Algorithm 1, is aimed at finding the optimal, or at least a _good_ feasible solution \(\mathbf{x}_{UB}\) of a problem that can be modeled as \(\min\{c^{T}x:\ Ax\geq b,\ Cx\geq d,\ x\in\mathbb{Z}_{+}^{n}\}\), where the constraints \(Ax\geq b\) are \"hard\" and the constraints \(Cx\geq d\) are \"easy\". The method requires to remove the hard constraints and penalize them in the objective function by means of a penalty vector \(\boldsymbol{\lambda}\) of _Lagrangian multipliers_, then to decompose the problem into a master problem and a subproblem. The subproblem \(\text{LR}(\boldsymbol{\lambda})\), \(\min\{c^{T}x+\lambda^{T}\big{(}b-Ax\big{)}:\ Cx\geq d,\ x\in\mathbb{Z}_{+}^{n }\}\), provides a (lower, in case of minimization) bound as a function of \(\boldsymbol{\lambda}\). The solution of the subproblem can be infeasible for the whole problem, but a _fixing_ heuristic (which is a driven heuristic, hence the denotation of metaheuristic for the whole procedure) can turn it into a feasible solution \(\mathbf{x}^{\mathbf{h}}\). The last element to mention is the penalty update procedure that hopefully drives the process toward better and better lower and upper bounds; this can be done in different ways, the most common being a _subgradient optimization_[29].  
In the pseudocode of Algorithm 1, step 4 solves the subproblem, obtaining a solution \(\mathbf{x}^{\lambda}\) which is possibly infeasible for the whole problem but whose cost \(z_{i}ambda\) is a lower bound to the problem's optimal cost. Step 6 checks its feasibility and returns a vector \(\mathbf{s}\) of subgradients, which is null in the case of a feasible solution. Step 7 is the optimality check and step 8 is the call to the fixing heuristic. Finally steps 10-11 implement the penalty update heuristic and step 12 implements [PERSON]'s rule [30] that ensures the convergence of the series of penalty vectors.  
The specific problem we applied the Lagrangian heuristic to is the GAP. This problem asks to uniquely assign \(n\) clients, index set \(J=\{1,\ldots,n\}\), to \(m\) servers, index set \(I=\{1,\ldots,m\}\), so that a cost function gets minimized while satisfying capacity constraints. Assignment costs are specified by a cost matrix \(\mathbf{C}=[c_{ij}]_{m}^{n}\), server capacities by a vector \(\mathbf{Q}=[Q_{i}]_{m}\) and client requests to servers by a request matrix \(\mathbf{q}=[q_{ij}]_{m}^{n}\). Partial assignments are not allowed, thus the mathematical formulation of the GAP is as follows.  
\[z_{GAP}=\mathbf{min}\sum_{i\in I}\sum_{j\in J}c_{ij}x_{ij} \tag{1}\] \[\mathbf{subject\ to}\sum_{j\in J}q_{ij}x_{ij}\leq Q_{i} i\in I\] (2) \[\sum_{i\in I}x_{ij}=1 j\in J\] (3) \[x_{ij}\in\{0,1\} i\in I,j\in J \tag{4}\]  
It is possible to relax in a Lagrangian fashion either constraints (2) or constraints (3) (or both), thus obtaining two (three) different subproblems to solve at step 4.  
Algorithm 1 when applied to the GAP has six parameters to set, which are:  
* _alphainit_: initial \(\alpha\) value for penalty updates;
* _alphastep_: step reduction (step 12);
* _minalpha_: minimum step length value (step 12);
* _inneriter_: internal iteration number before changing _alpha_ (step 12);
* _maxiter_: maximum number of iterations (terminating condition, step 13);
* _algotype_: which subproblem is used (step 4) (see [2] for details).  
The GAP is a very well known and studied problem, and several benchmark instance sets exist. The online collection from which we downloaded our test set was the GAPLIB instance library [31], which contains most instances from the literature.