# On the Use of Biased-Randomized Algorithms for Solving Non-Smooth Optimization Problems
## 3 Basic Concepts on Biased-Randomized Algorithms  
Pure greedy constructive heuristics are algorithms that iteratively build a solution by selecting the next movement from a list of candidates. Such candidates have been sorted previously according to some criteria, such as costs, savings, profits, etc. These heuristics typically select the \"most promising\" (in the short run) candidate from the list. Since they follow a constructive logic, a good final solution is expected by the end of the procedure. Nevertheless, these algorithms are deterministic, i.e., the solution is always the same every time the heuristic is executed. This means that the exploration process is poor, which prevents the algorithm from finding better solutions unless more complex searching structures--i.e., local searches and perturbation movements--are considered by investing more computing time. Examples of such heuristics are the well-known savings heuristic for the VRP [40],  
Figure 2: Example of a non-convex and non-smooth piecewise objective function. the nearest neighbor criterion for the traveling salesman problem [41], or the shortest processing time dispatching rule for some scheduling problems [42]. As described in [PERSON] et al. [43], using a skewed (nonuniform) probability distribution to introduce a biased-randomization behavior into the process that selects the candidates from the sorted list is an efficient way of generating better solutions. The idea is to assign a weighted probability to each candidate in the list, in such a way that the more promising candidates--those at the top of the list--receive a higher probability of being selected than those below them. This randomization process leads to the generation of slightly different solutions every time the algorithm is executed. Hence, multiple executions of a BRA--either completed in a sequential or in a parallel mode--will yield a set of alternative solutions, all of them based on the logic behind the heuristic. Since we are executing many biased-random variations of the constructive procedure defined by the heuristic, chances are that some of these \"near-greedy\" heuristics lead to solutions that outperform the one generated by the greedy heuristic [10]. Algorithm 1 shows a pseudo-code description of a basic BRA that performs in a sequential way. ```
1 bestSol \(\leftarrow\) execute the deterministic (greedy) heuristic
2 whilemore time is alloweddo
3 seed \(\leftarrow\) select a seed for the pseudo-random number generator
4 rng \(\leftarrow\) start a pseudo-random number generator with seed
5 dist \(\leftarrow\) select a skewed probability distribution (and its parameters)
6 newSol \(\leftarrow\) start an empty solution
7 list \(\leftarrow\) create the list of 'building blocks' for the solution
8 sortedList \(\leftarrow\) sort the list according to the heuristic logic
9 whilesortedList is not emptydo
10 nextElement \(\leftarrow\) use dist and rng to select and extract the next block from sortedList
11 ifnextElement can be added without losing feasibilitythen
12 newSol \(\leftarrow\) add nextElement to the incumbent solution
13
14 end if
15
16 end if
17
18 end if
19 ifnewSol is better than bestSol then
20 bestSol \(\leftarrow\) newSol
21
22 end if
23 return bestSol
```  
**Algorithm 1**Biased-Randomized Algorithm (BRA; basic sequential version). Notice that, by using this approach, a broad exploration of the solution space is carried out, which might be specially beneficial in the case of highly irregular objective functions as the ones characterizing non-smooth OPs. The proposed methodology can be seen as a natural extension of the basic greedy randomized adaptive search procedure (GRASP) [44], as analyzed in [PERSON] et al. [10]. Instead of employing empirical probability distributions--which require time-consuming parameter fine tuning and thus might slow down computations--a theoretical probability distribution such as the geometric distribution or the decreasing triangular distribution can be used.