%%class
\documentclass{iaesarticle3}

%%required package. add for your convenient, but do not remove the initial
\usepackage{amsmath, amsfonts, amssymb, float, fancyhdr}
\usepackage[scaled]{uarial}
\usepackage[figuresright]{rotating}
\usepackage{authblk, graphicx, indentfirst, lastpage, lipsum}
\usepackage{cite}
\newcounter{example}
\setcounter{example}{0}
\newtheorem{Example}[example]{Example}

\newcounter{remark}
\setcounter{remark}{0}
\newtheorem{Remark}[remark]{Remark}
\newcounter{definition}
\setcounter{definition}{0}
\newtheorem{Definition}[definition]{Definition}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{fontsmpl}
\usepackage{graphics}
\usepackage[english]{algorithme}
%\usepackage{subcaption}
\usepackage{epstopdf}

\setlength{\affilsep}{0cm}
\renewcommand\Authfont{\normalsize}
\renewcommand\Affilfont{\normalfont\small}
\usepackage{subfig, caption, epstopdf}
\usepackage[left=3cm, right=3cm, top=3cm, bottom=3cm, includefoot]{geometry}
\usepackage{caption}
\captionsetup{labelsep=period}
\usepackage{titlesec}
\titleformat{\section}
  {\normalfont\normalsize\bfseries}{\thesection}{1em}{}
\titlespacing*{\section}{0cm}{0.7cm}{0cm}
\titlespacing*{\subsection}{0cm}{0.5cm}{0cm}

%%leave copyright info to the editor
\CopyrightLine[Copyright]{2013}{Universitas Ahmad Dahlan. All rights reserved.}

%%author
\author[1*]{\bfseries Adil Bouhouch}
\author[1]{\bfseries Hamid Bennis}
\author[2]{\bfseries Chakir Loqman}
\author[3]{\bfseries Abderrahime El Qadi}

%%author's affiliation
\affil[1]{ Team TIM, High School of Technology - Moulay Ismail University, Meknes, Morocco}
\affil[2]{department of informatics, Sciences Faculty, Dhar Mehraz, Sidi Mohammed Ben Abdellah University,Fez, Morocco}
\affil[3]{LASTIMI, High School of Technology - Mohammed V University of Rabat Morocco}
\affil[*]{corresponding author, e-mail: bouhouch.adil@gmail.com}


%%title and shortitle (for footer)
\title{Neural Netowrk  and Local search to solve Binary CSP}
\shorttitle{CHN and MNC to solve BCSP,(Bouhouch adil)}

%%starting
\begin{document}

%%indentation. do not change
\setlength{\parindent}{1.27cm}

%%header and footer setting. do not change
\pagestyle{fancy}
\fancyhfoffset{0cm}

%%journal info
\journalname{Indonesian Journal of Electrical Engineering and Computer Science}
\journalshortname{IJEECS}
\revhistory{Received ****** 9, 201x; Revised ***** 3, 201x; Accepted ****** 16, 201x}
\vol{x}
\no{x}
\doi{10.11591/ijeecs.v2.i2.pages}
\months{}
\years{201*}
\issn{2302-4046}

%%build title
\maketitle
%
\begin{abstract}
\textit{\indent
 %Text of abstract
Continuous Hopfield neural Network (CHN) is one of the effective approaches to solve Constraint Satisfaction Problems (CSPs).  However, the main problem with CHN is that it can reach stabilisation with outputs in real values, which means an inconsistent solution or an incomplete assignment of CSP variables. In this  paper, we propose a new hybrid approach combining CHN and min-conflict heuristic to mitigate these problems. The obtained results show an improvement in terms of solution quality, either our approach  achieves feasible soluion with a high rate of convergence, furthermore, this approach can also enhance the performance more than conventional CHN in some cases, particularly, when the network crashes.
%%%
}
\end{abstract}

\begin{keyword}
\textit{
%%write keyword here. separate by comma (,)
Constraint Satisfaction Problem, Continuous Hopfield Neural Network, Meeting Scheduling,Quadratic Problem, Min-Conflict.	
%%
}
\end{keyword}


\section{Introduction}
In general, a Constraint Satisfaction Problem (CSP) consists of a finite set of variables, each one has a finite domain of values and a set of constraints which imposes a variable domain restriction.
And The goal is finding a complete assignment of variables which satisfies all constraints. Many problems from the real world can be reformulated as CSP. For example, qualitative and symbolic reasoning, diagnosis, scheduling, spatial and temporal planning, hardware design and verification, real-time systems and robot planning, etc....
It is known that solving a CSP with a finite domain is an NP-complete problem, which requires a combination of heuristics and combinatory search methods, in order to be solved in a reasonable time \cite{carvalho2013generator}.
%all approaches to solve CSPs.
Mainly, approaches to solve CSPs can be classified into two categories: exact approaches and heuristic ones. As for exact approaches, most of them have the backtracking algorithm (BT) as a main algorithm for solving constraint satisfaction problems. The BT applies a Depth-First search in order to instantiate variables and a backtrack mechanism when dead-ends appear. Many works have been devoted to improve its forward and backward phases by introducing look-ahead and look-back schemes. Some other search algorithms for classical CSPs like Forward Checking, Partial Look-ahead, Full Look-ahead, and Really Full Look-ahead are introduced and their performances are studied in \cite{nadel1988tree}. As far as  heuristic approaches are concerned, we find that, a very different approach has investigated discrete Hopfield Neural Network (HNN) to solve CSP 
\cite{tsang1992generic,adorf1990discrete,nakano2005lagrange}. In this  neural network approach, the CSP constraints are associated with  the network topology, biases, and connection strengths. Recently,  many approaches introduced Continuous Hopfield network to solve CSPs \cite{talavan2005continuous,ettaouil2013maximal,haddouch2013continuous} or problems which can be formulated as CSP \cite{adil2017chn} .  As we can see in \cite{haddouch2013continuous}, the authors propose mapping CSP to a quadratic problem and elaborate an appropriate parameters setting of network energy, then they solve it by finding the network equilibrium point \cite{talavan2005continuous}. Based on the same convergence procedure, Calabuig  \cite{calabuig2010fast}  adds dynamically  linear constraints to confine the network to the feasible subspace of solutions, this improvement ensures the final solution validity.
%\cite{ettaouil2013maximal,CSPCHN,GP,calabuig2010fas and use step by step stabilisation procedure introduced by \cite{talavan2005continuous} and improved by \cite{calabuig2010fast}
Practically, there are two important problems with approaches based on conventional neural network architectures.
The first problem is that HNN partially mitigates the problem of getting stuck in local optimum.
The second one is due to Hopfield network dynamic which continuously explores the search space and will not always stabilize at border 0 or 1. If the same case appears, we get low solution quality or an incomplete assignment
of variables problem. In order to tackle these problems, we propose to improve the CHN solution  by the Min-Conflict heuristic(MNC) \cite{minton1992minimizing}.
The MNC works as follows: it selects the value from each variable domain for which the total error in the next configuration will be minimal. Precisely, MNC is a repair-based stochastic approach, which starts with a complete but inconsistent assignment and then repairs variables implicated in constraint violations repetitively until a consistent assignment is achieved, this approach can solve large-scale problems in a practical time.\\
This paper is  organized as follows: In section 1, we present a modelization of the
binary CSP as 0-1 quadratic program,
and generalizes energy function associated with the CSPs.
Section 2 is devoted to giving implementation details of the proposed approach. In the last section, we show the complexity analysis and the results of the numerical experiments against other approaches like the Genetic Algorithm \cite{yadav2011design}.
%%%%%%%%%%%%%%%%%%%%%%                                                  {Binary CSPs Solved BY CHN}
%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%
\section{Binary CSPs Solved BY CHN}
\subsection{Quadratic model of Constraint satisfaction problem}
A large number of real problems such as artificial intelligence, scheduling, assignment problem can be formulated as a Constraint Satisfaction Problem. Solving a CSP requires to finding an assignment of all variables problem under constraints restriction. The CSP can be formulated as three sets:
% $(X;D;C)$ wher
\begin{itemize}
	\item Set of N variables: $X = \{X_{i}, 1 \leq i\leq N$ \}  .
	\item Set of N variables domains: $D = \{D_{i}, 1 \leq i\leq N$\}
	where each $D_{i}$ contains set of $d_{i}$ range values for $X_{i}$.
	\item Set of M constraints: $C = \{C_{i}, 1 \leq i\leq M$\}.
\end{itemize}
%Each constraint $C_{i}$ associate an ordered variables subset which called the scope of $C_{i}$.
%The arity of constraint is the number of variables in its scope variables.\\
Each constraint $C_{i}$ associates an ordered variables subset which is called the scope of $C_{i}$. The arity of a constraint is the number of involved variables. We can easily reformulate CSP as a Quadratic Problem(QP), by introducing a binary variable $x_{ik}$ for each CSP variable $x_{i}$, where $k$ varies over the range of $x_{i}$, given as follows:
\begin{equation}
x_{ik} =
\begin{cases}
1, & \mbox{if variable i takes value k} \\
0,  & \mbox{otherwise}
\end{cases}
\end{equation}
For each binary constraint $C_{ij}$, between the variables $y_{i}$ and $y_{j}$, we associate a state function defined as:
\begin{equation}\label{eq:Rij}
S_{ij}(x)=\sum_{r=1}^{d_{i}}\sum_{s=1}^{d_{j}}\,x_{ir}x_{js} \, Q_{irjs}
\end{equation}
Where  $x=\{x_{ik} \;,i \in [1..N],k \in d_{i} \}$ a vector of QP solution and the quadratic terms $Q_{irjs}$ defined as:
\begin{equation}\label{eq:qus}
Q_{irjs}=
\begin{cases}
1 & \mbox{if} (r,s)\notin C_{ij} \\
0 & otherwise
\end{cases}
\end{equation}
From all the equations defined in (\ref{eq:Rij}), which correspond to problem constraints, we deduce the objective function of its equivalent QP:
\begin{equation}
f(x)=\sum_{i=1}^N\sum_{r=1}^{d_{i}} \sum_{j=1}^N \sum_{s=1}^{d_{j}}\,x_{ir}x_{js} \, Q_{irjs}
\end{equation}
%Valid solutions must satisfy some strict constraints that can be written as linear equations:
Furthermore, some strict linear constraints equations must be satisfied by the solution:
$ \sum_{r=1}^{d_{i}}x_{ir}=1$. So, the model is given as follows:
\begin{equation}
 (QP) \qquad \left  \{
\begin{array}{lll}
Min& f(x)\\
with\\
&\forall X_i \in X\\
&\sum_{r=1}^{d_{i}}x_{ir}=1\\
&x_{ir}\in\{0,1\}^{n}
\end{array}
\right.
\end{equation}
Systematically, to solve the last Quadratic Optimization Problem with Hopfield model, we need to build an energy function such as the feasible solutions of the problem corresponding to the minimal of CHN energy function.



\subsection{Hopfield neural network }
Hopfield neural network was introduced by Hopfield and Tank \cite{hopfield1982neural}\cite{hopfield1984neurons}\cite{hopfield1985neural}.
At the beginning, it was developed
%%to solve the combinatorial optimization problems.It has been extensively studied,developed and has found many applications in many areas,such as pattern recognition,model identification and optimization.
to solve combinatorial optimization problems. Then it was extended extensively to other areas of application, such as recognition and optimization.
Hopfield neural network is classified as an efficient local search, which  gives an acceptable solution to hard optimization problems at reasonable time.
Basically, This neural network model is a fully connected neural network and its dynamic stats is governed by the following differential equation:
\begin{equation}
\frac{dy}{dt}=-\frac{x}{\tau}+T\,x+i^{b}
\end{equation}
where
\begin{description}
	\item[x]: vector of neurons input
	\item[y]: vector of output %$\in   \mathbb{R}^{n}$
	\item[T]: Matrix of weight between each neurons pairs
	\item[$i^{b}$]: The biases which describe the neurons selft internal noises.
\end{description}

Hopfield proved that if $T$ is symmetric then the network  energies is a Lyapunov function 
\begin{equation}
E(x) = -\frac{1}{2}x^{t}Tx-(i^{b})^{t}x +\sum_{i=1}^{n}\frac{1}{\tau_{i}} \int_{0}^{x_{i}} g^{-1}(v)dv
\label{eq:EhopL}
\end{equation} 


%the input is determine by an activation function $x=g(y)$  which is bounded below by 0 and 1. g(y) is given by:
For each neurons, the input is governed by an activation function $x=g(y)$ which varies between 0 and 1. This function is given by:
\begin{equation}
g(y) = \frac{1}{2}(1+\tanh(\frac{y}{u_{0}}))
\end{equation}
We define the energy function of CHN as to be associete with the cost of the problem to be minimised, this is down by taken $\tau$ too large:
\begin{equation}\label{eq:Ehop}
E(x)=x^{t}\,T\,x+{(i^{b})}^{t}\,x
\end{equation}

%In practice each network neurone is associated to one domain value of each binary CSPs variable, So for a variable $X_{i}$ and it's value at j indices,it's associated neurone is labeled $x_{ij}\in  [0,1]^{n}$ , n is the number of all values in all variables domains.
%\begin{equation}
%\begin{cases}
%x_{ij} =  1, & \mbox{if value j is assined to variable i} \\
%0,  & \mbox{otherwise}
%\end{cases}
%\end{equation}
% $ v_{i,j} = \begin{cases} 1, & \mbox{if value j is assigned to Xi }  \\0, & \mbox{else} \end{cases}$
In this paper, we use the ability of CHN to resolve Quadratic model optimization. So we choose a CHN energy function similar to \cite{haddouch2013continuous}, which is adapted to solve the quadratic formulation of the binary CSPs:
\begin{equation}\label{eq:Ecsp}
E(x)=\frac{\alpha}{2}\sum_{i=1}^N\sum_{j=1}^N\sum_{r=1}^{d_{i}}\sum_{s=1}^{d_{j}}\,x_{ir}x_{js} \, Q_{ijrs}+\beta \sum_{i=1}^N\sum_{r=1}^{d_{i}}x_{ir}+ \gamma\sum_{i=1}^N\sum_{r=1}^{d_{i}}x_{ir}(1-x_{ir})
\end{equation}
%\begin{gather}
%\begin{split}
%   E(x)&= \frac{\alpha}{2}\sum_{i=1}^N\sum_{j=1}^N\sum_{r=1}^{d_{i}}\sum_{s=1}^{d_{j}}\,x{ir}x_{js} \, Q_{ijrs}+\\
%   &\beta \sum_{i=1}^N\sum_{r=1}^{d_{i}}x_{ir}+ \gamma\sum_{i=1}^N\sum_{r=1}^{d_{i}}x_{ir}(1-x_{ir})
%\end{split}
%\end{gather}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The first term penalizes two values taken by two linked variables which caused a violation,
the second term restricts each variable to take one value, the third term aggregates all linear constraints ($Ax=b$),
and the last term satisfies the propriety of integrity which ensures neurons to stabilise at 0 or 1 state.
%$\sum_{r=1}^{d_{i}}x_{ir}=1$
%each $i \in [1,N ] $ and $x_{ir}in \{0,1\}$.
%for in the next out lined  will be in the ag   ,gregate form $Ax=b$,A is a $n\times m$ matrix with n the number of neurones and m the number of linear constraint ,$b_{i}=1$ for $i =1 \dots n$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
By corresponding (\ref{eq:Ehop}) and (\ref{eq:Ecsp}), we deduce the link weight  and biases of the network:
%????????
\begin{equation}
\qquad \left  \{
\begin{array}{l}
T_{irjs} = -\alpha(1-\delta_{ij})Q_{irjs}- \delta_{ij}\phi+2\delta_{ij}\delta_{rs} \gamma\\
i^{b}_{ir}\;\;\;\, = - \beta - \gamma \qquad\qquad\qquad\qquad\qquad
\end{array}
\right. 
\end{equation}
with
$\delta_{ij}=\left\{%
\begin{array}{ll}
1 & \hbox{si $i=j$} \\
0 & \hbox{si $i\neq j$} \\
\end{array}%
\right.$  is the Kronecker delta.\\
To obtain an equilibrium point of the CHN, the parameters setting procedure is used \cite{haddouch2013continuous}\cite{talavan2005continuous}. The principe of this procedure is to  move the network in the direction of $\frac{dy}{dt}$. This process speeds up the neural network convergence significantly.
Furthermore, to assure the stability, we use  the hyperplane analysis method which calculates the
%which consists of divided Hamming hypercube by a hyperplane containing all feasible solutions.
Furthermore, let $E_{ir}(x)=\frac{\partial E(x)}{\partial x_{ir}}$ the following conditions must be imposed to ensure the convergence:
\begin{itemize}
	\item $\alpha>$ to have a minimization problem
	\item The first one concerns avoiding the case when two values are assgined to the same variable, $\exists i,j\in D(X_k)$ with $i\neq j$ and their corresponding neurons  $x_ki=x_kj=1$, so E(x) must verify:
	\begin{equation}
	E_{ir}(x)\geq 2\phi +\beta -\gamma \geq\varepsilon
	\end{equation}
	\item The second ensures that all variable must be assigned and escape the case where :  $x_{ir}=0 \quad \forall r\in\{1,...,d_{i}\}$ so E(x) must verify also: 
	\begin{equation}
	E_{ir}(x)\leq  \alpha \, d+\beta +\gamma \leq -\varepsilon
	\end{equation}
	with $d = Max  \left  \{
	\begin{array}{c}
	\displaystyle  \sum_{j=1}^{N} \sum_{s=1}^{d_{j}} q_{irjs}\:\: / \: i\in \{1,...,N\}  \:\,et  \:\, r \in \{1,...,d_{i}\}
	\end{array}
	\right\} $
\end{itemize}
The best value of $\varepsilon$ is $10^{-5}$
%Based on this hyperplane and the associated half-spaces,
parameters setting by solving \cite{haddouch2013continuous}:
\begin{equation}
\qquad \left  \{
\begin{array}{cccc}
& \phi\geq0,\;\;\alpha>0\\
&  -\phi + 2\gamma\geq0 \\
& 2\phi +\beta -\gamma =\varepsilon\\
& \alpha\, d+\beta +\gamma = -\varepsilon
\end{array}
\right.
\end{equation}
%\subsection{improving Step by step Hopfield stabilisation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%There has been a long history of using neural networks for combinatorial optimization and constraint satisfaction problems.
%Symmetric Hopfield networks and similar approaches use steepest descent dynamics that converge to the closest local minimum of energy.

%\begin{remark}
The CHN parameters setting and the starting point used in this paper are similar to \cite{haddouch2013continuous}
. Furthermore, a procedure which allows each neuron of the same variable to take 0, if one converges to the boarder 1, is added. This procedure is called Moderator(Figure \ref{fig:modu}).
%\end{remark}

\begin{figure}[h]
	\centering{\includegraphics[width=0.65\textwidth,height=0.15\textheight]{Mod.eps}}%[width=0.99\textwidth,height=0.2\textheight]
	\caption{Moderator} \label{fig:modu}
\end{figure}

This approach, which only uses Continuous Hopfield  neural Network (CHN), was extensively studied over different instances of Constraints satisfaction problem \cite{talavan2005continuous}, but simulation proved that this approach has many disadvantages. For example, sometimes the network in continuous dynamic does not gives a valid solution, and
it is attracted by the nearest local minimal to the starting point. This attracting effect remains a result of its deterministic input-output interaction of the units in the network. Consequently, the network is not able to escape from a local solution closed to the starting point. Also, for Hopfield neural network with a continuous dynamics case,  each unit  output can take any  value between 0 and 1. So, the network can be stranded at a local minimum which contains some units that still take real values. In this case, we obtain an invalid solution for CSP. To overcome this neural network weakness, the main idea of this work is to repair the solution given by the CHN and improve it by  a known Min-conflict algorithm.

\section{CHN and Min conflict heuristic to solve CSPs }
The MNC algorithm \cite{minton1992minimizing} is a very simple and fast
local repairing method to resolve CSPs, which aims at assigning all the variables randomly.
Next, it iteratively selects one variable from the set of the variables with conflicts which violates one or more constraints of the CSP. Then, it assigns a value to the selected variable, so that it can minimize the number of conflicts. MNC has demonstrated to be able to solve the queens problem in minutes \cite{minton1993minimizing}.
MNC is widely used to construct hybrid algorithms with other optimizations
\cite{handa2003hybridization,hayakawa2011improving,liu2005hybrid,zou2003characterizing}.
In this way, the basic idea of our proposed approach is to use MNC to improve the solution reached by CHN. This will be done in two steps (see Figure \ref{fig:main}). First, MNC visits all assigned variables; for each one, we apply Min-Conflict directly to the neural network structure, then, it returns the best assignment for the current variable (see Figure \ref{fig:minc}), the decision will be taken by the sum of  all activated neurons weight.
Second, we propagate this assignment to other set variables not yet assigned iteratively by applying the MNC heuristic to guarantee as much consistency as possible.
%
%\begin{figure}%\sidecaption
%\resizebox{0.8\hsize}{!}{\includegraphics{Propagate.eps}}
%\caption{A figure}\label{fig:main1}
%\end{figure}

\begin{figure}
	\centerline{\includegraphics[width=0.75\textwidth,height=0.30\textheightwidth=0.75\textwidth,height=0.30\textheight]{Propagate.eps}}%[width=0.80\textwidth,height=0.50\textheight]
	\caption{main function which improve solution by Min-conflict algorithm}\label{fig:main}
\end{figure}

\begin{figure}
	\centerline{\includegraphics[width=0.75\textwidth,height=0.30\textheight]{minc.eps}}
	\caption{Selected the most coherent neuron of current cluster with other variables clusters already affected}\label{fig:minc}
\end{figure}

The diagram of our proposed algorithm is described by the following plan(Figure4):
\begin{figure}
	% \vspace{1.5cm}
	
	\centerline{\includegraphics[width=6cm]{algoCHNMNC.eps}}%[width=7cm]
	\caption{Diagram of the proposed algorithm} \label{fig:algdiag}
\end{figure}
\begin{Example}{\textbf{\emph{Meeting Scheduling Problem}}}
	\\The Meeting Scheduling problem (MSP) is a decision-making process affecting several people, in which it is necessary to decide when and where several meetings could be scheduled.To show how this algorithm works, we consider the following MSP example:
	\begin{itemize}
		\item Persons=$\{0,1,2,3\}$
		\item  Meetings $m_{1},m_{2},m_{3},m_{4}$
		\begin{itemize}
			\item $m_{1}$ attend person group: $\{0,1\}$
			\item $m_{2}$ attend person group:$\{1,2\}$
			\item $m_{3}$ attend person group:$\{0,1,2\}$
			\item $m_{4}$ attend person group:$\{2,3\}$
		\end{itemize}
		\item  Location $L=\{ pl_{1},pl_{2},pl_{3},pl_{4}\}$
		\item  Distances :
		\begin{center}
			\includegraphics[width=3.3cm]{distances.eps}%[width=4cm]
		\end{center}
		\item  Time Slot=$\{t_{1},t_{2},t_{3},t_{4},t_{5}\}$
		\item Duration of each meeting $1\,time\,slot$
	\end{itemize}
	\textbf{This problem can be reformulated as the following CSP:}
	\begin{itemize}
		\item Variables: V=$ \{m_{1},m_{2},m_{3},m_{4}\}$  list of meeting
		\item Domains D=$\{t_{i} ,1 \leq i \leq 4 \}$  where
		$$t_{1}=t_{4}=\{0,1,2,3,4\} \,\,\, and \,\,\,t_{2}=t_{3}=\{0,4\}$$
		\item Constraints C= $\{C_{i,j} ,1 \leq i< j \leq 4   \}$
		$$  C_{i,j} \,\,\,\,\,\,  is\,\, violated \,\, if \,\, \mid t_{i}-t_{j}\mid- Duration(m_{i})-TravelingFromTo ( pl_{i},pl_{j})<0$$
		So we can extract tuple of relation for each constraint($R_{ij}$ refers to allowed tuple and $\overline{R}_{ij}$ refers to disallowed ones):\\   $\overline{R}_{1,2}=\{0 \; 0|1\; 0|3 \;4|4 \;4\}$
		$\quad \overline{R}_{1,3}=\{0 \; 0|1\; 0|3 \;4|4 \;4\}$ $\quad \overline{R}_{1,4}=\{{\emptyset}\}$ \\
		$R_{2,3}=\{0 \; 4|4 \; 0\}$
		$\quad\overline{R}_{2,4}=\{0 \; 0|1 \; 0|3 \; 4|4 \; 4\}$
		$\quad\overline{R}_{3,4}=\{0 \; 0|0 \; 1|4 \; 3|4 \; 4\}$
		
	\end{itemize}
	We supposed that CHN after running gives an incomplete solution $S=V_{a}=\{ \{m_{1}=1 \} ,\{m_{2}=4 \},\{m_{3}=0 \} \}$
	First passe :
	For each variable in $V_{a}$
	\begin{itemize}
		\item $m_{1}$
		\begin{itemize}
			\item  $w(0)=w(1)=w(3)=w(4)=-\alpha$
			\item  $w(2)=0 $\\ so $Min$-$Conf( m_{1} ,V_{a}$)  return 2
		\end{itemize}
		
		\item $m_{2}$
		\begin{itemize}
			\item  $w(0)=-\alpha$
			\item $w(4)=0$
			\\    so $Min$-$Conf( m_{2} ,V_{a}$)  return 4
		\end{itemize}
		\item $m_{3}$
		\begin{itemize}
			\item  $w(0)=0$
			\item $w(4)=-\alpha$
			\\ so $Min$-$Conf( m_{3} ,V_{a}$)  return 0
		\end{itemize}
	\end{itemize}
	The second phase will take $m_{4}$ which is not yet assigned   :
	
	\begin{itemize}
		\item $m_{4}$
		\begin{itemize}
			\item  $w(0)=w(1)=w(3)=w(4)=-\alpha$
			\item $w(2)=0$
			\\so  $Min$-$Conf( m_{4} ,V_{a}$)  return 2
		\end{itemize}
	\end{itemize}
	The final solution is $S=V_{a}=\{ \{m_{1}=2 \} ,\{m_{2}=4 \},\{m_{3}=0 \},\{m_{4}=2 \} \}$.
	
\end{Example}



\section{ Numerical results}
\subsection{Generated randomly instances}
To evaluate the performance of proposed resolving methods, we run some preliminary experiments on the randomly generated
problems and  we compare the solution quality by  the number of violations. Simulation has been done with the following  machine characteristics: I5 core(TM) 2,35GHz  processor and limitation of memory to 2GO. For CHN parameters,
the best values were founded empirically:
$$\phi= \alpha\, d+2\;\varepsilon\qquad\qquad\gamma=\frac{\phi}{2}\qquad\qquad \beta= \varepsilon-3\; \gamma$$
To generate random problems, we use a random generator based extended model B as it is described in  \cite{xu2000exact,xu2005simple,xu2007random}. This extended model which is called Model RB is able to generate a hard satisfiable instance. To summarize this generation method, a random CSP is defined by the following five input parameters:
\begin{itemize}
	\item  $k $:  denotes the arity of each constraint, fixed at $k=2$, so all constraints are binary
	\item  $n$ :  denotes the number of variables,
	\item  $\alpha$:  determines the domain size $d = n^{\alpha}$ of each variable,
	\item  $r > 0$: determines the number $m = r\,n\,\ln(n)$ of constraints,
	\item $1 > p > 0$: determines the number $t = p\,d^{k}$ of disallowed tuples of each relation.
\end{itemize}
In the following, a class of  CSPs will be denoted by a tuple of the form  $<n, d, m, k, p> $.
For simulation, we generate  $50$ instances for each  $p$ value for $k = 2$,  $\alpha= 0.8$, $r = 3$ and $n\in\{20, 30, 40\}$, and we calculate the average of violated constraints of each instance in the same class of p value.
For the model parameter used, we get $<20, 11,180,p> $, $<30,15,306,p>$  and $<40,19,443,p>$. The corresponding load curve is given in Figures \ref{fig:rb20chnmin}, \ref{fig:rb30chnmin} and  \ref{fig:rb40chnmin} respectively. Comparison is made between the solution obtained by the proposed algorithm and the solution given by the original approach \cite{haddouch2013continuous}.
As we can see Min-Conflict improves the quality of the solution considerably around mean $50\%$, and the success of network is up to 100\%, but for CHN approach, we find the empirically mean value 72\% over all runs.

\begin{figure}[h]
	% \vspace{1.5cm}
	\centering{\includegraphics[width=6.9cm]{RBn20chnmin.eps}}%
		\caption{number of violation over classe  N=20 } \label{fig:rb20chnmin}
	
\end{figure}
\begin{figure}[H]
	% \vspace{1.5cm}
	\centering  \includegraphics[width=6.7cm]{RBn30chnmin.eps}%
	\caption{number of violation over classe  N=30 } \label{fig:rb30chnmin}
	
\end{figure}

\begin{figure}[H]
	% \vspace{1.5cm}
	\caption{number of violation over classe  N=40 } \label{fig:rb40chnmin}
	\centering \includegraphics[width=6.7cm]{RBn40chnmin.eps}%
\end{figure}
\subsection{Typical instances}
For showing the practical interest of our approach, we also study its performance over problems of different natures
(random, academic and real-world problems) \cite{cspbenchLc}. The goal is to evaluate its performance with other evolutionary algorithms \cite{jamian2012new,omranpour2012dynamic}. Thus, we compare its efficiency with the Genetic Algorithm (GA) \cite{kanoh1995genetic} and the Particular Swarm Optimization (PSO) \cite{schoofs2002swarm} . In practice, rather than authors settings we have empirically searching the Genetic Algorithm and PSO goods ones, adopted to CSP problem. So, for GA the population was 200 individuals, mutation rate equals to 5\% and crossing rate equals to 72\%, as for PSO \cite{schoofs2002swarm} we chose $\varphi_1=\varphi_2=1$ and population size fixed at 100. We  also run each one 200 times. \\ 
The CHN parameters setting and the starting point used in this paper are similar to \cite{haddouch2013continuous}, we have used
the Variable Updating Step (VUS) technique proposed by Talav{\'a}n and Y{\'a}{\~n}ez in \cite{talavan2005continuous}. Table \ref{table_example} shows the comparison between our approach CHN-MNC and original
CHN. The description of table columns is the following:
\begin{itemize}
	\item V: the number of  variables.
	\item C: the number of constraints.
	%\item Number of Run: the  number of execution of solver for each instances
	%	\item Ratio min:  the better result11s obtained by each solver111111
	\item Ratio mean:  the average of the optimal value in a 200 run.
	\item Time:  the average of the time of all runs.
	
	%\item Ratio mod:  the most repetitive (mode) optimal value obtained by CHN in number of run
\end{itemize}
% \begin{description}   \item[V] the number of instance variables   \item[C] the number of constraints   \item[Number of Run] the  number of execution of solver for each instances   \item[Ratio min]  the better results obtained by each solver   \item Ratio mean]  the average of the optimal value in a number of run,   \item[Ratio mode] the most repetitive (mode) optimal value obtained by CHN in number of run,  \end{description}
% \begin{figure}[!h]
% \centering
% \vspace{1.5cm}
% \e includegraphics[width=10cm]{algo1.png}
% \caption{number of violation over classe  N=40 } \label{fig:rbn}
% \end{figure}
% \begin{figure}[!h]
% \centering
% \vspace{1.5cm}
% \e includegraphics[width=10cm]{algo2.png}
% \caption{number of violation over classe  N=40 } \label{fig:rb}
% \end{figure}

\begin{table}
	%% increase table row spacing, adjust to taste
	\renewcommand{\arraystretch}{1.3}
	% if using array.sty, it might be a good idea to tweak the value of
	% \extrarowheight %as needed to properly center the text within the cells
	\tiny{
		\caption{Performance of our proposed methods CHN-MNC and CHN over typical instances problems }
		\label{table_example}
		\centering
		% Some packages, such as MDW tools, offer better commands for making tables
		% !than the plain LaTeX2e yabular which is used here.
		\scriptsize{
			%\rotatebox{90}{
			\begin{tabular}{|l|c|c|c|c|c|c|c|c|}
				\hline
				Name of 	&	V	&	C	&	 \multicolumn{2} {c|}{ CHN-MNC}			&	 \multicolumn{2} {c|}{GA}			&	 \multicolumn{2} {c|}{ PSO}			\\
				\cline{4-9}
				instance	&		&		&	Mean	&	CPU(s)	&	Mean 	&	CPU(s)	&	Mean 	&	CPU(s)	\\
				\hline
				queens-10	&	10,00	&	45,00	&	1,00	&	0,01	&	2,00	&	0,02	&	13,00	&	0,04	\\
				queens-20	&	20,00	&	190,00	&	2,00	&	0,03	&	4,00	&	0,06	&	39,00	&	0,11	\\
				
				queens-5-5-5	&	25,00	&	160,00	&	0,00	&	0,03	&	0,00	&	0,06	&	19,00	&	0,10	\\
				frb30-15-5-mgd	&	30,00	&	210,00	&	10,00	&	1,07	&	14,00	&	2,46	&	40,00	&	4,08	\\
				geom-30a-5	&	30,00	&	81,00	&	1,00	&	0,06	&	2,00	&	0,13	&	7,00	&	0,21	\\
				geom-30a-6	&	30,00	&	81,00	&	0,00	&	0,05	&	0,00	&	0,12	&	4,00	&	0,20	\\
				queens-30	&	30,00	&	435,00	&	4,00	&	1,94	&	6,00	&	4,45	&	83,00	&	7,39	\\
				frb40-19-3-mgd	&	40,00	&	308,00	&	14,00	&	0,93	&	21,00	&	2,14	&	53,00	&	3,56	\\
				geom-40-2	&	40,00	&	78,00	&	23,00	&	0,01	&	24,00	&	0,03	&	28,00	&	0,04	\\
				geom-40-6	&	40,00	&	78,00	&	0,00	&	0,09	&	0,00	&	0,21	&	4,00	&	0,36	\\
				myciel-5g-3	&	47,00	&	236,00	&	10,00	&	0,22	&	12,00	&	0,50	&	47,00	&	0,83	\\
				myciel-5g-4	&	47,00	&	236,00	&	5,00	&	0,41	&	8,00	&	0,95	&	29,00	&	1,58	\\
				myciel-5g-5	&	47,00	&	236,00	&	1,00	&	0,47	&	3,00	&	1,09	&	12,00	&	1,81	\\
				myciel-5g-6	&	47,00	&	236,00	&	0,00	&	0,13	&	1,00	&	0,31	&	12,00	&	0,51	\\
				driverlogw-01c	&	71,00	&	217,00	&	0,00	&	0,08	&	0,00	&	0,17	&	3,00	&	0,29	\\
				composed*	&	105,00	&	620,00	&	13,00	&	2,93	&	14,00	&	6,75	&	56,00	&	11,20	\\
				dsjc-125-1-4	&	125,00	&	736,00	&	50,00	&	0,30	&	64,00	&	0,69	&	102,00	&	1,15	\\
				dsjc-125-1-5	&	125,00	&	736,00	&	19,00	&	0,80	&	29,00	&	1,83	&	85,00	&	3,04	\\
				qwh-15-106-1	&	225,00	&	2324,00	&	20,00	&	1,60	&	23,00	&	3,68	&	66,00	&	6,11	\\
				qwh-15-106-4	&	225,00	&	2324,00	&	18,00	&	4,06	&	22,00	&	9,35	&	59,00	&	15,52	\\
				qwh-15-106-6	&	225,00	&	2324,00	&	22,00	&	2,31	&	23,00	&	5,31	&	68,00	&	8,82	\\
				driverlogw-04c	&	272,00	&	3876,00	&	3,00	&	8,32	&	5,00	&	19,13	&	11,00	&	31,75	\\
				driverlogw-02c	&	301,00	&	4055,00	&	3,00	&	9,17	&	5,00	&	21,09	&	9,00	&	35,01	\\
				qwh-20-166-0	&	400,00	&	5092,00	&	30,00	&	16,79	&	32,00	&	38,63	&	93,00	&	64,12	\\
				qwh-20-166-3	&	400,00	&	5092,00	&	29,00	&	2,88	&	31,00	&	6,63	&	89,00	&	11,00	\\
				qwh-20-166-6	&	400,00	&	5092,00	&	25,00	&	8,19	&	29,00	&	18,84	&	86,00	&	31,27	\\
				le-450-5a-3	&	450,00	&	5714,00	&	1173,00	&	333,69	&	1261,00	&	767,49	&	1566,00	&	1274,03	\\
				le-450-5a-4	&	450,00	&	5714,00	&	712,00	&	3,89	&	745,00	&	8,95	&	1066,00	&	14,86	\\
				le-450-5a-5t	&	450,00	&	5714,00	&	441,00	&	2,29	&	470,00	&	5,26	&	874,00	&	8,72	\\
				
				\hline
				
			\end{tabular}
			
			NB:composed* is the instance composed-25-10-20-5
		}
		%}
	}
\end{table}



%\hline
%plain

From Table \ref{table_example} we learn that GA and CHN-MNC are close and both better than PSO, but regarding the mean time taken by all compared algorithms CHN-MNC is the short one. GA \cite{kanoh1995genetic} have the same principle with our approach while they use GA and Minimization of conflicts, but they improve the best individual. It's not sure that improving a best solution will give the good one, it can be near the worst one in the population. For this reason, the means value of the multiple runs of our approach was the best because it improves each founded solution.      
\section{Conclusion}
In this paper, we have proposed a new approach for solving binary constraint satisfaction problems. Our hybrid algorithm
gives a good solution quality rather than using CHN alone, this improvement  is done by adding a no importuned time computation.
Furthermore the rate of network success to give a valid solution is up to 100\% by repairing. Also, the results of the numerical example show that our approach is competitive with GA and PSO. The basic Hopfield  neural network architecture described above includes only binary constraints, but some classes of problems are natively n-ary.
The extension of this approach to solve these problems is possible if  we can translate
any n-ary problem to an equivalent binary one.
Other studies are in progress to apply this approach to many real-world problems such as aircraft conflict, timetabling and Meeting scheduling.
%% main text

%\section{Introduction}
%\label{}
%The main text format consists of a flat left-right columns on A4 paper (quarto). The margin text from the left, right, top, and bottom 3 cm. The manuscript is written in Microsoft Word, single space, Arial 10pt and maximum 12 pages, which can be downloaded at the website: http://www.telkomnika.ee.uad.ac.id
%\par
%A title of article should be the fewest possible words that accurately describe the content of the paper. Omit all waste words such as "A study of ...", "Investigations of ...", "Implementation of ...", "Observations on ...", "Effect of.....", "Analysis of ...", "Design of ..." etc. Indexing and abstracting services depend on the accuracy of the title, extracting from it keywords useful in cross-referencing and computer searching. An improperly titled paper may never reach the audience for which it was intended, so be specific.
%\par
%The Introduction should provide a clear background, a clear statement of the problem, the relevant literature on the subject, the proposed approach or solution, and the new value of research which it is innovation. It should be understandable to colleagues from a broad range of scientific disciplines. Organization and citation of the bibliography are made in Vancouver style in sign \cite{Li}, \cite{Arulmozhiyal} and so on. The terms in foreign languages are written italic (italic). The text should be divided into sections, each with a separate heading and numbered consecutively. The section/subsection headings should be typed on a separate line, e.g., 1. Introduction \cite{Zhang}. Authors are suggested to present their articles in the section structure: Introduction - the comprehensive theoretical basis and/or the Proposed Method/Algorithm - Research Method - Results and Discussion – Conclusion.
%\par
%Literature review that has been done author used in the chapter "Introduction" to explain the difference of the manuscript with other papers, that it is innovative, it are used in the chapter "Research Method" to describe the step of research and used in the chapter "Results and Discussion" to support the analysis of the results \cite{Arulmozhiyal}. If the manuscript was written really have high originality, which proposed a new method or algorithm, the additional chapter after the "Introduction" chapter and before the "Research Method" chapter can be added to explain briefly the theory and/or the proposed method/algorithm \cite{Zhang}.
%
%\section{Research Method}
%\label{}
%Explaining research chronological, including research design, research procedure (in the form of algorithms, Pseudocode or other), how to test and data acquisition \cite{Li}-\cite{Zhang}. The description of the course of research should be supported references, so the explanation can be accepted scientifically \cite{Arulmozhiyal}, \cite{Yinhai}.
%\par
%Tables and Figures are presented center, as shown below and cited in the manuscript.\\
%
%\begin{table}[h]
%\caption{The Performance of ...}
%\centering
%\begin{tabular}{lcr}
%\hline
%Variable & Speed (rpm) & Power (kW) \\
%\hline
%x & 10 & 8.6 \\
%y & 15 & 12.4 \\
%z & 20 & 15.3 \\
%\hline
%\end{tabular}
%\end{table}
%
%\begin{figure}[h]
%\centering
%\includegraphics[scale=0.5]{figure1}
%\caption{Effects of selecting different switching under dynamic condition}
%\end{figure}
%
%\section{Result and Analysis}
%\label{}
%In this section, it is explained the results of research and at the same time is given the comprehensive discussion. Results can be presented in figures, graphs, tables and others that make the reader understand easily \cite{Arulmozhiyal}, \cite{lamport}. The discussion can be made in several sub-chapters.
%
%\subsection{Equations}
%Equations should be placed at the center of the line and provided consecutively with equation numbers in parentheses flushed to the right margin, as in (1). The use of Microsoft Equation Editor or MathType is preferred.
%\\
%\begin{equation}
%E_v - E = \frac{\hbar}{2.m}(k_x^2 + k_y^2)
%\end{equation}
%\\
%All symbols that have not been mentioned in the equation should be explained in the following text.
%
%\subsection{Citations}
%Proper citation of other works should be made to avoid plagiarism. When referring to a reference item, please use the reference number as in \cite{Li} or \cite{Li, Arulmozhiyal, Zhang, Yinhai, lamport, knuth} for multiple references. The use of "Ref \cite{lamport}..." should be employed for any reference citation at the beginning of sentence. For any reference with more than 3 or more authors, only the first author is to be written followed by et al (e.g. in \cite{Yinhai}).  Examples of reference items of different categories shown in the References section. Each items in the references section should be typed using 9pt font size.
%
%\section{Conclusion}
%\label{}
%Provide a statement that what is expected, as stated in the "Introduction" chapter can ultimately result in "Results and Discussion" chapter, so there is compatibility. Moreover, it can also be added the prospect of the development of research results and application prospects of further studies into the next (based on result and discussion).
%
%\section*{Acknowledgement}
%\label{}
%The acknowledgment section is optional. The funding source of the research can be put here.

%% The Appendices part is started with the command \appendix;
%% appendix sections are then done as normal sections
%% \appendix

%% \section{}
%% \label{}

%% References
%%
%% Following citation commands can be used in the body text:
%% Usage of \cite is as follows:
%%   \cite{key}         ==>>  [#]
%%   \cite[chap. 2]{key} ==>> [#, chap. 2]
%%

%% References with BibTeX database:

\bibliographystyle{IEEEtran}
\bibliography{dataitem}

%% Authors are advised to use a BibTeX database file for their reference list.
%% The provided style IEEEtran.bst formats references is generally used.

%% For references without a BibTeX database:

% \begin{thebibliography}{4}
%
%%% \bibitem must have the following form:
%%%   \bibitem{key}...
%%%
%
% \bibitem{Li} X. S. Li., et al., "Analysis and Simplification of Three-Dimensional Space Vector PWM for Three-Phase Four-Leg Inverters," \textsl{IEEE Transactions on Industrial Electronics}, vol. 58, pp. 450-464, Feb 2011.
%
% \bibitem{Arulmozhiyal}	R. Arulmozhiyal and K. Baskaran, "Implementation of a Fuzzy PI Controller for Speed Control of Induction Motors Using FPGA," \textsl{Journal of Power Electronics}, vol. 10, pp. 65-71, 2010.
%
% \bibitem{Zhang} D. Zhang, et al., "Common Mode Circulating Current Control of Interleaved Three-Phase Two-Level Voltage-Source Converters with Discontinuous Space-Vector Modulation," \textsl{2009 IEEE Energy Conversion Congress and Exposition}, Vols 1-6, pp. 3906-3912, 2009.
%
% \bibitem{Yinhai}	Z. Yinhai, et al., "A Novel SVPWM Modulation Scheme," in \textsl{Applied Power Electronics Conference and Exposition, 2009. APEC 2009. Twenty-Fourth Annual IEEE}, 2009, pp. 128-131.
% 
% \bibitem{lamport} Leslie Lamport. \textsl{\LaTeX\ -- A Document Preparation System}, 2nd edition. Addison-Wesley, Reading, MA, 1994.
% 
% \bibitem{knuth} Donald E. Knuth. \textsl{Computers and Typesetting Vol.\ A--E}. Addison-Wesley, Reading, MA, 1986
%
% \end{thebibliography}


\end{document}

%%
%% End of file `telkomnika.tex'. 