optimization-algorithms 0.0.1
It is a Python library that contains useful algorithms for several complex problems such as partitioning, floor planning, scheduling.
Requires Python: >=3.7


![Logo](https://github.com/alqmase/optimization-algorithms/blob/main/img/home/logo.png) 


# Optimization-algorithms

Optimization-algorithms is a Python library that contains useful algorithms for several complex problems such as partitioning, floor planning, scheduling. This library will provide many implementations for many optimization algorithms. This library is organized in a problem-wise structure. For example, there are many problems such as graph partitioning problem, scheduling problem, etc. For each problem, there are many algorithms to solve it. For each algorithm, there are many possible approaches to implement it. 

## Q1: what is the goal of this library?

The goal is to provide a python library: 
* **_for the purpose of_** optimization algorithms 
* **_with respect to_** consistency and simplicity 
* **_from the viewpoint of_** researchers, students, and industries 
* **_in the context of_** VLSI circuit design, parallel computing, cloud computing, and artificial intelligent.

## Q2: what are the motivation of building this library?
During my research in partitioning problem, I found that there is a lack of library where the researchers can easily compare their algorithms with others. I found that each implementation has its own input style and output style which means more afford is spent for understanding the codes and adapting the input. We suggest this library where the optimization algorithms can be packaged with consistency in mind.


## Q3: who are the users?
1.	Students
2.	Researchers
3.	Industries


## Q4: what are the features of this library?
* **_Consistency:_** we are striving to ensure consistency. 
* **_Simplicity:_** we are striving to ensure simplicity.
* **_Source for learning, and teaching:_** we are striving to make this library an essential source for learning and teaching optimization algorithms.
* **_Useful resource for researchers, students, and industries:_** we are striving to make this library an essential resource for researchers, students, and industries.

## Q5: what we mean by ensuring the consistency?
**Consistency** is the main feature of this library. We will strive to be consistent in project structure, coding, documentation, videos, and datasets. The following provide a basic consistency points of this library:

1. **Consistency in the project structure**
	* Consistency in guidelines, styles, and templates.
	* Consistency in creating new modules and packages. 
	* Consistency in the file names, folders names, folders hierarchies, configuration files, files arrangement and distributions.
	* Consistency in dates and times of updating and reviewing.
	*  Consistency in working teams and reviews.
	* Consistency in evaluation tests and validation.
	* Consistency in reviews methodology.

2. **Consistency in the code**
	* Consistency within one module or function 
	* Consistency in return statements. 
	* Consistency in input, and output.
	* Consistency in print and summary.
	* Consistency in signatures of objects, methods, or data attributes.
	* Consistency in code style. The style of coding should be consistent and following special best practices guides such as spaces, comments, etc.
	* Consistency in the data structure.

3. **Consistency in the documentation**
	* Consistency in describing problems, algorithms, and implementations.
	* Consistency in describing classes, methods, attributes.
	* Consistency in titles.
	* Consistency in adding new sections and chapters.
	* Consistency in naming conventions. The naming conventions should follow a certain naming standard. 
	* Consistency in writing many special names such as the names of operating systems, programming languages, standards bodies, etc.
	* Consistency in writing abbreviations. 
	* Consistency in references.
	* Consistency in code documentation.
	* Consistency in describing the datasets.

4. **Consistency in the videos**
	* Video length should follow ultimate guide to ensure consistency.
	* The methodology of describing problems, algorithms, implementation should ensure consistency.
	* All videos should be hosted in one place such as one YouTube channel.
	* The videos should be categorized properly with consistency in mind. 
	* Consistency in ordering and naming
	* Consistency with the documentation

5. **Consistency in the datasets**
	* The structure of the dataset should follow a certain formatting and structure.
	* The test datasets should be consistent to validate and ensure the quality of the implemented algorithms.

## Q6: what are the metrics that will be used to measure success?
* Number of installations 
* Number of problems that are considered.
* Number of algorithms that are considered.
* Number of implementations
* Number of Awards
* Number of citations
* Number of visitors/readers
* Number of developers/contributors 
* Number of reviewers
* Number of versions
* Number of issues
* Number of comments
* Number of research groups that use or support -OAL-
* Number of industries that use or support -OAL-
* Number of students 




## Q7: what is the structure of this library?
> ### Optimization-Algorithms 
> > **Partitioning Problem** 
> > > `Kernighan-Lin (KL)`
> > > 
> > > `Simulated Annealing (SA)`
> > > 
> > >  `Hybridization SA+KL`
> > >  
> > >  `Others not Yet implemented`
> > >  
> > **Floor Planning Problem**  
> > >  
> > >  `Algorithms not Yet implemented`
> > >  
> > **Schedualing Problem**  
> > >  
> > >  `Algorithms not Yet implemented`
> > >  
> > **Rooting Problem**  
> > >  
> > >  `Algorithms not Yet implemented`
> > >  
> > **Other problems not Yet defined** 

<br />

![Optimization Hierarchy](https://github.com/alqmase/optimization-algorithms/blob/main/img/home/problems-hierarchy.png) 
#

## Q8: what is our future plan?

|Date|Version|Main Deliverable Features|
|----|-----|-----|
|26th September, 2021|0.1.0| (1)	Formulating at least three problems (2)	Implementing at least ten optimization-algorithms (3)	Stablishing official website for this project (4)	Improving the consistency |
|26th September, 2022|0.2.0|(1)	Formulating at least three new problems (2)	Implementing at least ten optimization-algorithms (3)	Publishing at least one paper (4)	By this time, the author expects that we receive at least three citations. (5)	By this time, the author expects that the library will be a good resource in industries. (6)	By this time, the author expect that the library tutorial will be a recommended source for learning optimization algorithm. (7)	By this time, the author expect that the library receives a number of contributions from researchers.|
|26th September, 2023|0.3.0|(1)	Formulating at least three new problems (2)	Implementing at least ten optimization-algorithms. (3)	Publishing at least one new paper. (4)	By this time, the author expects that the library will be cited by at least new thirty citations. (5)	By this time, the author expects that the number of industries that used the library is increased by at least half. (6)	By this time, the author expect that the library tutorial will be a recommended source for learning optimization algorithm. (7)	By this time, the author expect that the library receives a number of contributions from researchers.|
|26th September, 2024|0.4.0|(1) By this time, the author expects that the library becomes essential library for many industries. (2) By this time, the author expects that the library becomes essential library for many researchers. (3) By this time, the author expects that the library becomes well-known library in the academic environment.|

## Q9: what is the development methodology?
The author adapts the GitHub methodology for contributing to this library. The proposed methodology has two steps. The first step is formulating the problem. This library is problem-wise library where the problem should be formulated into inputs and outputs with consistency in mind. The second step is contributing to this problem by implementing optimization algorithms to the given problem. The implementation can be done in parallel by many developers as shown in the following Figure.


![methodology](https://github.com/alqmase/optimization-algorithms/blob/main/img/home/methodology.png) 

## Q10: how volunteers, students, developers, researchers can contribute? 
The contribution is easy. The project is hosted in the GitHub. Therefore, any contributor can create new branch and add or update the project. Then, follow the GitHub approach where pull requests and issues can be generated. After, the consistency is ensured, the updates will be merged to the main project for next version.

## Q11: what are the current version services of this library?
In the current version, I focused on one problem which is partitioning. For this problem, we implemented three algorithms as described in the following Table.

|**Algorithm**|**Description**|
|---------|-----------|
|`kernighan_lin_0101(G, initial_partitions, attrs)`|Kernighan-Lin algorithm is well-known bi-partitioning heuristic. This implementation is optimized where many overheads are eliminated. The time complexity of this implementation is `O(n^2)`. This algorithm can have only one parameter which is G (undirected, unweighted, or Edges-weighted Graph) and produce balanced partitions.  The `initial_partitions` parameter is optional.|
|`simulated_annealing_0102(G, initial_partitions, attrs)`|Simulated annealing algorithm is well-known meta heuristic algorithm. This implementation is developed for graph bi-partitioning problem. This algorithm can have three parameters which are `G` (undirected, unweighted, or Edges-weighted Graph), and two algorithm-specific attributes (`cooling_rate` and `temperature`). The default values for cooling_rate is (`0.0001`) and for temperature is (`10000`). The `initial_partitions` parameter is optional. This algorithm produces balanced partitions.   |
|`hybridization_SA_KL_0103(G, initial_partitions, attrs)`|This Hybridization technique can help adapting the advantages of the two algorithms (simulated annealing and Kernighan-Lin algorithms).    The proposed hybridization can optimize both `running time` and `cost-cut` quality. This algorithm can have three parameters which are `G` (undirected, unweighted, or Edges-weighted Graph), and two algorithm-specific attributes (`cooling_rate` and `temperature`). The default values for cooling_rate is (`0.001`) and for temperature is (`100`). The `initial_partitions` parameter is optional. This algorithm produces balanced partitions.  |


<br />
<br />



|**Returns**|**Descriptions**|
|----|-----|
|`best cost-cut`|The total weights of cross-partition edges are called cost-cut. The goal is to minimize the number of cross partition edges. This output shows the minimum cost-cut achieved by the current run of the given algorithm.|
|`best-partitions`|It returns the partitions that have minimum cost cut (best cost cut). It will return iteratable object that contains the nodes labels of each partition. |

<br />
<br />



|**Common functions**|**Descriptions**|
|----|-----|
|`get_initial_partitions()`|This will return iteratable object contains initial partitions.|
|`get_best_partitions()`|This will return iteratable object contains best partitions.|
|`get_initial_cost_cut()`|This will return a value that shows the cost-cut of the initial partitions.|
|`get_bestt_cost_cut()`|This will return a value that shows the cost-cut of the best partitions.|

<br />
<br />
<br />





# Installation

Use the package manager [pip](https://pip.pypa.io/en/stable/) to install optimization-algorithms.

```bash
pip install optimization-algorithms
```


<br />
<br />
<br />




# Usage
In this library, we used [networkx](https://networkx.org/) to create a graph where the graph is used as input in many problems such as partitioning. Therefore, the first step is to create a graph. One possible approach of creating undirected graph is as follows:
 
```python
import networkx as nx

def create_graph():
    edgelist = [(5, 6), (5, 9), (6, 7), (6, 10), (7, 8), (7, 11), 
                (8, 12),(1, 2), (1, 5), (2, 3), (2, 6), (3, 4), 
                (3, 7), (4, 8), (9, 10), (9, 13), (10, 11), 
                (10, 14), (11, 12), (11, 15), (13, 14), (14, 15),
                (15, 16),(12, 16)]
    G = nx.Graph(edgelist)
    return G
```

To show how the optimization-algorithms library can be used for partitioning problem, we need a dataset.  In this case, we will use two-dimensional grid graph to show how this library can be used for portioning problem.  In the grid graph, each node connected to its four nearest neighbors. To generate the grid graph, we implement the following function:

```python
import networkx as nx
def generate_grid_2d_graph_dataset(grid_size):
    cols=[(i * grid_size + j, i * grid_size + j+1)  for i in range(grid_size) for j in range(grid_size-1)]
    rows=[(j * grid_size + i, j * grid_size + i + grid_size)  for i in range(grid_size) for j in range(grid_size-1)]
    edgeList=cols+rows
    return  nx.Graph(edgeList)
```

The following code shows how 4X4 grid graph can be generated.

```python
G=generate_grid_2d_graph_dataset(4)
nx.draw(G, with_labels=True)
```
> `**OUTPUT**`
>
> ![grid4X4](https://github.com/alqmase/optimization-algorithms/blob/main/img/home/grid4X4.png) 


The following code shows how 10X10 grid graph can be generated.

```python
G=generate_grid_2d_graph_dataset(10)
nx.draw(G, with_labels=True)
```
> `**OUTPUT**`
>
> ![grid4X4](https://github.com/alqmase/optimization-algorithms/blob/main/img/home/grid10X10.png) 


In the first step, we will import the optimization-algorithms library for partitioning problem where three algorithms for bi-partitioning will be imported. The following code show how these algorithms can be imported.


```python
from optimization_algorithms.for_partitioning import kernighan_lin_0101, simulated_annealing_0102, Hybridization_SA_KL_0103
```
The following code shows how 100X100 grid graph can be partitioning using Kernighan-Lin (KL) with the default parameters.
```python
G=generate_grid_2d_graph_dataset(100)
```

```python
KL=kernighan_lin_0101(G)
```

> `**OUTPUT**`
>
> -------Result Summary---------
>
>	initial cost-cut :             9841                
>	Best cost-cut :                130                 
>	Running Time in Second :       76.8

The best partitions can be obtained by the following function:
```python
partitions=KL.get_best_partitions()
```

The following code shows how 100X100 grid graph can be partitioning using Simulated Annealing algorithm (SA) with the default parameters.
```python
SA=simulated_annealing_0102(G)
```
> `**OUTPUT**`
>
> -------Result Summary---------
>
>	initial cost-cut :             9837                
>	Best cost-cut :                4454                 
>	Running Time in Second :       3.1

The best partitions can be obtained by the following function:
```python
partitions=SA.get_best_partitions()
```
The following code shows how 100X100 grid graph can be partitioning using Hybridization SA&KL algorithm with the default parameters.

```python
SA_KL = hybridization_SA_KL_0103(G)
```
> `**OUTPUT**`
>
> -------Result Summary---------
>
>	initial cost-cut :             9902                
>	Best cost-cut :                119                 
>	Running Time in Second :       35.5

The best partitions can be obtained by the following function:
```python
partitions= SA_KL.get_best_partitions()
```
To create initial partitions and pass it as parameter, in this example, we may create the initial partitions as even partition and odd partition where the nodes with even labels will be in one partition, and the nodes with odd labels will be in another partition. The following function can help generate the initial partition.

```python
def create_initial_partitions(G):
    even=[i for i in G.nodes if i%2 == 0]
    odd =[i for i in G.nodes if i%2 == 1]
    return [even, odd]

```
The following code is used to prepare the initial_partitons parameters.
```python
initial_partitions=create_initial_partitions(G)
```
Now, we can pass this parameter to the three algorithms. 
```python
KL=kernighan_lin_0101(G, initial_partitions)
```
> `**OUTPUT**`
>
> -------Result Summary---------
>
>	initial cost-cut :             9900                
>	Best cost-cut :                111                 
>	Running Time in Second :       56.4


```python
SA=simulated_annealing_0102(G, initial_partitions)
```
> `**OUTPUT**`
>
> -------Result Summary---------
>
>	initial cost-cut :             9900                
>	Best cost-cut :                111                 
>	Running Time in Second :       56.4


```python
SA_KL = hybridization_SA_KL_0103(G, initial_partitions)
```
> `**OUTPUT**`
>
> -------Result Summary---------
>
>	initial cost-cut :             9900                
>	Best cost-cut :                111                 
>	Running Time in Second :       56.4

The following code shows how to play with algorithm-specific parameters such as cooling-rate and temperature parameters of simulated annealing algorithm and hybridization SA-KL algorithm. 

```python
Attrs={'cooling_rate':0.001, 'temperature':1000}
```

```python
SA=simulated_annealing_0102(G, initial_partitions, Attrs)
```
> `**OUTPUT**`
>
> -------Result Summary---------
>
>	initial cost-cut :             9900                
>	Best cost-cut :                111                 
>	Running Time in Second :       56.4


```python
SA_KL = hybridization_SA_KL_0103(G, initial_partitions, Attrs)
```
> `**OUTPUT**`
>
> -------Result Summary---------
>
>	initial cost-cut :             9900                
>	Best cost-cut :                111                 
>	Running Time in Second :       56.4

There are some Tips in using parameters. Simulate annealing and hybridization are different algorithm. It is better to examine each one with different values of the cooling rate and temperature parameters. The hybridization algorithm requires only small values. For Kernighan-Lin algorithm, there are some useful functions that allow user to obtain some useful information. The following shows those functions.

```python
KL.get_number_of_iterations()
```
> `**OUTPUT**`
>
> 19

We can notice that the number of iterations by KL for the given dataset is 19.

```python
KL.get_cost_per_iterations()
```
> `**OUTPUT**`
>
> [9900, 3154, 2900, 2836, 2436, 2100, 1900, 1700, 1500, 1300, 1100, 	 1002, 700, 602, 237, 154, 135, 111, 111]





<br />
<br />
<br />




# License
[MIT](https://choosealicense.com/licenses/mit/)
#