Hi all,
I get some strange results when solving a MIP in CPLEX, and I was wondering
if somebody in here could give me a couple of hints
Consider an acyclic graph with one source and one sink. Each
(resource-constrained) path from source to sink corresponds to one variable
and associated column in my MIP. To solve the MIP, I have implemented a
branch-and-price procedure. I start off with a restricted version of my
MIP, which contains only a small subset of all variables. In each node of
the branch-and-bound tree, I then iteratively solve the linear relaxation
of the underlying MIP and use the resulting shadow prices to determine
further variables (paths) with negative costs that are then appended to the
MIP at this node. Variables with minimum negative costs are calculated by
determining a shortest path in my graph, where the original arc weights are
modified using the previously obtained shadow prices. In principle, this
seems to work alright.
However, in order to compare results and computing times I then implemented
another program, where I enumerate all paths from source to sink beforehand
and feed the resulting MIP to CPLEX (default parameter settings).
, the optimal solution obtained this way should be equivalent to
the solution obtained by the aforementioned branch-and-price algorithm.
This is true in *most* cases, but for a few problem instances the solution
obtained by branch-and-price is slightly better (i.e., optimal obj.
function value of 40196 instead of 40197 for a min problem), and naturally
both optimal obj. function values are larger than the lower bound obtained
at the root of my branch-and-bound tree. Manual checking of the results
shows that both solutions are feasible. I also checked that the (optimal)
paths that are present in the branch-and-price solution are properly
enumerated in the "brute force" algorithm; this is the case.
Right now I am therefore at a loss trying to explain these differences. Does
this maybe have to do with some numerical difficulties? What would be the
best way to get to the bottom of this? Are there any parameter settings
that are worth looking into? I'd very much appreciate it, if somebody could
give me a hint where to start looking ;-)
I enclosed the corresponding CPLEX output below, but I don't see anything
strange there.
Total of 2957 columns generated
Tried aggregator 1 time.
MIP Presolve eliminated 2 rows and 2482 columns.
Reduced MIP has 13 rows, 491 columns, and 2032 nonzeros.
Presolve time = 0.01 sec.
Clique table members: 13.
MIP emphasis: balance optimality and feasibility.
Root relaxation solution time = 0.01 sec.
Nodes Cuts/
Node Left IInf Best Integer Best Node ItCnt
Gap Variable B Parent Depth
0 0 40195.0000 6 40195.0000 63
* 0+ 0 0 130112.0000 40195.0000 63
69.11%
* 0+ 0 0 40197.0000 40195.0000 63
0.00%
Cheers,
Chris

CPLEX's solution is optimal to within a mipgap of
|40195-40197|/(1+40195) = .00004976. Since this is less than CPLEX's
default mipgap tolerance of .0001, CPLEX declares it optimal. Try
setting mipgap to, say, .00001 instead.

Bob Fourer
4er@iems.northwestern.edu

Christoph Stark wrote:
Hi all,

I get some strange results when solving a MIP in CPLEX, and I was wondering
if somebody in here could give me a couple of hints

Consider an acyclic graph with one source and one sink. Each
(resource-constrained) path from source to sink corresponds to one variable
and associated column in my MIP. To solve the MIP, I have implemented a
branch-and-price procedure. I start off with a restricted version of my
MIP, which contains only a small subset of all variables. In each node of
the branch-and-bound tree, I then iteratively solve the linear relaxation
of the underlying MIP and use the resulting shadow prices to determine
further variables (paths) with negative costs that are then appended to the
MIP at this node. Variables with minimum negative costs are calculated by
determining a shortest path in my graph, where the original arc weights are
modified using the previously obtained shadow prices. In principle, this
seems to work alright.

However, in order to compare results and computing times I then implemented
another program, where I enumerate all paths from source to sink beforehand
and feed the resulting MIP to CPLEX (default parameter settings).
, the optimal solution obtained this way should be equivalent to
the solution obtained by the aforementioned branch-and-price algorithm.
This is true in *most* cases, but for a few problem instances the solution
obtained by branch-and-price is slightly better (i.e., optimal obj.
function value of 40196 instead of 40197 for a min problem), and naturally
both optimal obj. function values are larger than the lower bound obtained
at the root of my branch-and-bound tree. Manual checking of the results
shows that both solutions are feasible. I also checked that the (optimal)
paths that are present in the branch-and-price solution are properly
enumerated in the "brute force" algorithm; this is the case.

Right now I am therefore at a loss trying to explain these differences. Does
this maybe have to do with some numerical difficulties? What would be the
best way to get to the bottom of this? Are there any parameter settings
that are worth looking into? I'd very much appreciate it, if somebody could
give me a hint where to start looking ;-)

I enclosed the corresponding CPLEX output below, but I don't see anything
strange there.

Total of 2957 columns generated

Tried aggregator 1 time.
MIP Presolve eliminated 2 rows and 2482 columns.
Reduced MIP has 13 rows, 491 columns, and 2032 nonzeros.
Presolve time = 0.01 sec.
Clique table members: 13.
MIP emphasis: balance optimality and feasibility.
Root relaxation solution time = 0.01 sec.

Nodes Cuts/
Node Left IInf Best Integer Best Node ItCnt
Gap Variable B Parent Depth

0 0 40195.0000 6 40195.0000 63
* 0+ 0 0 130112.0000 40195.0000 63
69.11%
* 0+ 0 0 40197.0000 40195.0000 63
0.00%

Cheers,
Chris

Hi Bob,

Bob Fourer wrote:

CPLEX's solution is optimal to within a mipgap of
|40195-40197|/(1+40195) = .00004976. Since this is less than CPLEX's
default mipgap tolerance of .0001, CPLEX declares it optimal. Try
setting mipgap to, say, .00001 instead.

Excellent. Works like a charm.
Since I use Concert, adding cplex.setParam(IloCplex::EpGap, 0.00000001); did
the trick in all instances concerned.

Why didn't I think of that ;-)

Thanks a lot
Chris