\section{Introduction}

The unit commitment problem (UCP) consists of deciding which power generating units must be committed/decommitted over a planning horizon, usually lasting from 1 day to 2 weeks and split into periods of one hour.  The production levels at which units must operate (pre-dispatch) must also be determined to optimize a cost function which includes both fixed and variable costs.  The committed units must satisfy the forecasted system load and reserve requirements, as well as a large set of technological constraints.  This problem has great practical relevance, due to the savings that can be achieved with an optimized schedule.

Simple approaches for this problem model the cost as a linear function, which provides a rather rough approximation; accuracy can be improved by switching to a quadratic function.  For these models general-purpose mixed-integer convex optimization solvers can be used to find optimum solutions for realistic, large instances.  Nonetheless, much better approximations of the true costs can be obtained if the valve-point loading effect is taken into account;  however models become much more difficult to optimize.

Valve-point loading affects the input-output characteristics of generating units, making the fuel costs nonlinear and nonsmooth.  This has been considered in the heuristic solution of load dispatch problems --- see, \emph{e.g.}, \cite{AlSumait2007720, Hemamalini2011868, Roy20134244, SrinivasaReddy2013342}, but there are no exact methods available in the literature.

Concerning the planning phase of unit commitment, even for convex models most of the research on the solution of the UCP focuses in heuristic methods.   Recently, however, improvements in the capabilities of mixed-integer programming solvers has encouraged the thorough exploitation of their capabilities~\cite{viana2013}.  Extensive surveys of different optimization techniques and modeling issues are provided in \cite{sen1998, PAD04, YAM04}, but the valve-point loading effect is not considered in any of the exact methods proposed.  A mixed integer quadratically constrained model to solve unit commitment on real-life, large-scale power systems is presented in~\cite{Alvarez2012}; it details some features of the units, but not the valve-point loading effect.  Another approach, where a mixed integer linear formulation is used for modeling nonlinear output of generators and applied to unit commitment, is presented in~\cite{Simoglou2010}.  A process with some similarities to the method we propose, also involving the assessment of lower and upper bounds to a nonlinear function and iteratively converging to the optimum, has been presented in~\cite{Lima2013} and applied to a related problem: that of optimizing short-term hydro scheduling.

The main contribution of this paper is a method based on a careful linearization of the fuel cost function, which is modeled with great detail on power regions being used in the current solution and roughly on other regions; this formulation is used in an iterative process that converges to the optimum.  The method may be used both for load dispatch (by setting the number of planning periods to one) and for unit commitment.  When the solution process stops, \emph{e.g.}~due to a limit on CPU usage, the method provides both an upper and a lower bound to the optimum; this information is usually very important in practice.

\section{Mathematical model}
\label{sec:model}

A concise, complete description of the unit commitment problem as a mathematical optimization model has been provided in~\cite{viana2013}.  When valve-point loading is taken into account that model can be used as is, except for the shape of the objective function: instead of a quadratic function, as considered in~\cite{kazarlis1996}, it is now a nonconvex, nonsmooth function, as has been proposed for load dispatching in~\cite{wood1984} (cited by~\cite{coelho2006}).

\begin{figure}[!htbp]
\centering
\resizebox{.75\linewidth}{!}{\input{cost_shape}}
\caption{Typical shape of the fuel cost considering the valve-point loading effect.}
\label{fig:cost_shape}
\end{figure}

\subsection{Objective}
\label{sec:objective}

A commonly used function of the fuel costs in a generating unit in terms of the power produced $p$, taking into account the valve-point loading effect, is the following~\cite{wood1984}:
\begin{alignat}{27}
F(p) = a + b p + c p^2 + \left|e \sin\left(f (P^{\mathsf{min}}} %%%{\underline{P}-p)\right)\right|,  \label{eq:valve}
\end{alignat}
where $a,b,c,e,f$ are function's parameters (see Figure~\ref{fig:cost_shape}), as are the minimum and maximum operating powers $P^{\mathsf{min}}} %%%{\underline{P}$ and $P^{\mathsf{max}}} %%%{\overline{P}$.
The first three terms describe a quadratic function, as usually taken into account when valve-point loading is not considered; when it is, there is a periodic factor, as described in the rightmost term.

This function being nonlinear, nonconvex, and nonsmooth, methods for optimizing it under constraints on load limit and demand satisfaction --- \emph{i.e.}, in an economic load dispatch setting --- usually involve specifically designed heuristic approaches, many of them based on evolutionary algorithms~\cite{SrinivasaReddy2013342, Coelho20102580}.

There is, however, a way of tackling this problem exactly (\emph{i.e.}, with arbitrarily low error).  Let us first notice that the valve points --- where there is a discontinuity --- limit areas where the function is concave.  Thus, if we evaluate the function into several points and use them as breakpoints for joining the two valve points, we obtain a linear function that is never larger than the true function (see Figure~\ref{fig:cost_lowerA}).  Given a power production level this function provides, thus, a lower bound to the objective value; on the other hand, the evaluation of the true function provides a trivial upper bound.  For any solution satisfying all the problem's constraints, a lower and an upper bound to possible values of the objective can therefore be obtained by the piecewise-linear lower approximation and the true function, respectively.
\begin{figure}[!htbp]
\centering
\resizebox{.49\linewidth}{!}{\input{cost_lowerA}}
\resizebox{.49\linewidth}{!}{\input{cost_bounds}}
\caption{Fuel cost and its representation with a piecewise-linear function (left).  Upper bound (UB, exact function evaluation) and lower bound (LB, piecewise-linear approximation) at a given production level $p$ (right).}
\label{fig:cost_lowerA}
\label{fig:cost_bounds}
\end{figure}

For obtaining increased precision, a large number of breakpoints may be required; this is likely to be the limiting step for large instances.  In order to obviate this problem as much as possible, we may have the cost function represented with greater detail in power regions of potential operation, whereas on other areas the representation may be more rough; in the limit, there may be a single straight line joining two valve points (see Figure~\ref{fig:cost_lowerB}).
Later in this section we propose an algorithm for determining where to expand the number of breakpoints.  The final shape of the piecewise-linear approximation may resemble that of Figure~\ref{fig:cost_lowerC}.
\begin{figure}[!htbp]
\centering
\resizebox{.49\linewidth}{!}{\input{cost_lowerB}}
\resizebox{.49\linewidth}{!}{\input{cost_lowerC}}
\caption{Piecewise-linear fine approximation in important areas, rough on the other areas (left). Fuel cost and its possible final representation with a piecewise-linear function (right).}
\label{fig:cost_lowerB}
\label{fig:cost_lowerC}
\end{figure}

Considering a set of units $\mathcal{U}$ and a set of periods $\mathcal{T}$, for a given unit $u\in\mathcal{U}$ and period $t\in\mathcal{T}$, once the coordinates $(X_{utk},Y_{utk})$ for the set of breakpoints $k=0,\ldots,K$ to be considered is known, the lower approximation of the objective function can easily be included in a mixed-integer programming (MIP) linear model by means of a convex combination of these points:

\begin{alignat}{27}
  & p_{ut} = \sum_{k=0}^{K} X_{utk} z_{utk}, \quad && \forall u \in \mathcal{U}, \forall t \in \mathcal{T}, \label{eq:ccX} \\
  & L_{ut} = \sum_{k=0}^{K} Y_{utk} z_{utk}, \quad && \forall u \in \mathcal{U}, \forall t \in \mathcal{T}, \label{eq:ccY} \\
  & \sum_{k=0}^{K} z_{utk} \leq y_{ut},  \quad && \forall u \in \mathcal{U}, \forall t \in \mathcal{T}. \label{eq:ccz}
\end{alignat}

In a standard convex combination model the last equation is written as $\sum_{k=0}^{K} z_{utk} = 1$.  However, in the case a unit is not committed in a given period, both the production level $p_{ut}$ and the linearized fuel cost $L_{ut}$ must be zero.  For taking this into account, in the right hand size of equation (\ref{eq:ccz}) instead of 1 there must be  variable $y_{ut}$, which indicates whether unit $u$ was committed to produce in period $t$ ($y_{ut} = 1$) or not ($y_{ut}=0$).  Additionally, for the model to be correct, there must be points corresponding to minimum and maximum operating powers, \emph{i.e.}, $X_{ut0} = P^{\mathsf{min}}} %%%{\underline{P}_u$ and $X_{utK} = P^{\mathsf{max}}} %%%{\overline{P}_u$, for each unit $u$ and period $t$.

For the minimization of non-convex functions represented by piecewise-linear segments, as in the present case, it is necessary to introduce binary variables, each corresponding to a $z_{utk}$, limiting which may be non-zero; also an additional constraint for forcing the convex combination to take on two consecutive points is necessary (\emph{i.e.}, there can be $z_{utk}>0$ and $z_{u,t,k+1}>0$ only for one value of $k\in\{0,\ldots,K-1\}$).  Alternatively, we may use a convenience of most modern MIP solvers that assures the same thing by declaring that, for each $u$ and $t$, the set of variables $z_{utk}, \forall k$ forms a so-called  \emph{special ordered set} constraint of type II (SOS2)~\cite{gurobi}.

The objective is to minimize the total production costs,
\begin{alignat}{27}
  \minim \sum_{t\in\mathcal{T}}\sum_{u\in\mathcal{U}} \left(L_{ut} + S_{ut}\right),  \label{eq:objective}
\end{alignat}
which include start-up costs $S_{ut}$; these are modeled as
\begin{alignat}{27}
  S_{ut} = a_u^{\mathsf{hot}}  s^{\mathsf{hot}}_{ut} + a_u^{\mathsf{cold}}  s_{ut}^{\mathsf{cold}},  \label{eq:startup}\\
\end{alignat}
where $a_u^{\mathsf{hot}}$ is the hot start up cost and variable $s^{\mathsf{hot}}_{ut}=1$ if there was a hot start for unit $u$ in period $t$, 0 otherwise.  Equivalently for cold start up, with $a_u^{\mathsf{cold}}$ and $s_{ut}^{\mathsf{cold}}$.  (See also constraints (\ref{eq:incurred_start_cost}) to~(\ref{eq:switch_off}).)

\subsection{Constraints}
\label{sec:constraints}

In this problem the following constraints will be considered: system power balance and generation limits (\emph{i.e.}, load dispatch), system reserve requirements, unit initial conditions, and unit minimum up and down times; this MIP model was introduced in~\cite{viana2013}.

Demand satisfaction is modeled by constraint~(\ref{eq:load}), and power reserve requirements by constraint~(\ref{eq:reserve}).
\begin{alignat}{27}
  & \sum_{u \in \mathcal{U}} p_{ut} = D_t, \quad && \forall t \in \mathcal{T}, \label{eq:load}\\
  & \sum_{u \in \mathcal{U}} P^{\mathsf{max}}} %%%{\overline{P}_{u} y_{ut} \geq D_t + R_t, \quad && \forall t \in \mathcal{T}. \label{eq:reserve}
\end{alignat}

Power production levels of thermal power units are within the range defined by the technical minimum and maximum production levels in~(\ref{eq:prod_limits}).
\begin{alignat}{27}
  & P^{\mathsf{min}}} %%%{\underline{P}_u y_{ut} \leq p_{ut} \leq P^{\mathsf{max}}} %%%{\overline{P}_{u} y_{ut}, \quad && \forall u \in \mathcal{U}, \forall t \in \mathcal{T}. \label{eq:prod_limits}
\end{alignat}

When a unit $u$ is switched on, it must remain on for at least $T_u^{\mathsf{on}}$ consecutive periods; similarly, it must be kept off for at least $T_u^{\mathsf{off}}$ after being switched off.  Constraints (\ref{eq:min_up_ini}) and (\ref{eq:min_down_ini}) model this aspect for the initial state, while constraints (\ref{eq:min_up}) and (\ref{eq:min_down}) do the same for the remaining planning horizon.  In (\ref{eq:min_up_ini}) $\theta^{\mathsf{on}}_u$ represents $\max(0,T_u^{\mathsf{on}} - t^{\mathsf{prev}}_u)$, and $\theta^{\mathsf{off}}_u$ in (\ref{eq:min_down_ini}) stands for $\max(0,T_u^{\mathsf{off}} - t^{\mathsf{prev}}_u)$; the previous state of unit $u$ is the parameter $y^{\mathsf{prev}}_u$, which is 1 if the unit was on, 0 if it was off.
\begin{alignat}{27}
  & y_{ut} = 1, \quad && \forall u\in\mathcal{U}: y^{\mathsf{prev}}_u = 1, \mathop{\text{ for }} t = 0,\ldots,\theta^{\mathsf{on}}_u,  \label{eq:min_up_ini} \\
  & y_{ut} = 0, \quad && \forall u\in\mathcal{U}: y^{\mathsf{prev}}_u = 0, \mathop{\text{ for }} t = 0,\ldots,\theta^{\mathsf{off}}_u.  \label{eq:min_down_ini}
\end{alignat}
Constraints (\ref{eq:min_up}) and (\ref{eq:min_down}) determine if a unit $u$ is started/switched off in period $t$ ($x^{\son}} %%%{\mathit{on}_{ut}=1, x^{\soff}} %%%{\mathit{off}_{ut}=1$, respectively, or $0$ otherwise); variables $\tau^{\mathsf{on}}_{ut}$ and $\tau^{\mathsf{off}}_{ut}$ stand for $\max(t - T_u^{\mathsf{on}} + 1, 1)$ and $\max(t - T_u^{\mathsf{off}} + 1, 1)$, respectively.
\begin{alignat}{27}
  & \sum_{i = \tau^{\mathsf{on}}_{ut}}^{t} x^{\son}} %%%{\mathit{on}_{ui} \leq  y_{ut},       \quad && \forall u \in \mathcal{U}, \forall t \in \mathcal{T}, \label{eq:min_up} \\
  & \sum_{i = \tau^{\mathsf{off}}_{ut}}^{t} x^{\soff}} %%%{\mathit{off}_{ui} \leq  1 - y_{ut}, \quad && \forall u \in \mathcal{U}, \forall t \in \mathcal{T}. \label{eq:min_down}
\end{alignat}

Constraints (\ref{eq:incurred_start_cost}) state that every time a unit is switched on, a start-up cost will be incurred.
\begin{alignat}{27}
  & s^{\mathsf{hot}}_{ut} + s^{\mathsf{cold}}_{ut} = x^{\son}} %%%{\mathit{on}_{ut},  \quad && \forall u \in \mathcal{U}, \forall t \in \mathcal{T}. \label{eq:incurred_start_cost}
\end{alignat}

Constraints (\ref{eq:set_start_cost}) determine the start-up type of each unit, \emph{i.e.}, decide whether it is a cold or a hot start type. It will be a cold start if the unit remained off for more than $ t^{\mathsf{cold}}_u$ periods of time, and a hot start otherwise.

\begin{alignat}{27}
  & y_{ut} - \sum_{i = t - t_u^{\mathsf{cold}} - 1}^{t-1} y_{ui} \leq s^{\mathsf{cold}}_{ut}, \quad && \forall u \in \mathcal{U}, \forall t \in \mathcal{T}. \label{eq:set_start_cost}
\end{alignat}

Constraints (\ref{switch_on}) determine each unit's switch-on variables, and (\ref{eq:switch_off}) determine the switch-off variables.
\begin{alignat}{27}
  & y_{ut} - y_{u,t-1} \leq x^{\son}} %%%{\mathit{on}_{ut},           \quad && \forall u \in \mathcal{U}, \forall t \in \mathcal{T}, \label{switch_on} \\
  & x^{\soff}} %%%{\mathit{off}_{ut} = x^{\son}} %%%{\mathit{on}_{ut} + y_{u,t-1} - y_{ut}, \quad && \forall u \in \mathcal{U}, \forall t \in \mathcal{T}. \label{eq:switch_off}
\end{alignat}

\subsection{Solution approach}
\label{sec:solution}

There is not, to the best of our knowledge, exact solution method for the load dispatching problem when the valve-point loading effect is taken into account, let alone the full unit commitment problem.  The solution approach that we propose achieves this, in the sense that it converges to a solution with an arbitrary degree of precision.

The method is based in the replacement of the function defined by Equation~(\ref{eq:valve}) by a piecewise-linear function; a careful selection of the breakpoints allows the construction of a model that provides a lower bound to the exact function.  Upon a feasible solution obtained by this linear model, we can evaluate the true function; this will provide an upper bound to the value of the objective.  As described in Algorithm~\ref{alg:solution}, if the deviation between the upper and lower bounds are within a user-specified tolerance, then the method will stop.  Otherwise, the number of breakpoints is increased (though only in the required intervals), thus leading to a better approximation, and the optimization problem is resolved.  This process is repeated until the relative deviation between upper and lower bounds is small enough (or the allowed CPU time is exceeded).  Notice that the solution of an iteration is feasible to the problem of the next, the only changes are in its evaluation.  We can, therefore, supply it as a starting point to the MIP solver in line (\ref{itm:solve}) of the algorithm.

\begin{myalg}[htb!]
\caption{Solution procedure.}
\label{alg:solution}
\begin{footnotesize}
\alginout{UCP instance, CPU limit, tolerance}{A solution to the input instance}
\begin{algtab}
  \algforeach{unit $u \in \mathcal{U}$, period $t \in \mathcal{T}$:}
  $B_{ut} := $ set of breakpoints containing only the valve points\\
  \algend
  \algwhile{\algtrue}
  solve problem with piecewise-linear objective, breakpoints $B$  \label{itm:solve}\\
  \algif{$UB - LB <$ tolerance \algor CPU limit exceeded:}
  \algreturn solution\\
  \algend
  \algforeach{$u, t$ with coarse objective representation in the solution:}
  divide the inter-valve interval containing $p_{ut}$ into $K$ segments\\
  add corresponding points to $B_{ut}$\\
  \algend
  \algif{there were no $u,t$ with coarse objective in $p_{ut}$:}
  $K := 2 K$\\
  for each $u,t$ recompute $B_{ut}$ based on $K$ segments in the inter-valve interval containing $p_{ut}$\\
  \algend
  \algend

\end{algtab}
\end{footnotesize}
\end{myalg}

The value $K$ used in this algorithm should ideally be setup in such a way that the initial approximation is just good enough to solve the instance with sufficient precision.  If $K$ is set too high, there will be too many intervals in the piecewise-linear representation of the objective function, leading to great precision but requiring unnecessary CPU for solving the problem; if is it set too low, additional iterations will be necessary for providing the required precision (each iteration doubling the value of $K$), and again unnecessary CPU will be used.

The most important properties of this algorithm are summarized next.  Let us denominate $P_1$ the problem of maximizing the true objective,
\begin{alignat}{27}
  \minim \sum_{t\in\mathcal{T}}\sum_{u\in\mathcal{U}}
  \left[ S_{ut} + y_{ut} F_{ut}(p_{ut}) \right] \label{eq:trueobj}
\end{alignat}
where $$F_{ut}(p) = a_u + b_u p + c_u p^2 + \left|e_u \sin\left(f_u (P^{\mathsf{min}}} %%%{\underline{P}_{ut}-p) \right) \right|,$$
under constraints (\ref{eq:startup}) to~(\ref{eq:switch_off}), and $P_2$ its linearized counterpart, \emph{i.e.}, the problem of maximizing~(\ref{eq:objective}) under the same constraints and additionally (\ref{eq:ccX}), (\ref{eq:ccY}) and~(\ref{eq:ccz}).

\begin{figure}[!htbp]
\centering
\begin{minipage}{1.07\linewidth}
\hspace{-.05\linewidth}
\resizebox{.51\linewidth}{!}{\input{concavity_A}}
\resizebox{.51\linewidth}{!}{\input{concavity_B}}
\end{minipage}
\caption{Linear approximations in consecutive iterations.}
\label{fig:cost_shape}
\end{figure}

\begin{property}
  \label{prop:feas}
  Feasible solutions for $P_2$ are feasible for $P_1$.
\end{property}
\begin{proof}
  $P_2$ includes all the variables of $P_1$, and contraints of $P_2$ are a superset of constraints of $P_1$.
\end{proof}

\begin{property}
  The evaluation of the objective function~(\ref{eq:trueobj}) at a feasible solution obtained for $P_2$ is an upper bound to the optimum of $P_1$.
\end{property}
\begin{proof}
  Follows from Property~\ref{prop:feas} and from the notion of optimum: the objective at any feasible solution of a minimization problem provides an upper bound to its optimum.
\end{proof}

\begin{property}
  An optimum of $P_2$ is a lower bound to the optimum of $P_1$.
\end{property}
\begin{proof}
  Between two consecutive valve points the function $F(p)$ defined by Equation~\ref{eq:valve} is concave as long as $c \leq e f^2 / 2$ (see~\ref{sec:concavity}); therefore, if this condition is observed, any piecewise-linear interpolation between consecutive valve points is not larger than $F$.  In the construction of the piecewise-linear approximation we are considering all the valve points, as well as the extreme point of the domain of $F$, as interpolation points; hence, the linear interpolation is not larger than $F$ in its domain.  We can thus conclude that the minimum of $P_2$ --- where the objective is a linear interpolation in the previous conditions --- is not larger than the minimum of $P_1$, where the objective is function~$F$.
\end{proof}

\begin{property}

  With tolerance $\epsilon = 0$, when the number of iterations increases the solution provided by Algorithm~\ref{alg:solution} converges to the optimum solution of~$P_1$.
\end{property}
\begin{proof}
  Let us denote the linear approximation of $F$ at an iteration $i$ by $G_i$, and define $G = \lim_{i\rightarrow\infty}G_i$.  Note that $G_j(p) \geq G_i(p)$, for any $j>i$, and for all $p$ in the domain of $F$.  As functions $G_i$ are non-decreasing with increasing $i$ and are limited above by $F$, the sequence $G_i$ converges.

It remains to prove that the optimum solution with $G_i$ as the objective function, when $i$ tends to infinity, is an optimum solution with $F$ as the objective function.  We will assume that this is not true, \emph{i.e.}, that the optimum $F^*$ is strictly greater than $G^*$, and show that this leads to a contradiction.  Notice that $F^* > G^*$ is equivalent to $F^* - G^* = \epsilon^*$, with $\epsilon^*>0$, which implies that there must be some $u,t$ such that $F_{ut}(p^*) - G_{ut}(p^*) = \epsilon' > 0$.  However, lines (11) and (12) of Algorithm~\ref{alg:solution} imply that the number of segments in each inter-valve interval containing $p_{ut}^*$ tends to infinity when the number of iterations tends to infinity.  This means that $G_{ut}(p^*)$ becomes arbitrarily close to $F_{ut}(p^*)$, and hence $\epsilon'$ cannot be positive.
\end{proof}

\section{Computational results}
\label{sec:results}

In order to run economic load dispatch instances with the current model we must set up an instance with only one period; generators must have the previous status as operating, and must be forced to keep operating by adjusting the minimum number of on periods.  We have thus prepared data for the most widely used benchmark instances for load dispatching with valve-point loading effect: \emph{eld13} (first described in \cite{wood1984}) and \emph{eld40} (first described in \cite{sinha2003}); we have used the tables available in \cite{coelho2006}\footnote{All the data and programs used are available in this paper's Internet page, \url{http://www.dcc.fc.up.pt/~jpp/code/valve}}.

The setup used was the following: a computer with an Intel Xeon processor at 3.0 GHz and running Linux version 2.6.32, using Gurobi version 5.0.1~\cite{gurobi}.  Only one thread was assigned to this experiment.  Models were written in the Python language and the default Gurobi parameters were used until reaching the user-defined tolerance; then, parameters were changed to the maximum precision supported by Gurobi.  The aim of this procedure is to avoid spending too much CPU in the initial iterations, where the representation of the objective function is still rather course.

\begin{table}[!htbp]
  \centering
  \begin{tabular}{l|r|r|r|r|r|r}
    \hline
    Instance & Load      & Lower bound & Upper bound & Error    & CPU time      & $N$   \\\hline
    \emph{eld13}    & 1800      &  17963.83   &  17963.83   & $<$1.e-7 & 19.1s  & 34  \\
    \emph{eld13}    & 2520      &  24169.92   &  24169.92   & $<$1.e-7 &  1.8s  & 19  \\
    \emph{eld40}    & 10500     & 121412.53   & 121412.54   & $<$1.e-7 &  7.6s  & 27  \\
    \hline
  \end{tabular}
  \caption{Solution to economic load dispatch instances: bounds to the objective value, maximum relative error, CPU time employed, and number of iterations performed.}
  \label{tab:eld}
\end{table}

The results presented in Table~\ref{tab:eld} are optima, and are approximately equal to the best solutions found by the best methods available in the literature~\cite{SrinivasaReddy2013342}.\footnote{Results presented in~\cite{Coelho20102580} are better than the optimum for \emph{eld13}, indicating that there is likely an error in that paper.  Possibly this is due to a rounding error; if we calculate the cost for the solutions provided in the paper we obtain values greater than those reported.}

As for the unit commitment problem, to the best of our knowledge there are no test instances taking into account the valve-point effect.  We have therefore prepared a set of benchmarks, based on the instances for unit commitment provided in~\cite{kazarlis1996}, and on the instances for economic load dispatch mentioned above.  Instance \emph{ucp10} corresponds to the standard instance described in~\cite{kazarlis1996}; \emph{ucp5} is based on that instance, by selecting only half of the units and adjusting demand.  Instances \emph{ucp13} and \emph{ucp40} have costs taken from \emph{eld13} and \emph{eld40}, respectively, and data concerning multi-period operation based on~\cite{kazarlis1996}.  Notice that the difference between instances \emph{eld13} and \emph{ucp13} with one period (besides possible differences in the demand value) is that in the former the commitment decision has already been made, and all units considered must be operating; the same for \emph{eld40} and \emph{ucp40}.  These results are presented in Table~\ref{tab:ucp}.  Figure~\ref{fig:bound} plots the evolution, for a particular case, of the lower and upper bounds with respect to the iteration number; as expected, the lower bound is non-decreasing, whereas the upper bound may increase (when the linear approximation at the solution of the previous iteration was poor).

\begin{table}[!htbp]
  \centering
  \begin{tabular}{l|r|r|r|r|r@{.}l|r}
    \hline
    Instance & Periods   & Lower bound & Upper bound & Error  & \multicolumn{2}{r|}{CPU time} & $N$ \\\hline
\emph{ucp5}  & 1  &     7352.46 &    7352.46 & $<$1.e-7   &    0&12  &  5   \\
\emph{ucp5}  & 3  &    24506.12 &   24506.12 & $<$1.e-7   &    0&29  &  5   \\
\emph{ucp5}  & 6  &    59127.38 &   59127.39 & $<$1.e-7   &    1&2   &  6   \\
\emph{ucp5}  & 12 &   153575.68 &  153575.69 & $<$1.e-7   &   54&    &  7   \\
\emph{ucp5}  & 24 &   308482.03 &  309152.47 & 0.22\%     & 3600&    &  3   \\ \hline
\emph{ucp10} & 1  &    13826.85 &   13826.85 & $<$1.e-7   &    0&17  &  6   \\
\emph{ucp10} & 3  &    45929.36 &   45929.36 & $<$1.e-7   &    1&3   &  7   \\
\emph{ucp10} & 6  &   109919.97 &  109919.98 & $<$1.e-7   &   31&    &  9   \\
\emph{ucp10} & 12 &   285808.54 &  286067.44 & 0.091\%    & 3600&    &  5   \\
\emph{ucp10} & 24 &   572943.80 &  574554.02 & 0.28\%     & 3600&    &  3   \\ \hline
\emph{ucp13} & 1  &    11701.28 &   11701.28 & $<$1.e-7   &    0&15  &  6   \\
\emph{ucp13} & 3  &    38849.84 &   38849.84 & $<$1.e-7   &    3&3   & 11   \\
\emph{ucp13} & 6  &    91405.97 &   91783.98 & 0.41\%     & 3600&    & 10   \\
\emph{ucp13} & 12 &   231587.47 &  232537.37 & 0.41\%     & 3600&    &  4   \\
\emph{ucp13} & 24 &   464053.01 &  466186.98 & 0.46\%     & 3600&    &  3   \\ \hline
\emph{ucp40} & 1  &    55644.79 &   55644.79 & $<$1.e-7   &    3&9   & 25   \\
\emph{ucp40} & 3  &   178395.51 &  178547.12 & 0.085\%    & 3600&    & 30   \\
\emph{ucp40} & 6  &   416108.42 &  416605.93 & 0.12\%     & 3600&    & 15   \\
\emph{ucp40} & 12 &  1112370.94 & 1113801.09 & 0.13\%     & 3600&    & 11   \\
\emph{ucp40} & 24 &  2235970.56 & 2238504.45 & 0.11\%     & 3600&    &  7   \\
    \hline
  \end{tabular}
  \caption{Solution to unit commitment instances: bounds to the objective value, maximum relative error, CPU time employed, and number of iterations performed.}
  \label{tab:ucp}
\end{table}

\begin{figure}[!t]
\begin{minipage}{1.2\linewidth}
\begin{centering}
~\hspace{-0.2\textwidth}
\includegraphics[width=.48\columnwidth]{ucp40-1}
\includegraphics[width=.48\columnwidth]{ucp40-3}
\par\end{centering}
\end{minipage}
\caption{\textit{Bounds as a function of the iteration number, for instance \emph{ucp40} with one period (optimal solution was found) and three periods (final solution was not optimal).}\label{fig:bound}}
\end{figure}

\section{Conclusions}
\label{sec:conclusions}

The main contribution of this paper is a model and an algorithm for solving the unit commitment problem taking into consideration the valve-point loading effect in fuel cost computation.  This model can be used for planning which units to commit in each period so as to match demand, meeting reserve constraints, and under a set of technological constraints.  The algorithm iteratively calls a general-purpose mixed-integer programming solver for tackling optimization subproblems, and uses the solution to improve the accuracy of fuel cost approximation until reaching an error below a given tolerance, or reaching a given limit on CPU usage.

The model can also be used for load dispatching, when only one period is considered and the subset of units that will operate is already selected; this is known as the economic load dispatch problem with valve-point effect; the method proposed was able to solve well known benchmark instances of this problem for which the optimum was not known.

To the best of our knowledge, there are no standard benchmarks for unit commitment taking into account the valve-point loading effect.  We present a set of them, based on data from load dispatch and unit commitment.  Using our algorithm for their solution, the optimum was obtained for a subset of instances, and very good approximations, with a relative error below 1\%, were found for the remaining.

\section*{Acknowledgements}
This work was partly funded by project ``NORTE-07-0124-FEDER-000057'', under the North Portugal Regional Operational Programme (ON.2 – O Novo Norte) and the National Strategic Reference Framework through the European Regional Development Fund, and by national funds through Funda{\c c}{\~a}o para a Ci{\^e}ncia e a Tecnologia (FCT), and by FCT (under Project PTDC/EGE-GES/099120/2008) through ``Programa Operacional Tem\'atico Factores de Competitividade (COMPETE)'' of ``Quadro Comunit\'ario de Apoio III'', partially funded by FEDER.

\bibliographystyle{model3-num-names}


\section{Introduction}

Multidimensional convolutional codes are natural generalizations of classical (one-dimensional)
convolutional codes and are used to transmit
multidimensional data. They have been studied quite a
bit in the literature and we refer the reader
to     Fornasini and Valcher \cite{FV},  Valcher and Fornasini \cite{VF}, Weiner \cite{W}
 and more recent works Charoenlarpnopparut \cite{C}, Gluesing-Luerssen et al. \cite{GRW}, Jangisarakul and Charoenlarpnopparut \cite{JC}, Kitchens \cite{K}, Napp Avelli et al.
\cite{NPP1,NPP2}, Zerz \cite{Z}.

In this article, we would like to offer a new view-point on some
 fundamental issues of algebraic character related to multidimensional convolutional codes.

Throughout,  $\mathbb{F}$ is an arbitrary (finite) field, $n$  a fixed positive integer,
and $D=(D_1,\ldots ,D_n)$  a sequence of indeterminates. We let $S=\mathbb{F}[D]$. For
every  $d\in \mathbb{Z}$, we shall write $S_{\leq d}$ to denote the space of polynomials of degree
$\leq d$.

Following Weiner \cite{W} and other authors, by a  convolutional code of length $q$ we  mean
  a submodule  of $S^q$.
If $C$ is a convolutional code of length  $q$, then, for each $d\geq 0$, define
$
C_{\leq d}=C\cap S^q_{\leq d}
$
to be the space of codewords of degree $\leq d$.

In dimension 1, a submodule $C\subseteq S^q$ is free, and it is possible therefore
 to represent it via a full column rank polynomial matrix. In other words, there exist an integer $p$ and a polynomial matrix
$G\in S^{q\times p}$ such that
$$
0\ra S^p\stackrel{G}{\ra} C\ra 0
$$
is an exact sequence.
A higher-dimensional counterpart of this well-known fact is
Hilbert's syzygy theorem, according to  which there exists  $1\leq l \leq n$, and there exist integers
$p_1, \ldots , p_l \geq 1$ and polynomial matrices $G_1, \ldots , G_l$ of sizes
$q\times p_1, \ldots , p_l\times p_{l-1}$, respectively, such that the sequence
$$
0\ra S^{p_l}\stackrel{G_l}{\ra} S^{p_{l-1}}\ra \cdots \ra S^{p_1}\stackrel{G_1}{\ra} C\ra 0
$$
is exact.  This celebrated theorem suggests  to define higher-dimensional analogs of classical full column rank polynomial matrices
as sequences $(G_l, \ldots , G_1)$ of polynomial matrices satisfying the above exactness condition.

Starting with this idea, we  shall define higher-dimensional analogs of  the predictable degree property and column reducedness,
and prove that
the two properties are equivalent. We shall see that every multidimensional convolutional code has, what we call, a minimal
reduced polynomial resolution. It is uniquely determined (up to isomorphism) and  provides a number of important
integer invariants of the code that generalize classical Forney's indices.

 Recall that the degree of a
 column $f$ with entries in $S$ is defined to be the maximum of the degrees of the components of $f$; it is denoted by $\deg(f)$.
We shall need {\em relative} degrees as well.
Any function $[1, p] \ra \mathbb{Z}_+$ will be referred to as a twisting (or degree) function of length $p$. If $a$ is a twisting function
of length $p$, then, for
 $f\in S^p$, we set
$$\deg_a(f)=\max_i\{a(i)+\deg(f_i)\}.
$$
(If $f$ is zero, then $\deg_a(f)=-\infty$.) Notice that $\deg(f)=\deg_0(f)$.

 Without loss of generality, we shall always consider polynomial matrices
with no zero column. For such matrices, we can define (column) degree functions.
The  degree function of  a polynomial matrix $G\in S^{p\times q}$, denoted by $\deg(G)$, is the
function that assigns to every $j\in [1, q]$ the degree of the $j$-th column of $G$. More generally, if
 $a$ is a twisting function
of length $p$, we define the $a$-degree function $\deg_a(G):[1,q] \ra \mathbb{Z}_+$ to be the function
that assigns to every $j\in [1, r]$ the $a$-degree of the $j$-th column of $G$.
This is a degree function of length $q$.

By a  polynomial complex of length $l$, we shall mean a sequence $(G_l,\ldots , G_1)$ of polynomial matrices,
such that the products
$G_1G_2,\ \ldots ,\ G_{l-1}G_l$ (are defined and) are zero.
The size is defined to be  $q\times (p_l, \ldots ,p_1)$, where $q$ is the row number of $G_1$ and $p_1, \ldots , p_l$ are
 the column numbers of $G_1, \ldots , G_l$.
We say that $(G_l,\ldots , G_1)$ is a polynomial resolution  if
$$
0\ra S^{p_l}\stackrel{G_l}{\ra} S^{p_{l-1}}\ra \cdots \ra S^{p_1}\stackrel{G_1}{\ra} S^q.
$$
is an exact sequence.

If $C$ is a convolutional code, then, as already said, Hilbert's syzygy theorem guarantees existence of
 a polynomial resolution $(G_l,\ldots , G_1)$ such that
$\tx{Im}(G_1)=C$. The number $l$, called the homological dimension of $C$, is an important integer invariant of $C$. This number measures the complexity of $C$ and indicates how far is $C$ from being free.
 Free convolutional codes
are exactly convolutional codes of homological dimension 1.

  The point of convolutional codes is that they admit a  natural
 {\em homogenization}, and this permits us to study them using the method of graded modules. We introduce  an extra ("homogenizing") indeterminate $D_0$, and  define $T=\mathbb{F}[D_0,D]$. Given an integer function
 $a:[1,p]\ra \mathbb{Z}$, we shall write $D_0^a$ for the diagonal matrix with $D_0^{a(1)}, \ldots , D_0^{a(p)}$ on the diagonal.

This article has much overlaps with \cite{L2}. The relevant results from \cite{L2} are reproduced in a rather sketched form. The main new contribution is Theorem 1, which generalizes Forney's classical theorem stating that
a full column rank polynomial matrix has the predictable degree property if and only if its leading coefficient matrix
has full column rank.

\section{Filtered modules, and the PD property}

Let $M$ be a module over $S$.
A filtration on $M$ is an ascending chain
 $$M_{\leq 0} \subseteq M_{\leq 1} \subseteq  M_{\leq 2} \subseteq \cdots $$
 of linear subspaces of $M$
such that $$M=\bigcup M_{\leq d}\ \ \ \tx{and}\ \ \
  D_kM_{\leq d} \subseteq M_{\leq d+1}\ \forall k,d.
$$
A module equipped with a filtration is called a filtered module.

A twisting function $a:[1, p]\ra \mathbb{Z}_+$ determines on
$S^p$  a  filtration  consisting of the spaces
$$
S^p[-a]_{\leq d}=\{f\in S^p |\ \deg_a(f)\leq d \} \ \ \ (d\geq 0).
$$
The module $S^p$ equipped with this filtration is denoted by $S^p[-a]$.
Given a submodule  $C\subset S^p$, we shall write $C[-a]$ to denote
the module $C$ together with the filtration induced from $S^p[-a]$, that is,
$$
C[-a]_{\leq d}=C\cap S^p[-a]_{\leq d}.
$$

A homomorphism of filtered modules $(M, (M_{\leq d}))\ra (N, (N_{\leq d}))$ is a homomorphism $u:M\ra N$ such that
$$\forall d\geq 0,\ \ \ u(M_{\leq d})\subseteq N_{\leq d}.$$

{\em Example}. If $a: [1, p]\ra \mathbb{Z}_+$ and $b: [1, q]\ra \mathbb{Z}_+$ are two  functions, then
$$
\tx{Hom}(S^q[-b],S^p[-a])= \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
$$
$$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \{(g_{ij})\in S^{p\times q}|\ \deg(g_{ij})\leq b(j)-a(i)\}.
$$

Certainly, filtered modules and their homomorphisms form a category.
Consequently, we may speak,  in particular, about isomorphisms between filtered modules.

\begin{lem} Let $a: [1, p]\ra \mathbb{Z}_+$ and $b: [1, q]\ra \mathbb{Z}_+$ be two twisting functions. If
$$
  S^p[-a] \ \simeq \ S^q[-b],
$$
then \ $p=q$ and $a=b$ (up to permutation).
\end{lem}

{\em Proof}.  That $p=q$ is obvious. Proving the second equality, we may assume that $a$ and $b$ are increasing functions.
Suppose that $a\neq b$, and let $i$ be the smallest number such that $a(i)\neq b(i)$. Say that $a(i)>b(i)$. Letting $d=a(i)$, we have:
$$
S^p[-a]_{\leq d} \ \simeq \ S^p[-b]_{\leq d}.
$$
But the left side here is equal to
$$
S_{\leq a(1)-d}\oplus \cdots \oplus S_{\leq a(i-1)-d}\oplus \mathbb{F} \oplus \cdots
$$
and the right side is
$$
S_{\leq b(1)-d}\oplus \cdots \oplus S_{\leq b(i-1)-d}.
$$
We get a contradiction.
 $\quad\Box$

The category of filtered modules is not  abelian.  Nevertheless, we may speak about  exact
sequences in it. Call
a complex of filtered modules
$$
(F_l,(F_{l,\leq d}))\stackrel{\delta_l}{\ra} \cdots \stackrel{\delta_2}{\ra}
  (F_1,(F_{1,\leq d}))
\stackrel{\delta_1}{\ra} (F_0,(F_{0,\leq d}))
$$
 exact if the sequence
$$
F_{l,\leq d}\stackrel{\delta_l}{\ra} \cdots \stackrel{\delta_2}{\ra}
  F_{1,\leq d}
\stackrel{\delta_1}{\ra} F_{0,\leq d}
$$
is exact for all $d\geq 0$.

\begin{lem} If a complex of filtered modules
$$
(F_l,(F_{l,\leq d}))\stackrel{\delta_l}{\ra} \cdots \stackrel{\delta_2}{\ra}
  (F_1,(F_{1,\leq d}))
\stackrel{\delta_1}{\ra} (F_0,(F_{0,\leq d}))
$$
is  exact, then the complex  of modules
$$
F_l\stackrel{\delta_l}{\ra} \cdots \stackrel{\delta_2}{\ra}
  F_1
\stackrel{\delta_1}{\ra} F_0
$$
also is exact.
\end{lem}

{\em Proof}. This is obvious  because $F_i=\lim_{d\ra 0}F_{i,\leq d}$ (and because the direct limit functor is an exact functor).
 $\quad\Box$

{\bf Definition.}\  Let $G=(G_l,\ldots , G_1)$ be a polynomial complex, and
let $q\times (p_l, \ldots ,p_1)$ be its size.
 Define the degree  functions
 $$
 a_i:[1,p_i]\ra \mathbb{Z}_+,\ \ i=1,\ldots , l
 $$
 recursively as follows. Put
$a_0=0$, and if $a_i$ is defined,  define $a_{i+1}$ to  be
$$
a_{i+1}=\deg_{a_i}(G_{i+1}).
$$
Call $(a_l, \ldots ,a_1)$ the column degree table of $G$.
The  polynomial complex $G$ gives rise to  the following complex of filtered modules
\begin{equation}
0\ra S^{p_l}[-a_l]\stackrel{G_l}{\ra}  \cdots \stackrel{G_2}{\ra} S^{p_1}[-a_1]
\stackrel{G_1}{\ra} C[0]\ra 0.
\end{equation}
We say that $G$
  has the PD (predictable degree) property if this complex is exact.

The following example justifies the above definition.

{\em Example}. Assume $n=1$. Following Forney \cite{F},
a polynomial matrix $G\in S^{q\times p}$ is said to have  the PD property if, for every $f\in S^p$,
$$
\deg(Gf)=\deg_a(f),
$$
where $a$ is the column degree function  of $G$.
 For each $d\geq 0$, $G$ determines a linear map
$$
S^p[-a]_{\leq d}\ra C_{\leq d},
$$
and it is easily seen that $G$ has the PD property in the sense of Forney if and only if all these linear maps are bijective.

Let $C$ be a convolutional code of length  $q$.
Define the Hilbert function of $C$ as
$$
\tx{HF}(C,d)=\dim_\mathbb{F}(C_{\leq d}), \ \ \ d\in \mathbb{Z}_+.
$$
This can be easily computed from the column degree table of a  polynomial resolution of
$C$ having the PD property. Indeed, if
 $(G_l,\ldots , G_1)$ is such a resolution and if
  $(a_l, \ldots ,a_1)$ is its column degree table, then, for each $d\geq 0$,
  \begin{equation}
0\ra S^{p_l}[-a_l]_{\leq d}\stackrel{G_l}{\ra} \cdots \stackrel{G_2}{\ra}
S^{p_1}[-a_1]_{\leq d}\stackrel{G_1}{\ra} C_{\leq d}\ra 0
\end{equation}
is an exact sequence of finite-dimensional linear spaces.
As is known, the dimension of the space of polynomials
of degree $\leq d$, where $d\in \mathbb{Z}$,  is equal to $\left(\begin{array}{c}d+n\\n\end{array}\right)$ (with the  convention that
$\left(\begin{array}{c}d+n\\n\end{array}\right)=0$ when $d\leq -1$).
It immediately follows from (2) therefore that
$$
\tx{HF}(C,d)=\sum_{i=1}^l(-1)^{i-1}\sum_j \left(\begin{array}{c}d-a_i(j)+n\\ n\end{array}\right).
$$

{\em Remarks}.  Hilbert functions  were introduced by Hilbert  in the context of graded finitely generated modules.
For one-dimensional convolutional codes, they have been defined in McEliece and Stanley \cite{MS}. Notice that
the above expression
for Hilbert function is a generalization of that given in [Corollary 3.2, 13].

\section{The homogenization and the leading term complex}

According to Lemma 2, the polynomial complexes having the PD property are polynomial resolutions
necessarily. The converse is not true, and the  goal of this section is to obtain  a test
to establish whether a polynomial resolution has the predictable degree property or not.

We need to recall the notion of graded modules.

Let $M$ be a module over $S$ or $T$. A gradation on $M$ is a sequence $$M_0,M_1,M_2,\ldots $$ of $\mathbb{F}$-linear subspaces of $M$
such that
$$
M=\bigoplus M_d \ \ \ \tx{and}\ \ \ D_kM_d\subseteq M_{d+1}\ \forall k,d.
$$
A module equipped with a gradation is called a graded module.

{\em Example}. Let $R$ be either $S$ or $T$. A twisting function $a$
of length $p$ determines on $R^p$ the gradation  consisting of the spaces
$$
R^p(-a)_d=\{f\in S^p |\ \deg(f_i)= d-a(i) \} \ \ \ (d\geq 0).
$$
The module $R^p$ equipped with this gradation will be denoted by
$R^p(-a)$.

A homomorphism of graded modules $(M, (M_{d}))\ra (N, (N_{d}))$ is a homomorphism $u:M\ra N$ such that
$$\forall d\geq 0,\ \ \ u(M_{d})\subseteq N_{d}.$$
Graded modules  form an abelian category, and one therefore has the notion of exact
sequences. It is worth noting  that
a complex of graded modules
$$
(F_l,(F_{l,d}))\stackrel{\delta_l}{\ra} \cdots \stackrel{\delta_2}{\ra}
  (F_1,(F_{1,d}))
\stackrel{\delta_1}{\ra} (F_0,(F_{0,d}))
$$
is exact if only if the sequence of linear spaces
$$
 F_{l,d}\stackrel{\delta_l}{\ra} \cdots \stackrel{\delta_2}{\ra}
  F_{1,d}
\stackrel{\delta_1}{\ra} F_{0,d}
$$
is exact for all $d\geq 0$.

The homogenization in degree $d$ is the bijective linear map
$$
S_{\leq d}\ra T_d
$$
defined by
$$f(D)\mapsto D_0^df(D/D_0).$$ (Here and below $D/D_0$ means $(D_1/D_0,\ldots , D_n/D_0)$.)

({\em Warning}: It is essential  to indicate the "$d$". For instance, the homogenization in degree 4 of the polynomial $2D_1^3D_n+1$ is
 $2D_1^3D_n+D_0^4$ and the homogenization in degree 5 is $2D_0D_1^3D_n+D_0^5$.)

Let $C\subseteq S^p$ be a convolutional code.
The homogenization $C^H$ of $C$ is defined to be
$$C^H=\bigoplus_{d\geq 0} C^H_d,$$
where $C^H_d$ is the image of $C_{\leq d}=C\cap \mathbb{F}[s]^p_{\leq d}$ under the homogenization operator
$S^p_{\leq d}\ra T^p_d$.
This is a "homogeneous convolutional code" in $T^p$.

{\bf Definition} \ Let $G=(G_l,\ldots ,G_1)$ be a polynomial complex, and let $q\times (p_l,\ldots ,p_1)$
be its size and $(a_l,\ldots ,a_1)$ the column degree.

a) The homogenization of $G$ is the sequence $G^H=(G_l^H,\ldots ,G_1^H)$ of homogeneous polynomial matrices,
where $G_k^H=D_0^{-a(k)}G_k(D/D_0)D_0^{a(k+1)}$.

b) The  leading term complex of $G$  is the sequence $G^L=(G_1^L,\ldots ,G_l^L)$ of
homogeneous polynomial matrices, where
$G_k^L$ is defined as follows. The  $(i,j)$ entry of $G_k^L$ is
the homogeneous  ($a_{k+1}(j)-a_k(i)$)-th part of the $(i, j)$ entry of $G_k$.

These two sequences  give rise respectively to the following complexes of graded modules:
\begin{equation}
0\ra T^{p_l}(-a_l)\stackrel{G_l^H}{\ra}  \cdots \stackrel{G_2^H}{\ra} T^{p_1}(-a_1)
\stackrel{G_1^H}{\ra} T^q(0)
\end{equation}
and
\begin{equation}
0\ra S^{p_l}(-a_l)\stackrel{G_l^L}{\ra}  \cdots \stackrel{G_2^L}{\ra}
S^{p_1}(-a_1)\stackrel{G_1^L}{\ra} S^q(0).
\end{equation}
We remark that
$$
G^L(D)=G^H(0,D),
$$
that is, $G^L$ is obtained from $G^H$ by replacing $D_0$ by 0.

\begin{thm} Let $G=(G_l,\ldots, G_1)$ be a polynomial complex, and let $q\times (p_l,\ldots ,p_1)$ be its size
and $(a_l,\ldots ,a_1)$ the column degree. The following three conditions are
equivalent:

(a) $G$ has the PD property;

(b) $ImG_1^H=C^H$ and the complex (3) is exact;

(c) $G$ is a polynomial resolution and the complex (4) is exact.
\end{thm}

{\em Proof}. (a)\ $ \Leftrightarrow $ \ (b) This is obvious since the complex (2)
is isomorphic to the complex
$$
0\ra T^{p_l}(-a_l)_d\stackrel{G_l^H}{\ra}  \cdots \stackrel{G_2^H}{\ra}
  T^{p_1}(-a_1)_d\stackrel{G_1^H}{\ra} C^H_d\ra 0.
$$
(b)\ $\Rightarrow $ \ (c)  We have an exact sequence
$$
0\ra T^{p_l}(-a_l)\stackrel{G_l^H}{\ra}  \cdots \stackrel{G_2^H}{\ra} T^{p_2}(-a_2)\stackrel{G_1^H}{\ra} T^q\ra T^q/C^H.
$$
We claim that $D_0$ is not a zero divisor on $T^q/C^H$.
Suppose that $u\in T^q_d$ is such that $D_0u\in C^H_{1+d}$. Then $u(1,D)\in C$.
 Since
$u(1,D)$ has degree $\leq d$, we have $u(1,D)\in C_{\leq d}$. Clearly, $u$ is the $d$-homogenization of
$u(1,D)$, and therefore belongs to $C^H_d$.
Using Corollary 1 in  \cite{L1}, we can see that the sequence
$$
0\ra T^{p_l}(-a_l)\stackrel{G_l^H}{\ra} T^{p_{l-1}}(-a_{l-1})\ra \cdots \stackrel{G_1^H}{\ra} T^q.
$$
remains exact after tensoring it by $T/D_0T=S$. Notice that replacing $D_0$ by 0 in each entry of $G_i^H$, we get $G_i^L$. This means that
$$G_i^H\otimes T/D_0T=G_i^L.$$
(b)\ $\Rightarrow $ \ (a)  Let $d\geq 0$. We have to show that the sequence
 $$
0\ra S^{p_l}[-a_l]_{\leq d}\stackrel{G_l}{\ra} \cdots \stackrel{G_2}{\ra}
  S^{p_1}[-a_1]_{\leq d}
\stackrel{G_1}{\ra} C_{\leq d}\ra 0
$$
is exact. For $1\leq i\leq l-1$, we set
$$ X_i=
Ker(S^{p_i}[-a_i]_{\leq d}\stackrel{G_i}{\ra}S^{p_{i-1}}[-a_{i-1}]_{\leq d});
$$
if $i=0$, define $X_i$ to be $C_{\leq d}$.

Take any $x\in X_i$. By the hypothesis,
there exists $y\in  S^{p_{i+1}}$ such that $G_{i+1}y=x$. If  $\deg_{a_{i+1}}(y)\leq d$, we are done.
 If $k=\deg_{a_{i+1}}(y)> d$, write
 $$y=y^L+y^{\prime}$$
 with $y^L\in S^{p_{i+1}}(-a_{i+1})_k$ and $y^\prime \in S^{p_{i+1}}[-a_{i+1}]_{\leq k-1}$.
 It is clear that $G_{i+1}^Ly^L=0$. Hence, by the hypothesis,
 $G_{i+2}^Lz=y^L$ for some   $z\in S^{p_{i+2}}(-a_{i+2})_k$.
Consider the element $y_1=y-G_{i+2}z$. It has $a_{i+1}$-degree $<k$ and $$G_{i+1}y_1=G_{i+1}y-G_{i+1}G_{i+2}z=G_{i+1}y=x.$$
Using induction, we find  that there  exists an element in $S^{p_{i+1}}[-a_{i+1}]_{\leq d}$ that goes to $x$.

The proof is complete.
 $\quad\Box$

{\bf Definition.}\
Let $G=(G_1,\ldots, G_l)$ be a polynomial complex, and let $q\times (p_l,\ldots ,p_1)$ be its size
and $(a_l,\ldots ,a_1)$ the column degree. Say that $G$ is (column) reduced if the complex (4) is exact.

We thus have the following statement.

\begin{cor}
A polynomial resolution has the PD
property if and only if it is reduced.
\end{cor}

{\em Remark}.  In dimension 1, if $G$ is a full column
rank polynomial matrix with degree function $a$, then $G^L$ is equal to the leading coefficient matrix multiplied by the diagonal matrix
with $D^{a(i)}$ on the diagonal.
For example, if
$$
G=\left[\begin{array}{cc}2D^3+D+1&D^2-10\\
D^2-5&D+4\\
3D^4+7D&D^2+1
\end{array}\right],
$$
then the column degree is equal to $(4,2)$, and we have
$$
G^L=\left[\begin{array}{cc}0&D^2\\
0&0\\
3D^4&D^2
\end{array}\right]=
\left[\begin{array}{cc}0&1\\
0&0\\
3&1
\end{array}\right]\left[\begin{array}{cc}
D^4&0\\
0&D^2
\end{array}\right].
$$
Therefore, the above corollary  should be regarded as a generalization of the classical Forney's theorem stating that a full column rank polynomial
matrix has the PD property if and only if its leading coefficient matrix has full column rank.

\section{Minimal reduced polynomial resolutions, and Forney tables}

A priori is not clear that every convolutional code possesses  reduced polynomial resolutions.
The issue of minimality also is not obvious.
(In dimension 1, reduced polynomial matrices automatically are minimal.)
 In this section, we shall see that for every convolutional code there exists a minimal reduced polynomial resolution and that such a resolution is uniquely determined up to equivalence.

Let $(M,(M_{\leq d}))$ be a filtered module. If $d\geq 0$, then
$$M_{\leq d-1}+D_1M_{\leq d-1}+\cdots +D_nM_{\leq d-1}$$ is the part of $M_{\leq d}$ that comes from $M_{\leq d-1}$ and
  should be regarded as the trivial part of $M_{\leq d}$. It is natural therefore to consider the quotient
$$
 \frac{M_{\leq d}}{M_{\leq d-1}+D_1M_{\leq d-1}+\cdots +D_nM_{\leq d-1}},
$$
which is a linear space over $\mathbb{F}$. Denote it by $\Gamma_d(M,(M_{\leq d}))$.

{\em Example}. There holds
$$ \Gamma_d(S[-k])=
\left\{\begin{array}{cc} \mathbb{F} & \ \tx{when} \ d=k;\\
\{0\} & \ \tx{when} \ d\neq k.
\end{array}\right.
$$

Let $u:(M,(M_{\leq d}))\ra (N,(N_{\leq d}))$ be a homomorphism of filtered modules. We say that $u$ is minimal if
it satisfies the following two conditions:

 1) $u: M_{\leq d} \ra N_{\leq d}$\ is surjective \ $\forall d\geq 0$;

 2) $\Gamma_d(u):\Gamma_d(M,(M_{\leq d}))\ra \Gamma_d(N,(N_{\leq d}))$ \ is bijective \ $\forall d\geq 0$.

\begin{lem} Let $p\geq 1$, and let  $C$ be a (nontrivial) convolutional code in $S^p$.
For any twisting function $a: [1, p]\ra \mathbb{Z}_+$,
 there exists a  polynomial matrix   $G$ such that
$$G:S^q[-b]\ra C[-a],$$
where $q$ is the column number and $b$ the column $a$-degree of $G$,  is minimal.
\end{lem}

{\em Proof}. See Lemma 7 in \cite{L2}.
 $\quad\Box$

Any $G$ satisfying the conditions of the lemma is called a minimal $a$-representation of $C$. In the case when
$a=0$, we simply say "minimal representation".

An exact sequence of filtered modules
$$
(F_l,(F_{l,\leq d}))\stackrel{\delta_l}{\ra} \cdots \stackrel{\delta_2}{\ra}
  (F_1,(F_{1,\leq d}))
\stackrel{\delta_1}{\ra} (F_0,(F_{0,\leq d}))
$$
is said to be minimal if $\delta_1$ is minimal and, for each $i\geq 2$, the homomorphism
$$
\delta_i: (F_i,(F_{i,\leq d}))\ra (Ker\delta_{i-1},(Ker\delta_{i-1}\cap F_{i-1,\leq d}))
$$
also
is minimal.

{\bf Definition.}\
Let $G=(G_1,\ldots, G_l)$ be a reduced polynomial resolution, and let $q\times (p_l,\ldots ,p_1)$ be its size
and $(a_l,\ldots ,a_1)$ the column degree. Say that $G$ is minimal if the sequence (1) of filtered modules
is minimal.

One constructs a  minimal reduced polynomial resolution step by step, using the previous lemma.
Assume  we have a convolutional code $C\subseteq S^q$.
 Choose a minimal representation $G_1$ of $C$. Let $C_1$  be the kernel of $G_1:S^{p_1}\ra C$, where $p_1$ is the column number of $G_1$.
 Letting $a_1$ denote the degree function of $G_1$,  choose next a minimal $a_1$-representation $G_2$ of $C_1$. If we continue this way the process will terminate.

\begin{thm} Every convolutional code  has a minimal reduced polynomial resolution.
\end{thm}

{\em Proof}. This is an immediate consequence of the "graded" Hilbert syzygy theorem. (See Theorem 4.15 in Lang \cite{L} and Theorem 1 in \cite{L2}.) $\quad\Box$

Let
 $G=(G_l,\ldots , G_1)$ and $G^\prime=(G^\prime_l,\ldots , G^\prime_1)$  be two reduced polynomial resolutions. Let $q\times (p_l,\ldots ,p_1)$ and $q\times (p^\prime_l,\ldots ,p^\prime_1)$ be their sizes, and let
  $(a_l, \ldots ,a_1)$ and $(a^\prime_l, \ldots ,a^\prime_1)$ be their
 column degree tables. We say that $G$ and $G^\prime$  are
  equivalent if there exist  isomorphisms
$$ U_i: S^{p_i}[-a_i] \ra S^{p^\prime_i}[-a^\prime_i], \ \ \ \ i=1,\ldots , l$$
such that
$$ G^\prime_1U_1=G_1, \ G^\prime_2U_2=U_1G_2, \ldots ,\ G^\prime_lU_l=U_{l-1}G_l.$$

It is immediate from Lemma 1 that
 equivalent reduced polynomial resolutions have the same size and the same column degree table.

\begin{thm} Any two minimal reduced polynomial resolutions of a convolutional code are  equivalent.
\end{thm}

{\em Proof}. This is an immediate consequence of the theorem about uniqueness of minimal graded free resolutions.
(See Theorem 6.3.13 in Cox,  Little and O'Shea \cite{CLS},  Theorem 1.6  in  Eisenbud \cite{E2}, and  Theorem 1 in \cite{L2}.) $\quad\Box$

The above two theorems permit us to give the following definition.

{\bf Definition.}\
 Let $C\subseteq S^q$ be a convolutional code, and let
 $G=(G_l,\ldots , G_1)$ be any its minimal reduced polynomial resolution. We define the rate
 of $C$ to be $(p_l,\ldots ,p_1)/q$, where  $(p_l,\ldots ,p_1)$ is the size of $G$. Next, we define
  the Forney table of $C$ to be the column degree table of $G$.
The maximum value of the degree function of $G_1$ is called the {\em memory} of the code.

\begin{prop} Let $C$ be a convolutional code, and let $m$ be its memory. Then $C$ can be recovered from the knowledge of \ $C_{\leq m}$.
\end{prop}

{\em Proof}. Let $G_1$ be a minimal representation of $C$, and let $p_1$ its column number, $a_1$ the degree function and $m$ the memory. For $d> m$, we have
$$
\Gamma_d(S^{p_1}[-a_1])=0.
$$
Because $G_1: S^{p_1}[-a_1]\ra C$ is minimal,
we get that $\Gamma_d(C)=0$ for all $d> m$. In other words, for all such $d$, we have
$$
C_{\leq d}=C_{\leq d-1}+D_1C_{\leq d-1}+\cdots +D_nC_{\leq d-1}.
$$
It follows that  knowing $C_{\leq m}$, we can find all $C_{\leq d}$ with $d> m$. This completes the proof since, for any $N$,
$$C=\bigcup_{d\geq N} C_{\leq d}.$$
$\quad\Box$

Closing the section, we want to present
 a simple test for  establishing whether a given reduced polynomial resolution is minimal or not.

\begin{prop} Let   $G=(G_l,\ldots , G_1)$ be a  reduced polynomial resolution. If $l=1$, then $G$ is minimal.
If $l\geq 2$, the $G$ is minimal if and only if none of the nonzero entries of the matrices
$G_2^L, \ldots , G_l^L$ are scalars from $\mathbb{F}$.
\end{prop}

{\em Proof}. The case $l=1$ is obvious. The resolution $G$ is minimal if and only if the sequence of graded free modules (3) is minimal.
(The reader is referred to Eisenbud \cite{E2} for the notion of minimal graded free resolutions.) By
 Corollary 1.5 in \cite{E2},
 (3) is minimal if and only if the scalar matrices
$$
G_k^H(0,0,\ldots,0), \ \ \ \ k=2, \ldots , l
$$
are zero. This completes the proof since
$$
G_k^L(0,\ldots,0)=G_k^H(0,0,\ldots,0).
$$
 $\quad\Box$

\section{Observability}

A desirable property from the point of view of coding is observability.

A convolutional code
$C\subseteq S^q$
is called
observable
if the quotient module $S^q/C$ is torsion free.  As is known, a finitely generated module is torsion free if and
only if it can be embedded into a free module of finite rank. It follows that
 $C$ is observable if and only if it can be described through
$$
C=\{f\in S^q|\ Hf=0\},
$$
where $H\in S^{\bullet\times q}$ is a polynomial matrix, called a parity check matrix or a syndrome former of $C$.

 For an irreducible polynomial $\lambda$ in $S=\mathbb{F}[D]$, let $\mathbb{F}(\lambda)$ denote the integral domain
   $\mathbb{F}[s]/\lambda\mathbb{F}[s]$. If $G$ is a polynomial matrix, define $G/\lambda$ to be its reduction modulo
   the principal ideal $\lambda\mathbb{F}[s]$.

   We   have the following proposition.

\begin{prop} Let $C\subseteq S^q$ be a convolutional code, and let $(G_l,\ldots ,G_1)$ be its
polynomial resolution of size $(p_l,\ldots, p_1)$, say. Then $C$ is observable if and only if the sequence
$$
0\ra \mathbb{F}(\lambda)^{p_l}\stackrel{G_l/\lambda}{\ra}
 \cdots \ra
\mathbb{F}(\lambda)^{p_1}\stackrel{G_1/ \lambda}{\ra} \mathbb{F}(\lambda)^q
$$
is exact for every irreducible polynomial $\lambda$.
\end{prop}

{\em Proof}. See Theorem 1 in  \cite{L1}.
 $\quad\Box$

{\em Remark}. In dimension 1, the statement is well-known in linear systems theory, where it is named as the
Popov-Belevich-Hautus test of controllability.