I meet with an integer optimizing problem, which is defined as follows:

$\displaystyle s^{*}= \textrm{argmax}_{\begin{subarray}{c}{s \in\mathcal{S}}\end{subarray}}\sum_{i=1}^{N}{\frac {\exp\left(c_i+b_i^Ts\right)}{\sum_{j=1}^{N}{\exp\ left(c_j+b_j^Ts\right)}}\cdot \left(a_i+w_i^Ts\right)}$

Where $\displaystyle \mathcal{S}$ denotes $\displaystyle n$ dimensional column parameter vector, each entry takes the integer and is defined as:

$\displaystyle 0 \le p_i \le n-i,\quad i=1,2\ldots n$

$\displaystyle 0 \le q_i \le i-1,\quad i=1,2 \ldots n$

$\displaystyle s_k=2\left(p_k-q_k\right),\quad k=1,2\ldots n$

$\displaystyle \sum_{j=1}^{k-1}{s_j} \ge q_k,\quad k=2,3,\ldots n$

$\displaystyle \sum_{j=1}^{n}{s_j}=0$

$\displaystyle s^{*}$ represents the optimal solution. $\displaystyle b_i,w_i$ denote $\displaystyle n$ dimensional column vector, whose values are known. The scalars $\displaystyle a_i,c_i$ are also defined.

Our Goal

Our goal is to build an algorithm, which can solve the optimization problem in polynomial order time with $\displaystyle m$ and $\displaystyle n$. What's happiest, you can yield an analytical solution to the optimization problem.

This problem comes from my research, which is very important for me.

I hope you give me some suggestion and advice.

Thank you.