[Coin-discuss] markshare1_1, meaning of solution

[JBS at watson.ibm.com]

         H. Mittelmann has been benchmarking MILP free codes (see
<a href="http://plato.asu.edu/ftp/milpf.html"> this page </a>).  I have
been looking at how CBC performs.  One of the problems CBC is unable to
do (within the 2 hour limit) is markshare1_1.  This is a modification
of markshare1, one of the MIPLIB 3.0 problems.  The modification
(changing 5 0-1 variables to continuous variables with bounds 0,1) was
apparently intended to make the problem easier.  However it appears the
problem is easier for MILP solvers only because they are not actually
finding the solution.  The original markshare1 minimization problem has
solution 1 (0 is a trivial lower bound).  The modified problem has
numerous feasible points for which the value of the objective function
is near zero but none for which it is exactly zero.  Hence it appears
that actually solving the problem by finding the best of these points
would be at least as hard as the original markshare1 problem.  However
the MILP solvers which "solve" the problem appear instead to be finding
one of the near-zero points and reporting it to be a zero point perhaps
because they don't require the 0-1 variables to be exactly 0 or 1.  For
example the log of the SCIP solution shows a value for x42 (a pure 0-1
variable) of 6.46e-7.  If this variable is required to be strictly
zero, the objective function would have value 2.23e-5 not 0.  This is
considerably greater than what I believe to be the actual solution,
5.8e-9.  The density of feasible points seems to be proportional to the
distance of the objective function from 0.  So it is orders of magnitude
easier to find a objective function below say 10e-4 (which appears to
be about the point which the MILP solvers think is the same as 0) than
the true solution.  So I question whether this benchmark is measuring
anything useful as solvers benefit by being sloppy about the meaning of
integer.
        Some additional details follow.  The markshare1 problem is an
integer knapsack problem.  50 dimension 6 integer vectors are given.
You want to find a subset with sum as close as possible to a 6-d
integer target (which is near the sum of all 50 vectors divided by 2)
without going over in any coordinate position.  The objective function
is the sum of the deficits in each coordinate position.  Clearly 0 is
a trivial lower bound.  However markshare1 has best solution 1.  This
problem is hard for MILP solvers as the LP relaxations often achieve 0
and provide little information.  Mittelmann changed the problem by
allowing the multipliers of the following vectors
        25        97        95         1         3        69
        99        13        87        66        20         3
        21        91        22        26        69         5
        75        70        97         1        13        77
        43        28        92        12        73        16
to range between 0 and 1 in the sum (instead of being strictly 0 or 1,
in or out). Obviously in the original problem there are 32 possibilities
for the contribution of these vectors to the sum.  With continuous
variables there are an infinite number of possibilities.  However to
achieve the lower bound of 0 these vectors must contribute integer
values to the sum (as the remaining terms are all integer).  There are
only 12 additional ways these vectors (with continuous multipliers
between 0 and 1) can contribute integer values to the sum.  The 12
possibilities arise from the fact that vectors 1,2,3 and 5 are linearly
dependent mod 7.  However none of the 12 possibilities leads to an
exact solution.
         While there are only 12 integer lattice points within the
polytope generated by these 5 points there are numerous integer lattice
points near the polytope.  When one of these points can be extended to
an exact solution of the knapsack problem this corresponds to an
objective function value near zero (how near being determined by how
close the lattice point was to the polytope).
         The 5 vectors above all have inner product zero with
 172428529 159440302  89397099 -350248871 -130370507 -398953428
so the subspace they generate consists of those vectors perpendicular
to the above vector.  The SCIP "solution" has multipliers for the 5
vectors above of
 .0166347809 .579881488 .658231211 .308702902 .190703142
leading to a contribution to the sum of
 102.999945 95.999964 113.999951 57.999965 79.999955 32.999974
The differences from exact integers are removed in the sum by allowing
one of the other vectors to have multiplier 6.46e-7 instead of 0
exactly.  However if the other 0,1 variables are required to be 0 or 1
exactly this point cannot be made to contribute
       103        96       114        58        80        33
exactly to the sum as is required for a 0 value of the objective
function.  This is because this point is not in the subspace generated
by the 5 vectors.  In fact its inner product with the vector above is
-8902 so it is close to the subspace but not in it.  The best you can
do is use multipliers
 .01663461 .57988184 .65823159 .30870303 .19070329
leading to a point
       103        96       114        58        80        32.99997768
corresponding to an objective function value of 2.23e-5.
         This is good but far from the best.  The point
       196       155       264        74       125       100
also leads to an exact solution and is much closer to the polytope as it
has inner product with the vector above of 1.  The best feasible point
near this point has objective value 5.8e-9 which I believe is in fact
the solution.
                             James B. Shearer