<html>
<head>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 11 (filtered)">
<style>
<!--
/* Font Definitions */
@font-face
{font-family:新細明體;
panose-1:2 2 3 0 0 0 0 0 0 0;}
@font-face
{font-family:"\@新細明體";
panose-1:2 2 3 0 0 0 0 0 0 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman";}
a:link, span.MsoHyperlink
{color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{color:purple;
text-decoration:underline;}
span.EmailStyle17
{font-family:Arial;
color:windowtext;}
/* Page Definitions */
@page Section1
{size:595.3pt 841.9pt;
margin:72.0pt 89.85pt 72.0pt 89.85pt;
layout-grid:18.0pt;}
div.Section1
{page:Section1;}
-->
</style>
</head>
<body lang=ZH-TW link=blue vlink=purple style='text-justify-trim:punctuation'>
<div class=Section1 style='layout-grid:18.0pt'>
<p class=MsoNormal><font size=3 face="Times New Roman"><span lang=EN-US
style='font-size:12.0pt'>Hi all,<br>
<br>
I am working on a 0-1 Integer programming problem, which in the form of Ax =<br>
b. The problems I am dealing with has a special structure in the matrix A.<br>
It definitely not a totally unimodular (TU) matrix, since we cannot find a<br>
integer solution by Simplex. But when I do branch-and-bound (branching on<br>
fractional value), after few iterations, an integer solution can be found by<br>
Simplex method. I suspected that the matrix A is not TU, but it is very<br>
close to TU. So, I have two questions,<br>
<br>
1. Given any {0,1}-matrix A, can we measure how close of A to be a TU<br>
matrix?<br>
2. Any fast implementation to check the total unimodularity?<br>
<br>
Thank you.<br>
<br>
Cheers,<br>
Spencer</span></font></p>
</div>
</body>
</html>