
\documentclass[a4paper, 12pt]{article} 


\title{Biq Mac Library part 2 - large instances}
\author{Angelika Wiegele\thanks{Alpen-Adria-Universit{\"a}t
    Klagenfurt, Institut f{\"u}r Mathematik, Universit{\"a}tsstr.\
    65-67, 9020 Klagenfurt, Austria, angelika.wiegele@uni-klu.ac.at}} 
\date{July 2009}

\usepackage[english]{babel} 
\usepackage{amssymb}
\usepackage{url}
\pagestyle{plain}

\addtolength{\hoffset}{-1.5cm}
\addtolength{\textwidth}{3cm}
\addtolength{\voffset}{-1.5cm}
\addtolength{\textheight}{3cm}

\begin{document} 

\maketitle 

\section{Quadratic 0-1 Programming problems}
The problem to be solved is the following:
\[
 \min \{ y^T Q y: ~y \in \{ 0,1 \}^n \},
\]
where $Q$ is a symmetric matrix of order $n$.

\subsection{Beasley instances}  \label{sec:beasley}

\begin{table}[h]
\begin{center}
\begin{tabular}{|l|r|r|r |r|}
\hline
Problem& &&& \\
name &\multicolumn{1}{|c|}{solution}&\multicolumn{1}{|c|}{lower bound}& time &terminationcode\\
\hline
\multicolumn{5}{|l|}{$n=500, d=0.1$}\\
\hline
bqp1000-1.sparse  & $\le$ -313554 & -1099060.40 & 3h &not terminated\\
bqp1000-2.sparse  & $\le$ -321843 &  -1081420.70 & 3h & not terminated\\
bqp1000-3.sparse  & $\le$  -321843 &-1081420.70 &3h &not terminated\\
bqp1000-4.sparse  & $\le$ -319161 & -1090515.70 & 3h &not terminated\\
bqp1000-5.sparse  & $\le$ -312107 &  -1013944.50 & 3h & not terminated\\
bqp1000-6.sparse  & $\le$ -337905 &-1130286.10& 3h &not terminated\\
bqp1000-7.sparse  & $\le$ -324935 & -1132657.90 & 3h &not terminated\\
bqp1000-8.sparse  & $\le$  -315873& -1050845.20 & 3h & not terminated\\
bqp1000-9.sparse  & $\le$  -323896&  -1062541.00 & 3h & not terminated\\
bqp1000-10.sparse & $\le$ -326342 & -1070584.90 & 3h &not terminated\\
bqp2500-1.sparse  & $\le$ -938260 & -1216648.70 & 3h &not terminated\\
bqp2500-2.sparse  & $\le$  -1196679&  -2409858.00 &3h	& not terminated\\
bqp2500-3.sparse  & $\le$ -1293141 &  -24252509.00 & 3h & not terminated\\
bqp2500-4.sparse  & $\le$  -1242889 & -24924060 & 3h &not terminated\\
bqp2500-5.sparse  & $\le$  -1216870 &  -24259735 & 3h & not terminated\\
bqp2500-6.sparse  & $\le$  -1230187 & -24453278 & 3h &not terminated\\
bqp2500-7.sparse  & $\le$ -1242411& -24548542 & 3h &not terminated\\
bqp2500-8.sparse  & $\le$  -1262588 & -24389751 & 3h & not terminated\\
bqp2500-9.sparse  & $\le$ -1241359 &  -25003483  & 3h & not terminated\\
bqp2500-10.sparse & $\le$  -1242782 & -24875407 & 3h &not terminated\\
\hline
\end{tabular}
\caption{Beasley data. For details see Section~\ref{sec:beasley} on
  page~\pageref{sec:beasley}.} \label{tab:beasley} 
\end{center} 
\end{table}

\begin{table}[h]
\begin{center}
\begin{tabular}{|l|r|r|}
\hline
Problem& & \\
name &\multicolumn{1}{|c|}{solution}&\multicolumn{1}{|c|}{lower bound}\\
\hline
\multicolumn{3}{|l|}{$n=500, d=0.1$}\\
\hline
bqp500-1  & $\le$ -116586 & -121588.41 \\
bqp500-2  & $\le$ -128223 & -132216.45 \\
bqp500-3  & $\le$ -130812 & -134214.12 \\
bqp500-4  & $\le$ -130097 & -134781.02 \\
bqp500-5  & $\le$ -125487 & -129572.87 \\
bqp500-6  & $\le$ -121772 & -126429.50 \\
bqp500-7  & $\le$ -122201 & -127136.37 \\
bqp500-8  & $\le$ -123559 & -128574.61 \\
bqp500-9  & $\le$ -120798 & -125821.63 \\
bqp500-10 & $\le$ -130619 & -134352.34 \\
\hline
\end{tabular}
\caption{Beasley data. For details see Section~\ref{sec:beasley} on
  page~\pageref{sec:beasley}.} \label{tab:beasley} 
\end{center} 
\end{table}


\section{Max-Cut instances}
The problem to be solved is
\[
\max \{ x^T L x: ~x \in \{ -1,1 \}^n \},
\]
where $L$ is the Laplace matrix of the given graph of $n$ vertices. 

\subsection{Max-Cut instances generated with rudy} \label{sec:mc}
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|r|r|r |r|}
\hline
Problem& &&& \\
name &\multicolumn{1}{|c|}{best found cut value}&\multicolumn{1}{|c|}{upper bound}& time &terminationcode\\
\hline
\multicolumn{5}{|l|}{$n=500, d=0.1$}\\
\hline
G1  & $\ge$  11602 & 12083.26 & 271 sec  & terminated\\
G2  & $\ge$  11599 & 12089.51  &272 sec& terminated\\
G3  & $\ge$  11580 & 12084.40& 240 sec & terminated\\
G4 & $\ge$ 11617 & 12111.53 & 245 sec & terminated\\
G5 & $\ge$ 11604 & 12099.95 & 234 sec &terminated\\
G6  & $\ge$ 1971 &2489.74& 270 sec & terminated\\
G7  & $\ge$ 1971 & 2489.28 & 269 sec &terminated\\
G8  & $\ge$ 1986 & 2506.95& 245 sec & terminated\\
G9  & $\ge$ 2036 &  2528.75 & 351 sec& terminated\\
G10 & $\ge$ 1966 & 2585.08 & 256 sec & terminated\\
G11  & $\ge$ 558 & 629.17 & 140 sec & terminated\\
G12  & $\ge$ 548 & 623.88 & 91 sec & terminated\\
G13 & $\ge$ 578 & 647.14 & 80 sec& terminated\\
G14  & $\ge$ 3044  & 3191.59 & 187 sec& terminated\\
G15 & $\ge$ 3033  &  3171.58 & 160 sec & terminated\\
G16& $\ge$  3044 & 3175.04 & 191 sec & terminated\\
G17  & $\ge$ 3033 & 3171.35& 180 sec & terminated\\
G18 & $\ge$  986 & 1166.02 & 167 sec & terminated\\
G19 & $\ge$ 891 & 1082.02   & 160 sec  & terminated\\
G20 & $\ge$  941 & 1111.40 & 146 sec& terminated\\
G21  & $\ge$ 914 & 1104.29 & 162 sec & terminated\\
G22  & $\ge$ 13282 & 14136.03 & 3017 sec& terminated\\
G23  & $\ge$  13300 & 14145.60& 2743 sec& terminated\\
G24 & $\ge$ 13274 & 14140.89& 2902 sec& terminated\\
G25 & $\ge$ 13281 & 14144.29 &2914 sec& terminated\\
G26  & $\ge$ 13289 &14133.01 & 3521 sec & terminated\\
G27  & $\ge$ 3271 & 4141.69 & 3149 sec& terminated\\
G28  & $\ge$ 3247 & 4100.83 & 4112 sec & terminated\\
G29  & $\ge$ 3328 &  4208.92 & 2285 sec& terminated\\
G30 & $\ge$ 3329 & 4215.42 & 2514 sec & terminated\\
G31  & $\ge$ 3271 & 4116.70 & 4212 sec & terminated\\
G32  & $\ge$ 1390 & 1567.65 & 1221 sec&terminated\\
G33 & $\ge$ 1352 & 1544.32 & 1116 sec&terminated\\
\hline
\end{tabular}
\end{center}
\end{table}

\begin{table}[h]
\begin{center}
\begin{tabular}{|l|r|r|r |r|}
\hline
Problem& &&& \\
name &\multicolumn{1}{|c|}{best found cut value}&\multicolumn{1}{|c|}{upper bound}& time &terminationcode\\
\hline
\multicolumn{5}{|l|}{$n=500, d=0.1$}\\
\hline
G34  & $\ge$  13666 & 1546.70 & 964 sec&\\
G35 & $\ge$  7633 &  8014.79 & 3116 sec& \\
G36& $\ge$  7635 & 8006.03& 4181 sec &terminated\\
G37  & $\ge$ 7643 &8018.68  &  3695 sec&terminated\\
G38 & $\ge$   7629 & 8015.04& 3394 sec & terminated\\
G39 & $\ge$ 2382 &  2877.67  & 2474 sec & terminated\\
G40 & $\ge$  2334 & 2839.14 & 2700 sec & terminated \\
G41  & $\ge$  2390 & 2865.24 & 3293 sec &terminated\\
G42  & $\ge$  2449&  2946.27& 2985 sec& terminated\\
G43  & $\ge$  6648 & 7232.27& 248 sec& terminated\\
G44 & $\ge$ 6631 & 7027.93 & 274 sec& terminated\\
G45 & $\ge$ 6630 & 7024.83 & 300 sec& terminated\\
G46  & $\ge$ 6633 & 7029.99 & 301 sec & terminated\\
G47  & $\ge$ 6634 & 7036.71 & 305 sec & terminated\\
G48  & $\ge$ 6000 & 6000.01 & 2 sec & terminated\\
G49  & $\ge$ 6000 &  6000.01 & 2 sec & terminated\\
G50 & $\ge$ 5880 & 5988.18 & 34 sec& terminated \\
G51  & $\ge$ 3824 & 4006.28 & 333 sec & terminated\\
G52  & $\ge$ 3829 & 4009.67 & 361 sec& terminated\\
G53 & $\ge$ 3837 & 4009.74 & 356 sec& terminated\\
G54  & $\ge$ 3825  & 4006.23 & 363 sec& terminated\\
G55 & $\ge$  11837 &  12875.70 & 3 h & not terminated\\
G56& $\ge$  3873 & 4792.95& 3h &not terminated\\
G57  & $\ge$ 3366 &3884.46 & 3h  &not terminated\\
G58 & $\ge$ 18782  & 25280.75 & 3h &not terminated \\
G59 & $\ge$  5542 &  12720.24  & 3h& not terminated\\
G60 & $\ge$  13958 & 15565.51 & 3h &not terminated\\
G61  & $\ge$ 5550 & 7099.96 & 3 h & not terminated\\
G62  & $\ge$ 4788 & 5615.07 & 3h &not terminated\\
G63  & $\ge$  26079 & 46673.80& 3h &not terminated\\
G64 & $\ge$ 7516 & 29266.20 & 3 h & not terminated\\
G65 & $\ge$ 5268 & 6277.86 & 3h& not terminated\\
G66  & $\ge$ 5886 & 7108.61 & 3h & not terminated\\
G67  & $\ge$ 6562 & 8078.72 & 3h & not terminated\\
\hline
\end{tabular}
\caption{Beasley data. For details see Section~\ref{sec:beasley} on
  page~\pageref{sec:beasley}.} \label{tab:beasley} 
\end{center} 
\end{table}

\end{document}
