11institutetext: Universidad de los Andes
Cra. 1 No 18a - 12 Edif. Mario Laserna Pinzón (Bogotá), Colombia
https://pylopre.uniandes.edu.co/
Grupo PyLO Producción y Logística
11email<EMAIL_ADDRESS>
# A Matheuristic Multi-Start Algorithm for a Novel Static Repositioning
Problem in Public Bike-Sharing Systems.

Julio Mario Daza-Escorcia
David Álvarez-Martínez  0000-0003-4557-5150 0000-0001-8411-1936

###### Abstract

This paper investigates a specific instance of the static repositioning
problem within station-based bike-sharing systems. Our study incorporates
operational and damaged bikes, a heterogeneous fleet, and multiple visits
between stations and the depot. The objective is to minimize the weighted sum
of the deviation from the target number of bikes for each station, the number
of damaged bikes not removed, and the total time used by vehicles. To solve
this problem, we propose a matheuristic approach based on a randomized multi-
start algorithm integrated with an integer programming model for optimizing
the number of operatives and damaged bikes that will be moved between stations
and/or the depot (loading instructions). The algorithm’s effectiveness was
assessed using instances derived from real-world data, yielding encouraging
results. Furthermore, we adapted our algorithm to a simpler problem studied in
the literature, achieving competitive outcomes compared to other existing
methods. The experimental results in both scenarios demonstrate that this
algorithm can generate high-quality solutions within a short computational
time.

###### Keywords:

Bike-sharing Static repositioning Matheuristic multi-star Damaged bikes.

##  1 Introduction

Bike-sharing systems (BSS) originated over 50 years ago in Northern Europe,
serving as a mobility facilitator and a supplement to traditional public
transportation. Notable advantages include their minimal environmental impact
and cost-effectiveness compared to other transportation modes. Despite these
benefits, specific challenges and instances of dissatisfaction need attention.
For instance, issues arise when a station needs more free anchors for bike
parking, has insufficient available bikes for users, or when the available
bikes are damaged, hindering the system’s smooth operation.

These scenarios give rise to what is known as the _Bike-sharing Repositioning
Problem_ (BRP), involving the redistribution or rebalancing of bikes within
the system through a fleet of vehicles. This process entails the movement of
operative bikes and/or damaged bikes between stations and the depot to align
their inventory with a desired or target level.

Two primary classifications exist within public bike-sharing systems. The
first, referred to as the _Station-Based Bike Sharing_ (SBBS) system, allows
users to rent bikes at designated stations and return them either to the same
station or any specified station upon completion of use [1]. The second
classification is the _Free-Floating Bike Sharing_ (FFBS) system, where bikes
can be picked up and dropped off at locations chosen by the users [21].

The literature identifies two types of repositioning strategies: dynamic and
static. In the _dynamic approach_ , bikes are repositioned while the system is
actively used, such as during the day. Instead, the _static approach_ involves
repositioning during minimal from the bike’s utilization on the system,
typically at night.

Our research focuses on a static approach to the bike-sharing repositioning
problem, particularly within the station-based model. We refer to this as the
_Station-Based Static Bike-sharing Repositioning Problem_. This study provides
significant contributions to the typical _Static Bike-sharing Repositioning
Problem_ (SBRP) in the following aspects:

  1. 1.

Introducing a novel instance of the static repositioning problem within
station-based bike-sharing systems, incorporating additional factors to
enhance realism. These include considerations for operational and damaged
bikes, a heterogeneous fleet, and multiple visits between stations and the
depot.

  2. 2.

Presenting an integer programming model to optimize the number of operative
and damaged bikes to be moved between stations and/or the depot (loading
instructions).

  3. 3.

Proposing an effective matheuristic based on a randomized multi-start
algorithm integrated with an integer programming model to handle large
instances.

The remainder of the paper is organized as follows. Section 2 provides the
literature review. The description of the research problem proposed is
presented in Section 3. Section 4 describes the proposed solution methodology
to solve the research problem. Section 5 presents a Randomized Multi-Start
Algorithm, and Section 6 describes an exact method to optimize loading
instructions of a previously constructed set of routes. Section 7 introduces
the set of instances used in this study and our computational experiments.
Finally, conclusions and remarks are presented in Section 8.

##  2 Literature Review

Much research has been published recently exploring different aspects of the
BRP. This paper primarily examines the characteristics of SBRP, including its
objectives and optimization methods. The characteristics of SBRP include the
fleets, multiple or single visits to the stations or depot, and types of bikes
for repositioning.

The literature encompasses works that explore either homogeneous or
heterogeneous fleets of vehicles. Most of these studies employ a heterogeneous
fleet of vehicles, which is also the case in our problem. Including a
heterogeneous fleet increases the complexity of the problem but results in a
more realistic scenario. The studies for the static case that employing a
heterogeneous fleet include those by Alvarez-Valdes et al. [1], Casazza [3],
Di Gaspero et al. [11, 10, 12], Espegren et al. [8], Forma et al. [9], Kinable
[16], Papazek et at. [23, 22], Raidl et al. [24], Rainer-Harbach et al [25,
26], Raviv et al. [27], Schuijbroek et al. [28], Du et al. [7] and Wang and
Szeto [31].

Multiple visits to the stations can occur in two distinct manners: (1) when a
station is open for visits by multiple vehicles but restricts repeated visits
by the exact vehicle (similar to the _Split Delivery Vehicle Routing Problem_
, SDVRP), and (2) when stations permit multiple visits by the same or
different vehicles. In this study, we specifically focus on this latter
scenario because it reflects a common occurrence in real-world settings within
BRPs. This feature is evident in the works of Alvarez-Valdes et al. [1],
Casazza [3], Di Gaspero et al. [11, 10, 12], Espegren et al. [8], Forma et al.
[9], Kloimullner and Raidl [17], Papazek et at. [23, 22], Raidl et al. [24],
Rainer-Harbach et al [25, 26], Raviv et al. [27], Schuijbroek et al. [28], Du
et al. [7] and Wang and Szeto [31].

Regarding the types of bikes, most studies focus on a single type of bike
(operative or usable bikes). Alvarez-Valdes et al. [1] and Wang and Szeto [31]
acknowledge the potential presence of damaged (unusable) bikes, suggesting
their removal from the stations. In contrast, Li et al. [19] introduces
diverse types of bikes but does not address the possibility of having damaged
ones. Lastly, Du et al. [7] stand out as they consider the collection of
damaged bicycles, but specifically in the context of _Free-Floating Bike
Sharing_ (FFBS) systems.

Beyond the diverse characteristics, the objectives explored in the literature
of BRPs exhibit considerable variation. Typically, these studies seek to
optimize one or multiple performance metrics, such as travel cost, time or
distance, the count of loading and unloading operations at stations, the
absolute deviation from the target number of bikes at stations, and so forth.
In this paper, we propose a multi-objective problem aimed at minimizing the
weighted sum of three terms: the deviation from the target number of bikes for
each station, the number of damaged bikes left unremoved, and the total time
used by vehicles.

Regarding the solution methods for the SBRP, while the majority are
heuristics, we encountered some tailored algorithms. Table 1 summarizes the
heuristic solution methods for SBRP. In our study, we propose a metaheuristic
approach, which combines mathematical optimization techniques with heuristic
methods to address complex optimization problems, such as the SBRP proposed
here.

Table 1: Heuristic solution methods for SBRP. Solution method |  Article
---|---
3-step heuristic | [9]
9.5-approximation Algorithm | [2]
Ant Colony Optimization | [11]
Chemical Reaction Optimization | [29]
Cluster-first Route-second Heuristic | [28]
Destroy and Repair Algorithm | [6]
Genetic Algorithm |  [15], [18], [7]
Greedy Randomized Adaptive Search Procedure |  [23], [22], [26]
Heuristic based on Minimum Cost Flow Problem | [1]
Hybrid Genetic Search | [19]
Iterated Local Search |  [5], [30]
Iterated Tabu Search | [13]
Large Neighborhood Search |  [10], [12], [14], [21]
Particle Swarm Optimization | [32]
Path Relinking | [22]
Tabu Search | [4]
Variable Neighborhood Descent |  [5], [23], [22], [21] , [25], [26], [32]
Variable Neighborhood Search |  [24], [25], [26], [20]

As apparent from the preceding literature review, several studies have been
undertaken on the SBRP. Nonetheless, based on our understanding, more research
is still needed concerning static repositioning bike-sharing problems,
particularly regarding the collection of damaged bikes. This gap is especially
notable when considering the inclusion of a heterogeneous fleet and multiple
visits within this problem domain.

This paper presents a novel instance of the repositioning bike-sharing problem
with a static approach and within the station-based model. This problem
incorporates operational and damaged bikes, a heterogeneous fleet, and
multiple visits between stations and the depot. The objective is to minimize
the weighted sum of the deviation from the target number of bikes for each
station, the number of damaged bikes left unremoved, and the overall time used
by vehicles. To solve this problem, we propose a matheuristic approach
combining a randomized multi-start algorithm with an integer programming model
to optimize the number of bikes relocated during each visit.

##  3 Problem Description

The _Station-Based Static Bike-sharing Repositioning Problem_ (SSBRP)
considering in this paper is defined on a complete directed graph
$G_{o}=(V_{o},A_{o})$, where $V_{o}$ are the nodes set represented to the set
of stations $V$ and the depot $O$ (i.e, $V_{o}=V\cup O$), and $A_{o}$ are the
arcs representing the shortest paths (one for each pair of nodes). Each arc
$(u,v)\in A_{o}$ with $u,v\in V_{o}$ has a cost $t_{(u,v)}$ representing the
travel time between $u$ and $v$.

The depot $O\in V_{o}$ has a sufficient capacity $c_{o}$, and an initial
inventory of operative (or usable) bikes $p_{o}\geq 0$. Each station
$v_{\in}V$ has a capacity (or parking docks) $c_{v}>0$, an initial inventory
of operative bikes $p_{v}\geq 0$ and damaged bikes $a_{v}\geq 0$, a target
(desired) ending inventory $q_{v}\geq 0$, and a weight (or visit priority)
$w_{v}$.

We define the initial unbalance of operative bikes $d_{v}=p_{v}-q_{v}$.
According to its imbalance, a station can be: balanced $V_{bal}=\\{v\in V\mid
d_{v}=0\\}$, in surplus $V_{pic}=\\{v\in V\mid d_{v}>0\\}$, in deficit
$V_{del}=\\{v\in V\mid d_{v}<0\\}$. In either case, a station may have damaged
bikes $V_{ave}=\\{v\in V\mid a_{v}\geq 0\\}$.

A set of trucks $L$ can pick up or deliver bikes at each station or depot
(i.e., $L=\\{1,\dots,\lvert L\rvert\\}$). Each vehicle $l\in L$ has a
heterogeneous capacity of $k^{l}$, a route time no longer than $T$, and the
depot as the starting and ending point of the tour.

A possible solution to the SSBRP consists of a set of $R$ routes and $Y$
movements. Each route $r^{l}\in R$ is assigned to a vehicle $l$, and has an
ordered list of tours $r^{l}=\\{v_{1}^{l},\ldots,v_{n^{l}}^{l}\\}$. The route
must start and end at the depot, and not exceed the capacity $k^{l}$ and the
maximum route time $T$.

A loading instructions $y^{l}$ consists of a number of operative $B_{i}^{l}$
and damaged $A_{i}^{l}$ bikes that will be moved on visit $i$ by vehicle $l$,
such that if $B_{i}^{l}>0$ operative bikes are loaded on the vehicle, on the
other hand if $B_{i}^{l}<0$ these bikes are unloaded, if $B_{i}^{l}=0$ no
movements of operative bikes are made. Similarly for $A_{i}^{l}$. The load
instructions are formally defined as
$y^{l}=\\{(B_{1}^{l},A_{1}^{l}),\ldots,(B_{n^{l}}^{l},A_{n^{l}}^{l})\\}$).

The proposed SSBRP has as its objective function to design the routes of the
vehicles and the number of both operative and damaged bikes to be moved at
each station in such a way that a weighted sum of three terms is minimized,
where $\hat{d}_{v}$ and $\hat{a}_{v}$ represent the operative and damaged
bikes at the end of the repositioning operation.
$\gamma_{d},\gamma_{a},\gamma_{t}$ are the weights of the respective terms.

$\frac{\sum_{v\in V}w_{v}|q_{v}-\hat{p}_{v}|}{\sum_{v\in
V}w_{v}|q_{v}-p_{v}|+a_{v}}\gamma_{d}+\frac{\sum_{v\in
V}w_{v}\hat{a}_{v}}{\sum_{v\in
V}w_{v}|q_{v}-p_{v}|+a_{v}}\gamma_{a}+\frac{\sum_{l\in
L}t^{l}}{T*|L|}\gamma_{t}$ (1)

The first and second terms represent the imbalance and the number of damaged
bikes at the end of the repositioning for all the stations. The third term
relates to the total fleet operation time and is given by the total time of
all routes divided by the maximum repositioning time of the entire fleet.

##  4 Algorithmic Proposal

To address our described SSBRP detailed in Section 3, we introduce a
matheuristic procedure that combines a randomized multi-start algorithm with
an integrated integer programming model. Our matheuristic, which relies on the
_Randomized Multi-Start Algorithm_ (RMS), comprises two phases presented in
Algorithm 1).

In the first phase, a solution is constructed using RMS in the first phase,
where the RMS creates a solution at each iteration, which is updated if it
improves. The routes are created for each vehicle sequentially, i.e., one
after the other. The routes are formed by iteratively inserting a new node at
the end of the partial route using a greedy strategy, as detailed in Section
5.

The second phase involves optimizing the loading policy (or loading
instructions) for a given feasible solution obtained by RMS in each iteration.
This optimization is done through an integer mathematical model described in
Section 6. The objective is to determine the optimal loading policy for a
given set of routes, specifying the number of operative and damaged bikes to
be moved at the station or depot. The procedure is repeated in each iteration,
yielding high-quality solutions within short computational times.

Algorithm 1 – Matheuristic two-phase algorithm

0: Instance $I$

0: Parameter $MaxIter$

1: $\;Iter\leftarrow 1$, $\;\mathcal{S}\leftarrow\emptyset$

2: repeat

3: $\quad\mathcal{S}^{{}^{\prime}}\leftarrow$Randomized Multi-
Start$(I)\qquad\qquad\quad$// Phase I

4: $\quad\mathcal{S}^{{}^{\prime\prime}}\leftarrow$Optimal Loading
Instructions$(\mathcal{S}^{{}^{\prime}})\qquad$// Phase II

5: if $\mathcal{S}^{{}^{\prime\prime}}$ is better than $\mathcal{S}$ then

6: $\mathcal{S}\leftarrow\mathcal{S}^{{}^{\prime\prime}}$

7: $Iter\leftarrow 1$

8: else

9: $Iter\leftarrow Iter+1$

10: end if

11: until $Iter=MaxIter$

11: a feasible solution $\mathcal{S}$

In the subsequent sections, each phase of the developed matheuristic is
presented in detail.

##  5 Phase I: Randomized Multi-Start Algorithm

The _Randomized Multi-start Algorithm_ (RMS) sequentially constructs routes
for each vehicle. Routes are formed by iteratively inserting a new node at the
end of the partial route using a greedy strategy. Starting from the last visit
$u$ of a partial route (or initially, the depot), we identify the set
$F\subseteq V_{0}$ of feasible successors. For each candidate $v\in F$, we
compute a ratio between the maximum number of bikes to be moved at $v$ and the
travel time $t_{uv}$ we will take to visit each node candidate. Among the
candidates with the highest ratio values, one node is randomly selected for
insertion as the next visit in the current route. See Algorithm 2.

At each algorithm stage, we have built a partial solution that includes
station visits and loading and unloading operations on them. Suppose that the
constructed route is $l$, and $u$ is the last node inserted in this partial
route. As a result of the partial solution so far constructed, the states of
the depot and the stations have changed (i.e., after each insertion of a new
node $u$ at the end of the current route, say $l$, we update the whole
information of the depot, stations, and vehicles).

For each station $v$, let us denote by $\bar{d}_{v}$ and $\bar{a}_{v}$,
respectively, the imbalance and the number of damaged bikes according to the
partial solution built, and $\bar{p}^{l}_{0}$ the remaining number of
operative bikes at the depot that can be taken by vehicle $l$ (that is, they
have not been left by another vehicle). We denote by $\bar{V}_{def}=\\{\,v\in
V\,:\,\bar{d}_{v}<0\,\\}$, $\bar{V}_{spl}=\\{\,v\in V\,:\,\bar{d}_{v}>0\,\\}$,
$\bar{V}_{bal}=\\{\,v\in V\,:\,\bar{d}_{v}=0\,\\}$ and
$\bar{V}_{dam}=\\{\,v\in V\,:\,\bar{a}_{v}>0\,\\}$. We denoted by
$\bar{p}^{l}$ and $\bar{a}^{l}$, respectively, the number of operative bikes
and damaged bikes on the vehicle $l$ after visiting $u$, and let $\bar{t}^{l}$
the partial traveling time of route $l$. Additionally, we denote by
$\bar{k}^{l}$ the minimum number of free lockers in the vehicle in the section
of the current route from the last visit to the depot to node $u$.

Algorithm 2 – Randomized Multi-Start Algorithm

0: Instance $I$

1: $\;\mathcal{S}\leftarrow\emptyset$

2: for all $l\in L$ do

3: $\;i\leftarrow 1$, $\;F\leftarrow\emptyset\qquad$// First stop

4: Initialize the route with $r^{l}(1)$ and Loading Instructions $y^{l}(1)$

5: Define the set of candidate nodes $F\subseteq V_{0}$ to visit from $i$

6: while $|F|\neq\emptyset$ do

7: Calculate the ratios $\rho_{v}$ of each candidate $v\in F$

8: Select randomly $v^{*}$ among the highest ratios:
$\epsilon\times\rho_{max}\leq\rho_{v}\leq\rho_{max}$

9: $\;i\leftarrow i+1\qquad$// Next stop

10: Insert the node $v^{*}$ in the visit $r^{l}(i)$

11: Define Loading Instructions $y^{l}(i)$ on the node $v^{*}$

12: Define the set of new candidate nodes $F\subseteq V_{0}$ to visit from $i$

13: end while

14: Close the route $r^{l}$ visiting the depot and delivery all the bikes

15: Update the route set $r^{l}$ and the Loading Instructions $y^{l}$

16: $\;\mathcal{S}\leftarrow(r^{l},y^{l})$

17: end for

17: a feasible solution $\mathcal{S}$

The election of the next route visit $l$ is as follows: Firstly, a set of
potential candidates $F$ is built. This set initialized with all the nodes
$v\in\bar{V}_{def}\cup\bar{V}_{spl}\cup\bar{V}_{dam}$, $v\neq u$, such that
$\bar{t}^{l}+t_{uv}+t_{v0}\leq T$, that is, those nodes not balanced or with
damaged bikes that could be inserted after $u$ in the current route without
exceeding the time limit $T$ (also considering the time needed to return to
the depot). The depot is added to $F$ if $u\neq 0$ and $\bar{a}^{l}>0$.

For each potential candidate $v\in F$, $v\neq 0$, we compute the maximum
number of operative bikes $\beta_{v}$ and damaged bikes $\alpha_{v}$ we can
move if $v$ is inserted after node $u$ in the current route. These quantities
are computed as:

$\beta_{v}=\left\\{\begin{array}[]{lcl}\mbox{min}\\{\,k^{l}-\bar{p}^{l}-\bar{a}^{l},\,\bar{d}_{v}\,\\}&&v\in
F\cap\left(\bar{V}_{spl}\cup\bar{V}_{bal}\right)\\\\[5.69046pt]
\mbox{min}\\{\,\bar{p}^{l}+\mbox{min}\\{\bar{p}^{l}_{0},\bar{k}^{l}\\},\,|\bar{d}_{v}|\,\\}&&v\in
F\cap\bar{V}_{def}\\\ \end{array}\right.$ (2)
$\alpha_{v}=\left\\{\begin{array}[]{lcl}\mbox{min}\\{\,k^{l}-\bar{p}^{l}-\bar{a}^{l}-\beta_{v},\,\bar{a}_{v}\,\\}&&v\in
F\cap\left(\bar{V}_{spl}\cup\bar{V}_{bal}\right)\\\\[5.69046pt]
\mbox{min}\\{\,k^{l}-\bar{p}^{l}-\bar{a}^{l}+\beta_{v},\,\bar{a}_{v}\,\\}&&v\in
F\cap\bar{V}_{def}\\\ \end{array}\right.$ (3)

Note that in the case where $v\in\bar{V}_{def}$ with
$|\bar{d}_{v}|>\bar{p}^{l}$, we could consider to have taken more operative
bikes from the depot if $\bar{p}^{l}_{0}>0$. To do it, we also have to check
if the vehicle has enough capacity to carry it from the depot to $v$,
represented by $\bar{k}^{l}$. This is the reason to consider
$\mbox{min}\\{\,\bar{p}^{l}+\mbox{min}\\{\bar{p}^{l}_{0},\bar{k}^{l}\\},\,|\bar{d}_{v}|\,\\}$
in (2). Finally, if $v=0$, we assume that the damaged bikes on the vehicle
$\bar{a}^{l}$ would be unloaded in the depot.

The ultimate set of candidate successors for node $u$ in the route is derived
by excluding from $F$ those stations $v$ where $\beta_{v}+\alpha_{v}=0$. If
$F=\emptyset$, we conclude the route by appending a visit to the depot and
unloading all the bikes from the vehicle. Otherwise, for each $v\in F$, we
calculate a ratio $\rho_{v}$ using the following formula:

$\rho_{v}=\left\\{\begin{array}[]{lcl}\frac{(\alpha_{v}+\beta_{v})^{\theta}}{t_{uv}}w_{v}&&v\in
F\cap V\\\\[5.69046pt] \frac{\bar{a}^{l}}{t_{u0}}\mu&&v=0\in F\\\
\end{array}\right.$ (4)

where, parameters $\theta\in(0,1]$ and $\mu$ are employed to fine-tune the
algorithm. A value of $\theta<1$ is utilized to discourage the selection of
stations with a substantial number of bikes to be moved, especially those that
are far from $u$, in favor of stations that are closer to $u$ even if the
number of bikes to be moved is not as large. Lastly, if $\mu>1$, it promotes
visits to the depot.

In a deterministic scheme, we would choose as the next visit in the route the
candidate $v^{*}$ such that
$\rho_{v^{*}}=\rho_{max}=\mbox{max}\\{\,\rho_{v}\,:\,v\in F\,\\}$. However, we
have embedded the algorithm into an randomized multi-start scheme that
executes the construction of the solution a number of times equal to $MaxIter$
and output the best solution generated.

In this algorithm, the next node $v^{*}$ is randomly selected among the
candidates with the highest values of their ratios. Specifically, let
$\epsilon$ be a random number in $(0,1)$, then $v^{*}$ is randomly selected
among the candidates $v\in F$ such that
$\epsilon\times\rho_{max}\leq\rho_{v}\leq\rho_{max}$.

Once the node $v^{*}$ has been selected for the next visit, we carry out the
loading instructions procedure, that is, define the number of operative bikes
and damaged bikes to be moved at the station or the depot are given by
$\beta_{v^{*}}$ and $\alpha_{v^{*}}$, respectively. In the case where
$|\bar{d}_{v^{*}}|>\bar{p}^{l}$ and
$\mbox{min}\\{\bar{p}^{l}_{0},\bar{k}^{l}\\}>0$, $\beta_{v^{*}}-\bar{p}^{l}$
additional operative bikes are taken in the last visit to the depot, and the
values of $\bar{k}^{l}$ and $\bar{p}^{l}_{0}$ are consequently updated.

##  6 Phase II: Optimal Loading Instructions

Given a feasible solution provided by RMS (See Section 5) in each iteration
described above, we apply an integer mathematical model to finding the optimal
loading instructions in each route generated. Given a set of $s$ routes, this
model determines the optimal loading policy, minimizing the final imbalance
and the number of damaged bikes not removed.

Below, we present the data and variables required for developing the proposed
mathematical formulation.

Data:

  * •

initials of the stations and depot $v_{\in}V_{o}$ visited in $s$.

  * •

from the fleet of vehicles.

    * –

$\overline{L}$: Set of vehicles used in $s,\overline{L}\subseteq L$.

    * –

$k^{l}$: Vehicle capacity $l,\overline{L}$.

  * •

of the route.

    * –

$n^{l}$: Number of visits of the route (vehicle) $l^{l}$.

    * –

$r^{l}(i)$: Station or depot at the i-th visit of the route $l^{l}(i)$:
Station or depot at the i-th visit of the route $l^{l},i=1,\ldots,n^{l}$.

Variables:

For each path $l\in\overline{L}$:

  * •

$b_{o}^{l}$: number of operative bikes in the depot that will use $l$.

  * •

For each visit $i,i=1,\ldots,n^{l}$, to the stations or the depot:

    * –

$x_{i}^{l}$: number of operative bikes taken (+) or left (-).

    * –

$y_{i}^{l}$: number of damaged bikes taken (+) or left (-).

  * •

For each visit $i,i=1,\ldots,n^{l}-1$, in vehicle $l$:

    * –

$z_{i}^{l}$: number of operative bikes in $l$ when leaving the i-th visit.

    * –

$w_{i}^{l}$: number of damaged bikes in $l$ when leaving the i-th visit.

Objective Function:

$\text{Min }\sum_{v\in V_{spl}}(d_{v}-\sum_{l\in\overline{L}}\sum_{i\in
I^{l}_{v}}x_{i}^{l})-\sum_{v\in
V_{def}}(d_{v}-\sum_{l\in\overline{L}}\sum_{i\in
I^{l}_{v}}x_{i}^{l})+\sum_{v\in
V_{dam}}(a_{v}-\sum_{l\in\overline{L}}\sum_{i\in I^{l}_{v}}y_{i}^{l})$ (5)

s.t.:

$\sum_{i=1}^{j}(x_{i}^{l}+y_{i}^{l})\leq k^{l}\qquad\forall
l\in\overline{L},j=1,\ldots,n^{l}-1$ (6) $\sum_{i=1}^{j}x_{i}^{l}\geq
0\qquad\forall l\in\overline{L},j=1,\ldots,n^{l}-1$ (7)
$x_{n^{l}}^{l}=-\sum_{i=1}^{n^{l}-1}x_{i}^{l}\qquad\forall l\in\overline{L}$
(8) $\sum_{i=1}^{j}y_{i}^{l}=0\qquad\forall l\in\overline{L},\forall j\in
I^{l}_{0}$ (9) $\sum_{l\in\overline{L}}\sum_{i\in I^{l}_{v}}x^{l}_{i}\leq
d_{v}\qquad\forall v\in V_{spl}$ (10) $\sum_{l\in\overline{L}}\sum_{{i\in
I^{l}_{v}}}x^{l}_{i}\geq d_{v}\qquad\forall v\in V_{def}$ (11)
$\sum_{l\in\overline{L}}\sum_{{i\in I^{l}_{v}}}y^{l}_{i}\leq
a_{v}\qquad\forall v\in V_{dam}$ (12) $\sum_{l\in\overline{L}}w^{l}_{0}\leq
p_{o}$ (13) $x^{l}_{j}\leq w^{l}_{0}-\sum_{{i\in
I^{l}_{0},i<j}}x^{l}_{i}\qquad\forall l\in\overline{L},\forall{j\in
I^{l}_{0}}$ (14) ${x^{l}_{i}=0\qquad\forall l\in\overline{L},\forall v\in
V_{bal},\forall i\in I^{l}_{v}}$ (15) ${y^{l}_{i}=0\qquad\forall
l\in\overline{L},\forall v\in V\backslash V_{dam},\forall i\in I^{l}_{v}}$
(16) $x^{l}_{i}\in\mathbb{Z_{+}}\qquad\forall l\in\overline{L},\forall{v\in
V_{spl},\forall i\in I^{l}_{v}}$ (17) $x^{l}_{i}\in\mathbb{Z_{+}}\qquad\forall
l\in\overline{L},\forall{v\in V_{def},\forall i\in I^{l}_{v}}$ (18)
$y^{l}_{i}\in\mathbb{Z_{+}}\qquad\forall l\in\overline{L},\forall{v\in
V_{dam},\forall i\in I^{l}_{v}}$ (19)
${y^{l}_{i}\in\mathbb{Z_{+}}\qquad\forall l\in\overline{L},\forall i\in
I^{l}_{0}}$ (20) $w^{l}_{0}\in\mathbb{Z_{+}}\qquad\forall l\in\overline{L}$
(21) $x^{l}_{i}\in\mathbb{R}\qquad\forall l\in\overline{L},{\forall i\in
I^{l}_{0}}$ (22)

The objective function minimizes the total imbalance of the stations and the
number of damaged bikes that have not been collected from the stations.
Constraints (6-7) guarantee that the number of operative bikes and the total
number of bikes on the vehicle is non-negative and below capacity,
respectively, at each visit. Constraints (8) ensure that all operative bikes
are unloaded at the end of each route. Constraints (9) guarantee that all
damaged bikes are unloaded at each visit to the depot. Constraints (10-12)
limit the number of bikes that can be managed in the stations. Constraints
(13) limit the number of operative bikes that can be taken from the depot by
all the vehicles, and constraints (14) control the number of operative bikes
that can be taken in each visit to the depot. Finally, constraints (15-22)
define the domain of the variables.

##  7 Computational Experiments

The computational analysis to assess the performance of our algorithm is
structured as follows: We describe the instances based on real-world data used
for testing and introduce the parameters information used in our solution
method. Then, we evaluate the impact of the route construction parameters on
the best solutions found. Finally, we present a comparative study with another
SBRP variant that has been more extensively studied in the literature.

We evaluated the performance of our algorithms using 136 instances,
categorized into two groups: Palma and Wien.

The first set comprises instances from the Bike-Sharing System in Palma de
Mallorca, Spain, as initially proposed in [1]. Each instance includes 28
stations and one depot, with an initial inventory of 10 operative bikes,
represented as $p_{0}=10$. Additionally, two fleet sizes (2 and 3 vehicles
with a capacity of $k^{l}=20$) and two variations of maximum time (2 and 4
hours) were considered. This set consists of two instances in each group,
totaling 56 instances.

The second set was adapted from [26], with modifications to align with our
problem by randomly substituting some operational bikes in the stations with
damaged bikes. These instances involve 20, 30, 60, and 90 stations and one
depot (with no initial inventory, i.e., $p_{0}=0$). For this set, two values
for the maximum time (4 and 8 hours) and three fleet sizes (2, 3, and 5
vehicles with a capacity of $k^{l}=20$) were considered. Each group has five
instances, making a total of 80 instances in this set.

All algorithms were implemented in C++ and executed on a PC with an Intel(R)
Core(TM) i5-4200 CPU, operating at 1.60 GHz, and equipped with 4.00 GB of RAM.
Throughout the experiments, only a single thread was utilized. The integer
programming model described in Section 6 was resolved using IBM ILOG CPLEX
20.0.

Our experimentation evaluated the parameters: $MaxIter=500$, $\theta$ with
values 0.3, 0.5, and 0.8, and $\mu$ with values 1.0, 1.5, and 2.0. The scaling
factors in the objective function described in Section 3 were set to
$\gamma_{d}=\gamma_{a}=\gamma_{t}=1$. By employing these factors, enhancing
the system balance and collecting damaged bikes will consistently have a
greater impact on the objective value than reducing the total time of the
routes.

In our experimentation, first we independently assessed the impact of the
route construction parameters $\theta$ and $\mu$ on the best solutions found.

Table 2 displays the average results for each group of cases. The first two
columns show the route construction parameters $\theta$ and $\mu$,
respectively. The subsequent columns present the instance sets from Palma and
Wien, showing the average values of the objective function ($O.F$), the
average number of iterations needed to achieve the best solution ($Iter$), and
the time of ($CPU$) in seconds required to obtain those solutions.

Table 2: Average results of the route construction parameters $\theta$ and $\mu$. $\theta$ | $\mu$ | $O.F_{Palma}$ | $Iter_{Palma}$ | $CPU_{Palma}$ | $O.F_{Wien}$ | $Iter_{Wien}$ | $CPU_{Wien}$
---|---|---|---|---|---|---|---
0.3 | 1 | 0.745 | 133.21 | 1.65 | 1.010 | 229.56 | 1.14
0.3 | 1.5 | 0.745 | 133.21 | 3.22 | 1.010 | 235.24 | 1.62
0.3 | 2 | 0.745 | 133.21 | 3.30 | 1.011 | 232.61 | 0.97
0.5 | 1 | 0.748 | 152.07 | 3.34 | 0.998 | 238.09 | 2.36
0.5 | 1.5 | 0.748 | 147.79 | 1.32 | 0.998 | 240.24 | 3.05
0.5 | 2 | 0.748 | 147.79 | 4.09 | 0.997 | 249.09 | 3.07
0.8 | 1 | 0.755 | 129.80 | 2.53 | 0.992 | 212.25 | 4.33
0.8 | 1.5 | 0.755 | 129.80 | 3.57 | 0.992 | 213.28 | 3.63
0.8 | 2 | 0.755 | 129.80 | 1.12 | 0.980 | 215.90 | 4.27

Table 2 displays the outcomes, revealing that, on average, the parameter
$\theta=0.3$ consistently yields better solutions for the Palma instances,
irrespective of the $\mu$ value used. On the other hand, for the Wien
instances, the optimal parameters for achieving the best solutions, on
average, are $\theta=0.8$ and $\mu=2$. Subsequently, using these identified
best parameters, we evaluated the 136 instances.

For the Palma instances, our method successfully achieved complete station
balancing in 96.9% of cases and efficiently collected all damaged bikes. The
average CPU time for this set was 2.09 seconds. Similar favorable outcomes
were observed for instances in Wien with 20 stations, where achieved complete
station balancing in 95.7%. However, for instances with 30-90 stations in Wien
posed more challenges. In these cases, nearly all vehicles were utilized, and
in many instances, the solution could only fulfill some tasks, specifically
achieving complete station balancing and retrieving all damaged bikes. We
achieved complete station balancing in 62.35%. Notably, improvements were
observed with an increase in the number of vehicles or the maximum time $T$.
The average CPU time required for this group (30-90 stations) was 2.65
seconds.

Finally, we compare the performance of our solution methodology with a variant
presented in the study by Rainer-Harbach et al. [26]. These instances are
based on the Bike-Sharing System (BSS) of Vienna, Austria, and include 10 and
20 stations with one depot. For this set, three values for the maximum time
(2, 4, and 8 hours) and three fleet sizes (1, 2, and 3 vehicles) were
considered. Each instance set uses a unique combination of $|V|,|L|,T$ and
contains 30 cases, resulting in a total of 12 sets and 360 instances.

To compare our approach with the variant proposed in [26], we need to align
the characteristics of our problem with theirs. We believe that the features
of our problem (described in Section 3) can be considered a general variant of
the BRP compared to those found in the literature. Thus, our framework can
accommodate the study of other BRP variants, including the one proposed in
[26]. To do this, we may need to simplify or relax specific characteristics or
assumptions of our problem, particularly regarding the nodes, the routes, and
the objective function.

After adapting our algorithm to the variant proposed in [26], we apply it to
the original instances mentioned earlier. Table 3 presents the average results
for each group of cases. The table first displays the results of the MIP model
from [26], including the mean upper bounds ($\overline{ub}$), the mean lower
bounds ($\overline{lb}$) and the median total run times ($t_{MIP}(s)$).
Second, it shows the best-known solutions ($\overline{bks}$) obtained on
average by Rainer-Harbach et al. [26]. Third, it presents the average values
of the objective function ($\overline{obj}$) generated by our proposed
solution methodology from Section 4. Fourth, it indicates the gap between
$\overline{obj}$ and the mean lower bounds $\overline{lb}$ obtained in the MIP
model. Finally, it demonstrates the difference between $\overline{obj}$ and
$\overline{bks}$ and the mean runtime ($CPU_{obj}(s)$).

Table 3: Average results from 12 instances for each group of $|V|\in\\{10,20\\}$. $|V|$ | $|L|$ | $T(h)$ | $\overline{ub}$ | $\overline{lb}$ | $t_{MIP}(s)$ | $\overline{bks}$ | $\overline{obj}$ | gap | dif | $CPU_{obj}(s)$
---|---|---|---|---|---|---|---|---|---|---
10 | 1 | 2 | 27.80143 | 27.80143 | 3.0 | 27.86810 | 28.00143 | 0.00719 | 0.13333 | 0.22
10 | 1 | 4 | 3.46948 | 0.17536 | 3.600 | 3.50949 | 3.53615 | 19.16510 | 0.02666 | 0.29
10 | 1 | 8 | 0.00322 | 0.00260 | 3.600 | 0.00319 | 0.00320 | 0.22932 | 0.00000 | 0.18
10 | 2 | 2 | 9.13607 | 8.80436 | 897,5 | 9.26937 | 9.32270 | 0.05887 | 0.05333 | 1.38
10 | 2 | 4 | 0.00341 | 0.00326 | 3.600 | 0.00339 | 0.00339 | 0.04047 | 0.00001 | 0.78
10 | 2 | 8 | 0.00324 | 0.00315 | 3.600 | 0.00319 | 0.00320 | 0.01396 | 0.00000 | 0.70
20 | 2 | 2 | 52.46973 | 29.77982 | 3.600 | 51.52307 | 51.64306 | 0.73416 | 0.11999 | 0.46
20 | 2 | 4 | 16.00568 | 0.00387 | 3.600 | 5.24584 | 5.29917 | 1367.23341 | 0.05333 | 0.28
20 | 2 | 8 | 0.14154 | 0.00350 | 3.600 | 0.00638 | 0.00638 | 0.82338 | 0.00000 | 0.59
20 | 3 | 2 | 34.73765 | 2.08780 | 3.600 | 28.75112 | 28.96445 | 12.87320 | 0.21333 | 1.73
20 | 3 | 4 | 0.94106 | 0.00536 | 3.600 | 0.00670 | 0.00670 | 0.25089 | 0.00001 | 1.54
20 | 3 | 8 | 8.14200 | 0.00344 | 3.600 | 0.00638 | 0.00638 | 0.85440 | 0.00001 | 1.13

For the instance groups where the MIP showed small gaps between upper and
lower bounds, our solution method found solutions with equal or slightly
different objective values.

The results in the $\overline{bks}$ column of Table 3 represent the solutions,
on average, with the best objective values among the four variants proposed in
[26]. We observe a clear tendency that our solution method performs similarly
to the variants proposed in [26] in most instances.

It is important to note that the variants proposed by [26] are specifically
designed to solve their problem. At the same time, our approach needs to be
adapted beforehand because our solution methods were initially developed for
solving the BRP variant described in Section 3. Nevertheless, we achieved
similar results in 83.3% of the instances tested.

##  8 Concluding Remarks

This paper introduces a specific instance of the Static Bike-sharing
Repositioning Problem (SBRP). It incorporates new considerations for existing
SBRP to improve their realism, such as operational and damaged bikes, a
heterogeneous fleet, and multiple visits between stations and the depot.

To solve this problem, we propose a matheuristic approach based on a
randomized multi-start algorithm integrated with integer programming,
incorporating various strategies and route construction parameters that, in
combination, contribute to improving the quality of the solutions found.

To our knowledge, there are currently no previous works that allow us to
compare the quality of the solutions obtained. However, we are developing a
method to calculate a lower bound that allows us to evaluate the quality of
the solutions.

To demonstrate the applicability of our approach, we adapted our algorithm to
a more straightforward problem studied in the literature, achieving
competitive results. This suggests that the characteristics of our problem are
a general variant of the BRP compared to those described in existing
literature.

We proposed an integer programming model for optimizing the number of
operative and damaged bikes that will be moved between stations and/or the
depot (loading instructions). This model can be solved very quickly with IBM
ILOG CPLEX for the size of the instances we have tried.

## References

  * [1] Alvarez-Valdes, R., Belenguer, J.M., Benavent, E., Bermudez, J.D., Muñoz, F., Vercher, E., Verdejo, F.: Optimizing the level of service quality of a bike-sharing system. Omega 62, 163–175 (2016). https://doi.org/10.1016/j.omega.2015.09.007
  * [2] Benchimol, M., Benchimol, P., Chappert, B., la Taille, A.D., Laroche, F., Meunier, F., Robinet, L.: Balancing the stations of a self service bike hire system. RAIRO - Operations Research 45, 37–61 (2011). https://doi.org/10.1051/ro/2011102
  * [3] Casazza, M.: Exactly solving the split pickup and split delivery vehicle routing problem on a bike-sharing system (2016), http://hal.upmc.fr/hal-01304433.
  * [4] Chemla, D., Meunier, F., Calvo, R.W.: Bike sharing systems: solving the static rebalancing problem. Discrete Optimization 10, 120–146 (2013). https://doi.org/10.1016/j.disopt.2012.11.005
  * [5] Cruz, F., Subramanian, A., Bruck, B.P., Iori, M.: A heuristic algorithm for a single vehicle static bike sharing rebalancing problem. Computers & Operations Research 79, 19–33 (2017). https://doi.org/10.1016/j.cor.2016.09.025
  * [6] Dell’Amico, M., Iori, M., Novellani, S., Stutzle, T.: A destroy and repair algorithm for the bike sharing rebalancing problem. Computers & Operations Research 71, 149–162 (2016). https://doi.org/10.1016/j.cor.2016.01.011
  * [7] Du, M., Cheng, L., Li, X., Tang, F.: Static rebalancing optimization with considering the collection of malfunctioning bikes in free-floating bike sharing system. Transportation Research Part E: Logistics and Transportation Review 141, 102012 (9 2020). https://doi.org/10.1016/j.tre.2020.102012
  * [8] Espegren, H.M., Kristianslund, J., Andersson, H., Fagerholt, K.: The static bicycle repositioning problem - literature survey and new formulation, pp. 337–351. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44896-1
  * [9] Forma, I.A., Raviv, T., Tzur, M.: A 3-step math heuristic for the static repositioning problem in bike-sharing systems. Transportation Research Part B: Methodological 71, 230–247 (2015). https://doi.org/10.1016/j.trb.2014.10.003
  * [10] Gaspero, L.D., Rendl, A., Urli, T.: Constraint-based approaches for balancing bike sharing systems, pp. 758–773. Springer, Berlin, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40627-0
  * [11] Gaspero, L.D., Rendl, A., Urli, T.: A hybrid ACO+CP for balancing bicycle sharing systems, pp. 198–212. Springer, Berlin, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38516-2
  * [12] Gaspero, L.D., Rendl, A., Urli, T.: Balancing bike sharing systems with constraint programming. Constraints 21, 318–348 (2016). https://doi.org/10.1007/s10601-015-9182-1
  * [13] Ho, S.C., Szeto, W.Y.: Solving a static repositioning problem in bike-sharing systems using iterated tabu search. Transportation Research Part E: Logistics and Transportation Review 69, 180–198 (2014). https://doi.org/10.1016/j.tre.2014.05.017
  * [14] Ho, S.C., Szeto, W.Y.: A hybrid large neighborhood search for the static multi-vehicle bike-repositioning problem. Transportation Research Part B: Methodological 95, 340–363 (2017). https://doi.org/10.1016/j.trb.2016.11.003
  * [15] Kadri, A.A., Kacem, I., Labadi, K.: A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems. Computers & Industrial Engineering 95, 41–52 (2016). https://doi.org/10.1016/j.cie.2016.02.002
  * [16] Kinable, J.: A reservoir balancing constraint with applications to bike-sharing, pp. 216–228. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-33954-2
  * [17] Kloimullner, C., Raidl, G.R.: Full-load route planning for balancing bike sharing systems by logic-based benders decomposition. Networks 69, 270–289 (2017). https://doi.org/10.1002/net.21736
  * [18] Lahoorpoor, B., Faroqi, H., Sadeghi-Niaraki, A., Choi, S.M.: Spatial cluster-based model for static rebalancing bike sharing problem. Sustainability 11, 3205 (6 2019). https://doi.org/10.3390/su11113205
  * [19] Li, Y., Szeto, W.Y., Long, J., Shui, C.S.: A multiple type bike repositioning problem. Transportation Research Part B: Methodological 90, 263–278 (2016). https://doi.org/10.1016/j.trb.2016.05.010
  * [20] Lv, C., Zhang, C., Lian, K., Ren, Y., Meng, L.: A hybrid algorithm for the static bike-sharing re-positioning problem based on an effective clustering strategy. Transportation Research Part B: Methodological 140, 1–21 (10 2020). https://doi.org/10.1016/j.trb.2020.07.004
  * [21] Pal, A., Zhang, Y.: Free-floating bike sharing: solving real-life large-scale static rebalancing problems. Transportation Research Part C: Emerging Technologies 80, 92–116 (2017). https://doi.org/10.13140/RG.2.1.1727.1766
  * [22] Papazek, P., Kloimullner, C., Hu, B., Raidl, G.R.: Balancing bicycle sharing systems: an analysis of path relinking and recombination within a GRASP hybrid, pp. 792–801. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10762-2
  * [23] Papazek, P., Raidl, G.R., Rainer-Harbach, M., Hu, B.: A PILOT/VND/GRASP hybrid for the static balancing of public bicycle sharing systems, pp. 372–379. Springer, Berlin, Heidelberg (2013). https://doi.org/10.1007/978-3-642-53856-8
  * [24] Raidl, G.R., Hu, B., Rainer-Harbach, M., Papazek, P.: Balancing bicycle sharing systems: improving a VNS by efficiently determining optimal loading operations, pp. 130–143. Springer, Berlin, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38516-2
  * [25] Rainer-Harbach, M., Papazek, P., Hu, B., Raidl, G.R.: Balancing bicycle sharing systems: a variable neighborhood search approach, pp. 121–132. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37198-1
  * [26] Rainer-Harbach, M., Papazek, P., Raidl, G.R., Hu, B., Kloimullner, C.: Pilot, grasp, and vns approaches for the static balancing of bicycle sharing systems. Journal of Global Optimization 63, 597–629 (2015). https://doi.org/10.1007/s10898-014-0147-5
  * [27] Raviv, T., Tzur, M., Forma, I.A.: Static repositioning in a bike-sharing system: models and solution approaches. EURO Journal on Transportation and Logistics 2, 187–229 (2013). https://doi.org/10.1007/s13676-012-0017-6
  * [28] Schuijbroek, J., Hampshire, R.C., van Hoeve, W.J.: Inventory rebalancing and vehicle routing in bike sharing systems. European Journal of Operational Research 257, 992–1004 (2017). https://doi.org/10.1016/j.ejor.2016.08.029
  * [29] Szeto, W.Y., Liu, Y., Ho, S.C.: Chemical reaction optimization for solving a static bike repositioning problem. Transportation Research Part D: Transport and Environment 47, 104–135 (2016). https://doi.org/10.1016/j.trd.2016.05.005
  * [30] Tang, Q., Fu, Z., Zhang, D., Qiu, M., Li, M.: An improved iterated local search algorithm for the static partial repositioning problem in bike-sharing system. Journal of Advanced Transportation 2020, 1–15 (11 2020). https://doi.org/10.1155/2020/3040567
  * [31] Wang, Y., Szeto, W.: Static green repositioning in bike sharing systems with broken bikes. Transportation Research Part D: Transport and Environment 65, 438–457 (12 2018). https://doi.org/10.1016/j.trd.2018.09.016
  * [32] Zhang, S., Xiang, G., Huang, Z.: Bike-sharing static rebalancing by considering the collection of bicycles in need of repair. Journal of Advanced Transportation 2018, 1–18 (9 2018). https://doi.org/10.1155/2018/8086378


# Energy Efficient Hadamard Neural Networks

T. Ceren Deveci, Serdar Cakir and A. Enis Cetin

(April 2018)

###### Abstract

Deep learning has made significant improvements at many image processing tasks
in recent years, such as image classification, object recognition and object
detection. Convolutional neural networks (CNN), which is a popular deep
learning architecture designed to process data in multiple array form, show
great success to almost all detection & recognition problems and computer
vision tasks. However, the number of parameters in a CNN is too high such that
the computers require more energy and larger memory size. In order to solve
this problem, we propose a novel energy efficient model Binary Weight and
Hadamard-transformed Image Network (BWHIN), which is a combination of Binary
Weight Network (BWN) and Hadamard-transformed Image Network (HIN). It is
observed that energy efficiency is achieved with a slight sacrifice at
classification accuracy. Among all energy efficient networks, our novel
ensemble model outperforms other energy efficient models.

##  1 Introduction

In the recent years, artificial neural networks (ANN) have become very popular
amongst researchers due to their great success on image classification,
feature extraction, segmentation, object recognition and detection [1]. Deep
learning is a more sophisticated and particular form of machine learning,
which enables the user to form complex models which are composed of multiple
hidden layers. Deep learning methods have enhanced the state-of-the-art
performance in object recognition & detection and computer vision tasks. Deep
learning is also advantageous for processing raw data such that it can
automatically find a suitable representation for detection or classification
[2].

Convolutional neural network (CNN) is a specific deep learning architecture
for processing data which is composed of multiple arrays. Images can be a good
example of input to CNN with its 2D grid of pixels. Convolutional Neural
Networks have become popular with the introduction of its modern version
LeNet-5 for the recognition of handwritten numbers [3]. Besides, AlexNet, the
winner of ILSVRC object recognition challenge in 2012, aroused both commercial
and scientific interest in CNN and it is the main reason of the intense
popularity of CNN architectures for deep learning applications [4]. The usage
of CNN in AlexNet obtained remarkable results such that the network halved the
error rate of its previous competitors. Thanks to this great achievement, CNN
is the most preferred approach for most detection and recognition problems and
computer vision tasks.

Although CNNs are suitable for efficient hardware implementations such as in
GPUs or FPGAs, the training is computationally expensive due to the high
number of parameters. As a result, excessive amount of energy consumption and
memory usage make the implementation of neural networks ineffective. According
to [5], especially matrix multiplications at the layers of a neural network
consume too much energy compared to addition or activation function and
becomes a major problem for mobile devices with limited batteries. As a
result, replacing the multiplication operation becomes the main concern in
order to achieve energy efficiency.

Many solutions are proposed in order to handle the energy efficiency problem.
An energy efficient $\ell_{1}$-norm based operator is introduced in [6]. This
multiplier-less operator is first used in image processing tasks such as
cancer cell detection and licence plate recognition in [7, 8]. Multiplication-
free neural networks (MFNN) based on this operator are studied in [9, 10, 11].
This operator achieved promising performance especially at image
classification on MNIST dataset with multi-layer perceptron (MLP) models [10].
Han et al. reduces both the computation and storage in three steps: First, the
network is trained to learn the important connections. Then, the redundant
connections are discarded for a sparser network. Finally, the remaining
network is retrained [5]. Using neuromorphic processors with its special chip
architecture is another solution for energy efficiency [12]. In order to
improve energy consumption, Sarwar et al. exploits the error resiliency of
artificial neurons and approximates the multiplication operation and defines a
Multiplier-less Artificial Neuron (MAN) by using Alphabet Set Multiplier
(ASM). In ASM, the multiplication is approximated as shifting and adding in
bitwise manner with some previously defined alphabets [13]. Binary Weight
Networks are energy efficient neural networks whose filters at the
convolutional layers are approximated as binary weights. With these binary
weights, convolution operation can be computed only with addition and
subtraction [14]. There is also a computationally inexpensive method called
distillation [15]. A very large network or an emsemble model is first trained
and transfers its knowledge to a much smaller, distilled network. Using this
small and compact model is much more advantageous in mobile devices in terms
of speed and memory size. This method shows promising results at image
processing tasks such as facial expression recognition [16].

In this study, an energy-efficient neural network framework based on Binary
Weight Network (BWN) [14] and Hadamard Transform is developed. The weights at
the convolutional layers of the BWN are approximated to binary values, $+1$ or
$-1$ [14]. Instead of utilizing the original images as network inputs, the
network is modified to use compressed images. This network is called Hadamard-
transformed Image Network (HIN). Since Hadamard transform is implemented by
Fast Walsh-Hadamard Transform algorithm which requires only addition or
subtraction [17], the HIN network is energy efficient. Our main contribution
is the combination of BWN and HIN models: Binary Weight and Hadamard-
transformed Image Network (BWHIN). The combination is carried out after the
energy efficient layers, i.e. convolutional layers with two different
averaging techniques. All of the energy efficient models are also examined
with different CNN architectures. One of them (ConvoPool-CNN) contains pooling
layers along with convolutional layers, while the other (All-CNN [18]) uses
strided convolution instead of pooling layer [18]. We analyze the performance
of the models on two famous image datasets MNIST and CIFAR-10. While working
on MNIST, we also study the effects of certain hyperparameters on the
classification accuracy of energy efficient neural networks.

##  2 Methodology

Firstly, we investigate the efficiency BWN proposed in [14] which approximates
the weights to binary values. Similar to BWN, we propose a Hadamard-
transformed Image Network (HIN) which uses the Hadamard-transformed images
with binarized weights. Lastly, a combined network is introduced and its
performance is compared with BWN and HIN frameworks.

###  2.1 Binary Weight Networks (BWN)

Binary-Weight Network (BWN) is proposed in [14] as an efficient approximation
to standard convolutional neural networks. In BWNs, the filters, i.e. weights
of the CNN are approximated to binary values $+1$ and $-1$. While a
conventional convolutional neural network needs multiplication, addition and
subtraction for convolution operation, convolution with binary weights can be
estimated by only addition and subtraction.

Convolution operation can be approximated as
$\bm{I}\ast\bm{W}\approx(\bm{I}\oplus\bm{B})\alpha$ where $\bm{I}$ is the
input tensor, $\bm{W}$ is the weight (filter), $\bm{B}$ is the binary weight
tensor which has the same size with $\bm{W}$ and $\alpha\in\mathbb{R}^{+}$ is
the scaling factor such that $\bm{W}\approx\alpha\bm{B}$. $\oplus$ operation
indicates convolution only with addition and subtraction. Since the weight
values are only $+1$ and $-1$, convolution operation can be implemented in a
multiplier-less manner. After solving an optimization problem to estimate
$\bm{W}$, $\bm{B}$ and $\alpha$ is found as:

$\bm{B}=sign(\bm{W})$ (1)

$\alpha=\dfrac{\sum|\bm{W}_{i}|}{n}=\dfrac{1}{n}||\bm{W}||_{\ell 1}$ (2)

In Equation 2, $n=c\times w\times h$ where $c$ is the channel, $h$ is the
height and $w$ is the width of weight tensor $\bm{W}$, and of $\bm{B}$ as
well. Equations 1 and 2 show that binary weight filter is simply the sign of
weight values and scaling factor is the average of absolute weight values.
While training a CNN with binary weights, the weights are only binarized in
forward pass and back propagation steps of the training. At the parameter-
update stage, the real-valued weights (not binarized) are used. Another
significant point about this network is that convolutional filters here don’t
have bias terms, and this convolution approximation is only held in
convolutional layers. Fully connected layers still do have bias terms and
standard multiplication.

###  2.2 Hadamard-transformed Image Networks (HIN)

In the literature, transform domain features are also used as input data in
deep learning structures. Although feature extraction requires extra
computation time and energy, transform domain features as input to the
convolutional neural networks can be preferred due to simpler implementation,
effective computation and improved model accuracy. Discrete Cosine Transform
(DCT) domain data as the input data can outperform the state-of-the-art
results as shown in [19]. Wu et al. uses DCT because JPEG, MPEG video coding
standards are based on DCT. In this study, we also use transform domain
features to feed them into the our CNN model. This network model is called
Hadamard-transformed Image Networks (HIN).

Compressed domain data is also used as input in deep learning structures.
Discrete Cosine Transform (DCT) domain data as the input data can outperform
the state-of-the-art results as shown in [19]. Compressed domain video frames
as input to the convolutional neural networks are preferred rather than RGB
frames, since data decompression requires extra computation time and energy.
As a result; simpler implementation, effective computation and improved model
accuracy are achieved. Wu et al. uses DCT because JPEG, MPEG video coding
standards are based on DCT. In this study, we also use transform domain
features to feed them into the our CNN model. This network model is called
Hadamard-transformed Image Networks (HIN).

Hadamard Transform, also called as Hadamard-ordered Walsh-Hadamard Transform,
is an image transformation technique which is also used to compress images
[20]. Hadamard Transform coefficients consists of binary values +1 and -1.
Thus, Hadamard Transform can be considered as an efficient alternative to the
other image transforms such that it can be implemented without any
multiplication and division [21].

1-D Hadamard Transform is expressed by Equation 3. In this formula, $g(x)$ is
the elements of 1-D array $\underline{g}$ and $b_{i}(x)$ is the $i^{th}$ bit
(from right to left) in the binary representation of $x$. The scaling factor
$(\dfrac{1}{\sqrt{2}})^{m}$ is used to make the Hadamard matrix orthonormal,
hence it is mostly kept in the calculations.

$T(u)=(\dfrac{1}{\sqrt{2}})^{m}\sum_{x=0}^{2^{m}-1}g(x)(-1)^{\sum\limits_{i=0}^{m-1}b_{i}(x)b_{m-1-i}(u)}$
(3)

2-D Hadamard Transform is a straightforward extension of 1-D Hadamard
Transform [22]:

$T(u,v)=(\dfrac{1}{2})^{m}\sum_{x=0}^{2^{m}-1}\sum_{y=0}^{2^{m}-1}g(x,y)(-1)^{\sum\limits_{i=0}^{m-1}(b_{i}(x)p_{i}(u)+b_{i}(y)p_{i}(v))}$
(4)

In Equation 4, $p_{i}(u)$ is computed using:

$\begin{split}p_{0}(u)&=b_{m-1}(u)\\\ p_{1}(u)&=b_{m-1}(u)+b_{m-2}(u)\\\
\vdots\\\ p_{m-1}(u)&=b_{1}(u)+b_{0}(u)\\\ \end{split}$ (5)

2-D Hadamard Transform is separable and symmetric, hence it can be implemented
by using row-column or column-row passes of the corresponding 1-D transform.

There is an algorithm called Fast Walsh-Hadamard Transform ($FWTH_{h}$) which
requires less storage and is fast and efficient to compute Hadamard Transform
[17]. The implementation of this algorithm can be realized by only addition
and subtraction operations which can be summarized in a butterfly structure.
While the complexity of Hadamard Transform is $O(N^{2})$, complexity of fast
algorithm is $O(Nlog_{2}N)$ where $N=2^{m}$.If the length of the input 1-D
array is less than a power of 2, the array is padded with zeros up to the next
greater power of two. Since 2-D Hadamard Transform is separable, we can treat
columns and rows of the 2-D array as separate 1-D arrays.

Training of HIN is similar to the training of BWN; the only difference is that
the input images are Hadamard-transformed as explained above. Training
proceeds as explained in Section 2.1, but at the beginning Hadamard-
transformed input data is fed in to the network instead. As in BWN, binarized
weights are used and no bias terms are defined.

###  2.3 Combination of Models: Binary Weight & Hadamard Transformed Image
Network (BWHIN)

Combination of the neural networks can improve the performance of the neural
networks by a few percent. Since combining the neural networks reduces the
test error and tends to keep the training error the same, it can be viewed as
a regularization technique. One of the popular techniques of the combination
is called “model ensembles” which combines the multiple hypotheses that
explain the same training data [23, 24]. In model ensembles, the error made by
averaging prediction of all models in the ensemble decreases linearly with the
ensemble size, i.e. the number of models in the ensemble. However, since they
need longer time and higher amount of memory to evaluate on test example, we
try to avoid increasing the ensemble size for energy efficiency. In multi-
network frameworks, different networks are trained independently and
separately before performing a combination layer. Bilinear CNNs [25] is a good
example for such combination models. In bilinear CNN, there are two sub-
networks which are standard CNN units. After these CNN units, the image
regions which extract features are combined with a matrix dot product and then
average pooled to obtain the bilinear vector. In order to perform these
operations properly, those image regions have to be of the same size. This
vector is passed through a fully-connected and softmax layer to obtain class
predictions.

Our approach to combine BWN and HIN is quite similar to Bilinear-CNN, but
simpler. After convolutional, ReLU and pooling layers, the output tensor is
reshaped for fully connected layer as a 1-D tensor. Afterwards, these same
sized 1-D tensors of each sub-network will be averaged instead of dot product.
Since multiplication consumes power, dot product is avoided and averaging is
preferred. Two averaging methods are used: Simple averaging and weighted
averaging. [26]. Simple averaging is the conventional averaging technique
which calculates the output by averaging the sum of outputs from each ensemble
member. Weighted averaging technique assigns a weight to each ensemble member
and calculated the output by taking these weights into account. The total
weight of each ensemble is 1. In order to implement this technique, we define
a random number which behaves like a weight. If $YY_{binary}$ is defined as
the 1-D tensor of BWN and $YY_{hadamard}$ is the 1-D tensor of HIN, the
weighted averaging is defines as follows:

$YY_{combined}=(W_{combined}\times YY_{binary})+((1-W_{combined}))\times
YY_{hadamard}$ (6)

where $W_{combined}$ is initialized according to truncated normal distribution
which can only take values in $\left[0,1\right]$. After the averaging
operation, the resultant 1-D tensor is processed through a fully connected and
softmax layers. The architecture of our combined network Binary Weight &
Hadamard-Transformed Image Network (BWHIN) is summarized in Figure 1.

Figure 1: Our approach to combine BWN and HIN: The architecture of BWHIN [25].

By looking at Figure 1, one can observe that the combination is applied after
the convolutional layers of each network, which are energy efficient layers.
With this combination model, we still want to maintain the energy efficiency
of the entire network.

##  3 Experimental Studies

###  3.1 Image Datasets and Implementation

We analyze our proposed algorithm on two well-known datasets: MNIST and
CIFAR-10. The MNIST (Modified National Institute of Standards and Technology)
database of handwritten digit images is a very popular digit database for
implementing learning techniques and pattern recognition methods [27]. It
contains 60,000 training images and 10,000 test images in ten classes. These
black and white images are of size $28\times 28$ pixels.

CIFAR-10 (Canadian Institute for Advanced Research-10) is also a popular
dataset used for image classification tasks [28]. It consists of 50,000
training and 10,000 test images. These images, which are of size $32\times
32$, are collected in ten different classes of objects (airplane, automobile,
bird, cat, deer, dog, frog, horse, ship, truck).

Tensorflow is chosen to implement all of the deep neural networks for this
work. Tensorflow is an open-source software library for machine intelligence,
which is developed by Google Brain Team in Python language [29]. Since our
main purpose is to investigate the energy efficieny of the proposed neural
network models, simple architectures are chosen and no pretraining such as
feature extraction or unsupervised learning techniques is performed. Images in
both datasets are normalized such that the pixel values are in
$\left[0,1\right]$. All experiments are carried out on a single GPU, which is
NVIDIA GeForce 940M. Thanks to our CUDA-enabled GPU, we are able to run
Tensorflow with GPU support and we achieve faster computation.

###  3.2 Neural Network Architecture and Hyperparamaters

####  3.2.1 CNN Architectures

In order to implement the proposed networks and analyze their performances,
two different CNN architectures are utilized. First type of architecture for
MNIST database is very similar to LeNet-5 in [3] with convolutional and
pooling layers. Second architecture is built according to All-Convolutional-
Neural-Network [18] with strided convolution. Strided convolution is that some
positions of the kernel are skipped over in order to reduce the computational
burden while implementing the convolution operation. Strided convolution is
equivalent to downsampling the output of the full convolution function. The
reason is to investigate the effect of the pooling layer and strided
convolution on energy efficiency and test accuracy. Both neural network
architectures used for MNIST are summarized in Table 1.

ConvPool-CNN |  All-CNN
---|---
Input 28$\times$28 gray-scale image
6$\times$6 conv. 6 ReLU |  6$\times$6 conv. 6 ReLU
5$\times$5 conv. 12 ReLU |  5$\times$5 conv. 12 ReLU with stride 2
2$\times$2 max-pooling, stride 2 |
4$\times$4 conv. 24 ReLU |  4$\times$4 conv. 24 ReLU with stride 2
2$\times$2 max-pooling, stride 2 |
Fully connected layer with 200 neurons, dropout
10-way softmax layer
Table 1: Model description of the two architectures for MNIST dataset.

First architecture is built as a [Conv-ReLU-Conv-ReLU-Pool-Conv-ReLU-Pool-FC-
Softmax] structure while second architecture is built as [Conv-ReLU-
StridedConv-ReLU-StridedConv-ReLU-FC-Softmax]. The sizes of three
convolutional layers and 1 fully connected layer are determined as 6, 12, 24
and 200, respectively. These configurations are determined after a large scale
experimentation over the datasets. Both pooling and strided convolutional
operations are used to shrink the input size by a factor of two in order to
reduce the computational and statistical burden on the next layer.

Filter sizes are determined heuristically. Since $5\times 5$ filters are used
in LeNet-5, filter sizes are selected to be close to this size. In order to
preserve the input size for conventional convolutional layers, stride is
chosen as 1 and zero padding is used accordingly. For strided convolutional
layers, stride is 2 to decrease the height and width of the image by a factor
of 2. For non-overlapping max-pooling operation, $2\times 2$ filters with
stride 2 is chosen.

The architectures which are applied to CIFAR-10 dataset are described in Table
2. Since CIFAR-10 dataset has colored and high resolutions images compared to
the images in MNIST, models adapted for higher capacity are preferred. Model
capacity is expanded by increasing both the number of layers and the number of
neurons at the hidden layers. The architecture with pooling layers is built as
[Conv-ReLU-Conv-ReLU-Pool-Conv-ReLU-Conv-ReLU-Pool-FC-Softmax], while all-CNN
architecture is build as [Conv-ReLU-StridedConv-ReLU-Conv-ReLU-StridedConv-
ReLU-FC-Softmax]. Since we want to preserve the energy efficieny as far as
possible, we use more convolutional layers, which can be modified as energy
efficient layers, and only one fully-connected layer. The sizes of these 4
convolutional layers and 1 fully-connected layer are determined as 32, 32, 64,
64, and 512, respectively. The number of neurons in a layer and the filter
sizes are selected empirically. A critical point in CIFAR-10 architectures is
that more dropout is used due to the increased capacity.

ConvPool-CNN |  All-CNN
---|---
Input 32$\times$32 RGB image
3$\times$3 conv. 32 ReLU |  3$\times$3 conv. 32 ReLU
3$\times$3 conv. 32 ReLU |  3$\times$3 conv. 32 ReLU with stride 2
2$\times$2 max-pooling, stride 2 |
Dropout
3$\times$3 conv. 64 ReLU |  3$\times$3 conv. 64 ReLU
3$\times$3 conv. 64 ReLU |  3$\times$3 conv. 64 ReLU with stride 2
2$\times$2 max-pooling, stride 2 |
Dropout
Fully connected layer with 512 neurons, dropout
10-way softmax layer
Table 2: Model description of the two architectures for CIFAR-10 dataset.

Note that the size of an image in the MNIST dataset is altered from $28\times
28\times 1$ to $32\times 32\times 1$ after Hadamard transform. As a result,
the outputs of the BWN and HIN will not compatible in the combined model. In
order to overcome this problem in the MNIST architectures, the filter size in
the first convolutional layer whose input is Hadamard-transformed image is
modified as $5\times 5$ and zero-padding is not used. On the other hand, we
will not have that issue for CIFAR-10 database. Since the width & height of an
image in CIFAR-10 is 32, a power of 2, the size will remain unchanged
($32\times 32\times 3$) after Hadamard transform.

####  3.2.2 Network Hyperparamaters

In order to make a fair comparison, similar methods are used for both networks
and architectures. As optimization method, ADAM is selected as suggested in
[14]. ADAM is an practical optimizer which is fairly robust to the choice of
hyperparameters [23]. As regularization technique, dropout is chosen. In case
of dropout, a neuron is kept active with a fixed probability of $p$
independent of other units. $p$ can be considered as a hyperparameter and it
can be set to a number or determined by cross-validation. Although $p=0.5$ is
a reasonable choice for hidden units, the optimal probability is usually
closer to 1 than to 0.5 [30]. In addition to ReLU layers in convolutional
neural networks, ReLU is also used as the activation function for the fully-
connected layer. ReLU is also an energy efficient function since the
definition function of ReLU $f(x)=max(0,x)$ simply requires a comparison.

Other hyperparameter settings are summarized in Table 3.

|  MNIST |  CIFAR-10
---|---|---
Weight Initialization |  $W\sim\mathcal{N}\mathopen{(}0,0.1\mathclose{)}$ |  Xavier init.
Bias Initialization |  0.1 |  0.1
Mini-batch Size |  100 |  100
Initial Learning Rate |  0.003 |  0.0005
Exponential Decay Rate of Learning Rate |  0.0001 |  $10^{-6}$
Probability of Retention for Dropout, $p$ |  0.75 |  0.75, 0.75, 0.5
Table 3: Hyperparameter settings for different datasets.

###  3.3 Experimental Results

In the experiments, five CNN models (including the standard CNN) with two
different architectures are trained on MNIST and CIFAR-10 database. These CNN
models include the standard CNN, previously studied BWN and our energy
efficient neural networks. The performance of the neural networks is evaluated
based on test accuracies. Networks trained on MNIST dataset has 10000
iterations, while networks of CIFAR-10 dataset are trained in 150000
iterations. This means the number of epochs for MNIST and CIFAR-10 training is
chosen as 17 and 300, respectively. Before learning procedure is performed,
the input images are normalized to the $[0,1]$. The overall test accuracies
and test accuracies corresponding to each number of iterations are presented
in Table 4 and Figure 2, respectively.

| MNIST | CIFAR-10
---|---|---
|  ConvoPool- CNN |  All-CNN |  ConvoPool- CNN |  All-CNN
CNN |  99.48 |  99.31 |  82.64 |  77.32
BWN |  98.88 |  98.37 |  68.72 |  65.36
HIN |  98.32 |  97.84 |  61.36 |  11.76
BWHIN-NormalAvg |  98.79 |  98.40 |  72.10 |  67.70
BWHIN-RandomAvg |  98.96 |  98.61 |  72.65 |  67.30
Table 4: Test accuracy results (in percentage) for CIFAR-10 dataset.

By looking at the results presented in Table 4 and Figure 2, one can observe
that our energy-efficient solution sacrifice the classification performance
slightly in order to achieve a greater energy efficiency. While the proposed
networks almost achieve the state-of-the-art result for MNIST dataset, there
is an considerable accuracy gap between the state-of-the-art results and the
results of the proposed networks. This problem concerning CIFAR-10 dataset can
be solved by modifying the size of the network, since binarized neural
networks may need larger network structures than the networks with real-valued
parameters [31]. As observed from Table 4, it’s clear that our CNN-based
energy efficient neural networks with ConvPool architecture have better
classification results than the All-CNN networks. Although networks with
pooling layer have greater test accuracies, All-CNN can be preferred over
ConvPool-CNN, since they are more energy-efficient. Here, both a convolutional
layer with stride 1 and pooling layer is replaced by a convolutional layer
which has stride greater than 1. Number of multiplications in the
convolutional layer is decreased by a significant amount with strided
convolution. While the downsampling is performed along with full convolution,
a large number of values are already computed in convolutional layer, then
many of these values are discarded with pooling operation. This is
computationally wasteful; it will take more time and use more memory than
strided convolutional layer. If we take the risk of less test accuracy in
order to achieve energy efficiency, strided convolution should be used instead
of pooling. There is also a significant point about All-CNN. If we increase
the capacity of All-CNN by increasing the size of the layers and/or making a
deeper network, image classification can be performed without the loss of
accuracy. In some cases, it may even give better results [18].

(a) MINIST

(b) CIFAR-10

Figure 2: Test accuracy results.

Binary Weight Network is a very robust network to the changes of the
hyperparameters. As seen from Table 4, this model could train the network for
any cases. On the other hand, Hadamard-transformed Image Network is slightly
worse than BWN. The reason could be the slight change in the original
architecture. If Hadamard transform is applied to an image whose width &
height is not a power of 2, size of the image changes such that the width and
height is increased to the next power of 2 of their original values. Hence, if
we want to feed the Hadamard-transformed images to the network as input
images, we may have to modify the architecture of the network. That might be
the reason why HIN has worse performance and is a lossy network than BWN.
Combined models work as expected; they have better test accuracies than their
sub-networks BWN and HIN. When the conventional averaging has the lower test
accuracies than BWN, the random averaging is always better than both BWN and
BWHIN-Normal models. Hence both averaging techniques should be tried and it
should be observed which one has better test accuracies even though the
random-average works for most of the cases. Combined models are also a good
solution to the failure of one sub-network. For example, when HIN is not
trained, BWN compensates this failure and BWN-Normal/BWN-Random gives better
results than both BWN and HIN. Hence it can be said that our combined model is
also robust in case one of the subnetworks cannot be trained.

##  4 Conclusion

In this work, we study CNN-based enery efficient neural networks for the image
classification tasks of MNIST and CIFAR-10 databases. These models are BWN,
HIN, BWHIN-Normal and BWHIN-Random. As observed from these networks, energy
efficiency comes with a small loss of accuracy. BWN gives satisfying results,
while HIN sometimes may struggle to train the network. The combined models
BWHIN-Normal and BWHIN-Random, which are our principle contributions,
certainly improves the performance of their sub-networks BWN and HIN. Hence as
an energy efficient model, the combined model can be preferred with its
superior classification performance.

As future work, proposed energy efficient neural networks can be used for the
classification of other datasets such as CIFAR-100, Street View House Numbers
(SVHN) dataset or ImageNet. The networks can be also implemented with bigger
capacity by increasing the size of a hidden layer or with more hidden layers,
i.e. as a deeper network. Effects of data preprocessing or usage of
unsupervised learning as pretraining on energy efficient NN might be another
research topic.

## References

  * [1] M. Egmont-Petersen, D. de Ridder, and H. Handels, “Image processing with neural networks: a review,” Pattern recognition, vol. 35, no. 10, pp. 2279–2301, 2002.
  * [2] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” Nature, vol. 521, no. 7553, pp. 436–444, 2015.
  * [3] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” Proceedings of the IEEE, vol. 86, no. 11, pp. 2278–2324, 1998.
  * [4] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in Advances in neural information processing systems, pp. 1097–1105, 2012.
  * [5] S. Han, J. Pool, J. Tran, and W. Dally, “Learning both weights and connections for efficient neural network,” in Advances in Neural Information Processing Systems, pp. 1135–1143, 2015.
  * [6] H. Tuna, I. Onaran, and A. E. Cetin, “Image description using a multiplier-less operator,” IEEE Signal Processing Letters, vol. 16, no. 9, pp. 751–753, 2009.
  * [7] C. E. Akbas, A. Bozkurt, M. T. Arslan, H. Aslanoglu, and A. E. Cetin, “L1 norm based multiplication-free cosine similarity measures for big data analysis,” in Computational Intelligence for Multimedia Understanding (IWCIM), 2014 International Workshop on, pp. 1–5, IEEE, 2014.
  * [8] A. Suhre, F. Keskin, T. Ersahin, R. Cetin-Atalay, R. Ansari, and A. E. Cetin, “A multiplication-free framework for signal processing and applications in biomedical image analysis,” in Acoustics, Speech and Signal Processing (ICASSP), 2013 IEEE International Conference on, pp. 1123–1127, IEEE, 2013.
  * [9] C. E. Akbaş, A. Bozkurt, A. E. Çetin, R. Çetin-Atalay, and A. Üner, “Multiplication-free neural networks,” in Signal Processing and Communications Applications Conference (SIU), 2015 23th, pp. 2416–2418, IEEE, 2015.
  * [10] A. Afrasiyabi, O. Yildiz, B. Nasir, F. T. Y. Vural, and A. E. Cetin, “Energy saving additive neural network,” arXiv preprint arXiv:1702.02676, 2017\.
  * [11] D. Badawi, E. Akhan, M. Mallah, A. Üner, R. Çetin-Atalay, and A. E. Çetin, “Multiplication free neural network for cancer stem cell detection in h-and-e stained liver images,” in SPIE Commercial+ Scientific Sensing and Imaging, pp. 102110C–102110C, International Society for Optics and Photonics, 2017.
  * [12] S. K. Esser, P. A. Merolla, J. V. Arthur, A. S. Cassidy, R. Appuswamy, A. Andreopoulos, D. J. Berg, J. L. McKinstry, T. Melano, D. R. Barch, et al., “Convolutional networks for fast, energy-efficient neuromorphic computing,” Proceedings of the National Academy of Sciences, p. 201604850, 2016.
  * [13] S. S. Sarwar, S. Venkataramani, A. Raghunathan, and K. Roy, “Multiplier-less artificial neurons exploiting error resiliency for energy-efficient neural computing,” in Design, Automation & Test in Europe Conference & Exhibition (DATE), 2016, pp. 145–150, IEEE, 2016.
  * [14] M. Rastegari, V. Ordonez, J. Redmon, and A. Farhadi, “Xnor-net: Imagenet classification using binary convolutional neural networks,” in European Conference on Computer Vision, pp. 525–542, Springer, 2016.
  * [15] G. Hinton, O. Vinyals, and J. Dean, “Distilling the knowledge in a neural network,” arXiv preprint arXiv:1503.02531, 2015.
  * [16] İ. Çuğu, E. Şener, and E. Akbaş, “Microexpnet: An extremely small and fast model for expression recognition from frontal face images,” arXiv preprint arXiv:1711.07011, 2017.
  * [17] B. J. Fino and V. R. Algazi, “Unified matrix treatment of the fast walsh-hadamard transform,” IEEE Transactions on Computers, vol. 25, no. 11, pp. 1142–1146, 1976.
  * [18] J. T. Springenberg, A. Dosovitskiy, T. Brox, and M. Riedmiller, “Striving for simplicity: The all convolutional net,” arXiv preprint arXiv:1412.6806, 2014.
  * [19] C.-Y. Wu, M. Zaheer, H. Hu, R. Manmatha, A. J. Smola, and P. Krähenbühl, “Compressed video action recognition,” arXiv preprint arXiv:1712.00636, 2017.
  * [20] M. Petrou and C. Petrou, Image Processing: The Fundamentals.  John Wiley & Sons, 2010.
  * [21] R. C. Gonzalez and R. E. Woods, Digital Image Processing.  Pearson Education, 2007.
  * [22] W. K. Pratt, J. Kane, and H. C. Andrews, “Hadamard transform image coding,” Proceedings of the IEEE, vol. 57, no. 1, pp. 58–68, 1969.
  * [23] I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning.  MIT press, 2016.
  * [24] F. F. Li, J. Johnson, and A. Karpathy, “Cs231n: Convolutional neural networks for visual recognition - neural networks part 3: Learning and evaluation,” 2017\.  [Online; accessed 26-July-2017 ].
  * [25] T.-Y. Lin, A. RoyChowdhury, and S. Maji, “Bilinear cnn models for fine-grained visual recognition,” in Proceedings of the IEEE International Conference on Computer Vision, pp. 1449–1457, 2015.
  * [26] S. Yang and A. Browne, “Neural network ensembles: combining multiple models for enhanced performance using a multistage approach,” Expert Systems, vol. 21, no. 5, pp. 279–288, 2004.
  * [27] Y. LeCun, “The mnist database of handwritten digits,” http://yann. lecun. com/exdb/mnist/, 1998.
  * [28] A. Krizhevsky and G. Hinton, “Learning multiple layers of features from tiny images,” 2009.
  * [29] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, et al., “Tensorflow: Large-scale machine learning on heterogeneous distributed systems,” arXiv preprint arXiv:1603.04467, 2016.
  * [30] N. Srivastava, G. E. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov, “Dropout: a simple way to prevent neural networks from overfitting.,” Journal of Machine Learning Research, vol. 15, no. 1, pp. 1929–1958, 2014.
  * [31] M. Kim and P. Smaragdis, “Bitwise neural networks,” arXiv preprint arXiv:1601.06071, 2016.