# Labeled linear program with labeled equations and wide objective function

Can anybody help me stating a linear program in latex with the following requirements?

1. The LP itself shall be numbered on the left-hand side (although in the remaining document the equations' labels are on the rhs), with a certain tag, e.g. "(P)" which should be associated with an equation label.

2. The LP part consists of 5 columns:

• for "max" and for "subject to"
• for the lhs of the constraints
• for the relations $\leq$, etc.
• for the rhs of the constraints
• for quantification (e.g. $\forall v \in V$)
3. The objective function (which does not have a lhs/rhs) may be wide and should span over the three middle columns.

4. Every row should itself have an equation label which is right-justified.

So far I used an equation environment together with the array environment and the multicolumn command to get the layout right. But the constraint labels don't work here. On the other hand, using align doesn't seem to help since even the wide objective didn't work very nicely (I used \mathclap).

The following picture shows how it should look like

this http://www.math.uni-magdeburg.de/~walter/downloads/latex-lp-labels.png

Here is a MWE rendering the centered part - but I have no clue how to add the single equation labels nor the left-aligned equation label given that other equations are right-aligned.

\documentclass{article}
\usepackage{amsmath}
\begin{document}
\begin{equation*}
\begin{array}{lrcll}
\max
& \multicolumn{4}{l}{\sum\limits_{v \in V} x_v + \sum\limits_{e \in E} y_e + 10000\gamma } \\
\text{s.t.}
& x_v + x_w & \geq & 0 & \forall \{v,w\} \in E \\
& y_e & \geq & 0 & \forall e \in E \\
& y(\delta(U)) & \geq & \frac{1}{2}(|U|-1) & \forall U \subseteq V
\end{array}
\end{equation*}
\end{document}

• Welcome to TeX.SE. It would be helpful if you composed a fully compilable MWE including \documentclass and the appropriate packages that sets up the problem. While solving problems is fun, setting them up is not. Then those trying to help can simply cut and paste your MWE and get started on solving problem. – Peter Grill Nov 23 '12 at 10:33
• Should they be numbered always (1), (2), (3), or they should use the continuing numbering of equations in the whole document? – yo' Nov 23 '12 at 13:19
• The usual need is that the constraints are numbered as regular equations and the whole LP gets a special name. – Xammy Nov 26 '12 at 7:00

## 3 Answers

I've taken some liberties in interpreting what you're trying to accomplish here. For example, I assume that you will manually create the tag names for the LP blocks. Also, I think my solution lacks a certain elegance: in particular, each such block has to be created separately. I don't really like that.

Here's the general idea: create two adjacent boxes centered on the baseline with one containing a dummy equation to create the label for the entire block. Spacing after the boxes is a bit wonky. So, I add ~ after the last flalign environment. (Short coming: you also have to manually adjust the width of the first parbox to get the label to be positioned correctly.)

You seemed to want the first line to somehow align with the LP. I've got two solutions to that. The first puts the first line into a box of zero width. (Short coming: you have to re-enter math mode within this box.) The second puts this first line in its own flalign environment. (Short coming: you have to adjust the vertical spacing between the two environments.)

\documentclass{article}
\usepackage{amsmath,calc}
\newlength{\LPlhbox}
\begin{document}

\settowidth{\LPlhbox}{(P.1)}%
\noindent%
\parbox{\LPlhbox}{\begin{align}
\tag{P.1}\label{My first LP Block}
\end{align}}%
\hspace*{\fill}%
\begin{minipage}{\linewidth-2cm}
\begin{flalign}\notag
& \makebox[0pt][l]{$\displaystyle{}\max \sum\limits_{v \in V} x_v + \sum\limits_{e \in E} y_e + 10000\gamma$} \\
\label{this line can be referenced}
& \text{s.t.} & x_v + x_w   & \geq  0                 && \forall \{v,w\} \in E && \\
&             & y_3         & \geq 0                  && \forall e\in E        && \\
&             & (\delta(U)) & \geq \frac{1}{2}(|U|-1) && \forall U \subseteq V
\end{flalign}~
\end{minipage}

\settowidth{\LPlhbox}{(P.2)}%
\noindent%
\parbox{\LPlhbox}{\begin{align}
\tag{P.2}\label{My second LP Block}
\end{align}}%
\hspace*{\fill}%
\begin{minipage}{\linewidth-2cm}
\begin{flalign}\notag
\max \sum\limits_{v \in V} x_v + \sum\limits_{e \in E} y_e + 10000\gamma &&
\end{flalign}
\vspace{-1.5\baselineskip}
\begin{flalign}
& \text{s.t.} & x_v + x_w   & \geq  0                 && \forall \{v,w\} \in E && \\
&             & y_3         & \geq 0                  && \forall e\in E        && \\
&             & (\delta(U)) & \geq \frac{1}{2}(|U|-1) && \forall U \subseteq V
\end{flalign}~
\end{minipage}

Notice that we can reference line~\ref{this line can be referenced}
and both block~\ref{My first LP Block} and block~\ref{My second LP Block}
\end{document}


What would be nice is if there were a commands \lefttag and \righttag to temporarily override document defaults.

You can also easily create a command to do the work of the left-hand box.

\newcommand{\LPblocktag}{\settowidth{\LPlhbox}{(#1)}%
\parbox{\LPlhbox}{\begin{align}\tag{#1}#2\end{align}}%
\hspace*{\fill}}


I've written the second argument as I have because I don't want to assume you'll be referencing every such block.

So the first block above can be written as

\noindent%
\LPblocktag{P.3}{\label{My third LP Block}}%
\begin{minipage}{\linewidth-2cm}
\begin{flalign}\notag
& \makebox[0pt][l]{$\displaystyle{}\max \sum\limits_{v \in V} x_v + \sum\limits_{e \in E} y_e + 10000\gamma$} \\
\label{this line can be referenced}
& \text{s.t.} & x_v + x_w   & \geq  0                 && \forall \{v,w\} \in E && \\
&             & y_3         & \geq 0                  && \forall e\in E        && \\
&             & (\delta(U)) & \geq \frac{1}{2}(|U|-1) && \forall U \subseteq V
\end{flalign}~
\end{minipage}

I can reference \ref{My third LP Block} • I don't like the way my image came out. Can anyone recommend how I could trim it to show just what is necessary to see? – A.Ellett Nov 23 '12 at 20:16
• Yes, you should say \pagestyle{empty} in the preamble, and then you can use pdfcrop file.pdf to get the "tight" pdf file. – yo' Nov 23 '12 at 21:01
• Thank you! Still looks a bit small to me. But at least it's not all that white space it was before – A.Ellett Nov 23 '12 at 21:05
• Regarding the zero width math box of your first solution, and its short coming: the mathtools package has a \mathrlap macro for that, and much more. – mafp Nov 23 '12 at 22:14

I've modified the above to create a new environment that will wrap around a math equation environment. I'm keeping the old solution above because here I use xkeyval package to allow the user to pass arguments to the new environment, but also because the flavor of this solution's approach is rather different. I think this approach is a bit more versatile and suggests other modifications that could be useful.

Also, I've incorporated cmhughes suggested use of mathtools. Finally, as written, this environment seems to require explicit naming of the tag for the left-hand box. It seems that there should be some kind of default approach there. But, I'll leave that also for someone else to dream up.

Here's my re-imagined solution:

\documentclass{article}
\usepackage{amsmath,mathtools,calc}
%..%
\usepackage{xkeyval}
\makeatletter
\newlength{\LP@lh@boxwidth}      %% width of first box, set automatically within environment
\setlength{\LP@lh@boxwidth}{0pt}
\newlength{\LP@lh@boxsep}        %% distance between two boxes.  Default is 2em.  Can be overridden by using key boxsep=<length>
\setlength{\LP@lh@boxsep}{2em}
\newcommand{\LP@lh@content}{}
\newcommand{\LP@lh@tagname}{}    %% set by user using key tagname=<name of tag>
\define@key[LP]{lhbox}{boxsep}[2em]{\setlength{\LP@lh@boxsep}{#1}}
\define@key[LP]{lhbox}{content}[]{\renewcommand{\LP@lh@content}{#1}}
\define@key[LP]{lhbox}{tagname}[]{\renewcommand{\LP@lh@tagname}{#1}}
\newenvironment{tagblock}[]%
{\setkeys[LP]{lhbox}{tagname,boxsep,#1}\relax%
\settowidth{\LP@lh@boxwidth}{\tagform@\LP@lh@tagname}%
\noindent%
\parbox{\LP@lh@boxwidth}{\begin{align}\tag{\LP@lh@tagname}\LP@lh@content\end{align}}%
\hspace*{\LP@lh@boxsep}%
\begin{minipage}{\linewidth-\LP@lh@boxwidth-\LP@lh@boxsep}}%
{~\end{minipage}}
\makeatother
%..%
\begin{document}

\begin{tagblock}[tagname={P.1},content={\label{My first LP Block}}]
\begin{flalign}\notag
& \mathrlap{\max \sum\limits_{v \in V} x_v + \sum\limits_{e \in E} y_e + 10000\gamma} \\
\label{eq01:first_line}
& \text{s.t.} & x_v + x_w   & \geq  0                 && \forall \{v,w\} \in E && \\
&             & y_3         & \geq 0                  && \forall e\in E        && \\
&             & (\delta(U)) & \geq \frac{1}{2}(|U|-1) && \forall U \subseteq V
\end{flalign}
\end{tagblock}

\begin{tagblock}[tagname={P.2},content=\label{My second LP Block}]
\begin{flalign}\notag
& \mathrlap{\max \sum\limits_{v \in V} x_v + \sum\limits_{e \in E} y_e + 10000\gamma} \\
& \text{s.t.} & x_v + x_w   & \geq  0                 && \forall \{v,w\} \in E && \\
\label{eq02:second_line}
&             & y_3         & \geq 0                  && \forall e\in E        && \\
&             & (\delta(U)) & \geq \frac{1}{2}(|U|-1) && \forall U \subseteq V
\end{flalign}
\end{tagblock}

Notice that we can reference line~\ref{eq01:first_line} and line~\ref{eq02:second_line}
and both block~\ref{My first LP Block} and block~\ref{My second LP Block}

\end{document} • Indeed, wrapping everything in specific environments is quite helpful - I still flagged the other reply as the answer since it provides more insight / explanations. Thanks again. – Xammy Nov 26 '12 at 7:20

I think the other answer gives you the output you want.

My answer does 3 out of 4 of your requests, but labelling the extra (P) on the left is tricky; my code just demonstrates how you can use alignat to give you most of what you want. \documentclass{article}
\usepackage{amsmath}
\begin{document}

\subsection*{Original}
\begin{equation*}
\begin{array}{lrcll}
\max
& \multicolumn{4}{l}{\sum\limits_{v \in V} x_v + \sum\limits_{e \in E} y_e + 10000\gamma } \\
\text{s.t.}
& x_v + x_w & \geq & 0 & \forall \{v,w\} \in E \\
& y_e & \geq & 0 & \forall e \in E \\
& y(\delta(U)) & \geq & \frac{1}{2}(|U|-1) & \forall U \subseteq V
\end{array}
\end{equation*}

\subsection*{New}
\begin{alignat}{3}
\max              &   & \sum_{v \in V} x_v  + & \sum_{e \in E}  y_e + 10000\gamma  &   & \nonumber             \\
\text{s.t.}\qquad &   & x_v + x_w             & \geq            0                  &   & \forall \{v,w\} \in E \\
&   & y_e                   & \geq            0                  &   & \forall e \in E       \\
&   & y(\delta(U))          & \geq            \frac{1}{2}(|U|-1) &   & \forall U \subseteq V
\end{alignat}
\end{document}

• Thanks for the contribution - I used to split the objective into the column parts as well but sometimes there are longer expressions which cannot be split nicely. – Xammy Nov 26 '12 at 7:17