[Scip] Is their any tips for solve large MIP instance with scip?

[杨旭]

Dear all,
Currently I am working on a large MIP instance with scip. I have used scip
interface to construct the problem model and
I found  it seems impossible to get a optimal solution for my instance. The
solving process has run for several days and
has consumed memory up to nearly 30G, it always stuck at a certain gap(such
as 20%). I am a newbie of solving LP or
MIP， thus I am not sure whether a  reformulating of my problem could help
or not， and don't known how to.

Generally speaking, my problem is content caching problem in network, a
kind of Capacitated Facility Location Problem,
below is a modeling of my problem in mathprog.
####################################################
# node set
set NODE;
# content set
set CONTENT;

# null mode u[v,nil]=0;
param nil := -1, integer;

# table-nc
# content request<q>
param q{NODE,CONTENT};

# table-c
# resident node of content<l>
param l{CONTENT};
# content size
param m{CONTENT};

# table-n
# node capacity
param b{NODE}, default 0;

# table-nn
# shortest path length
param u{NODE,NODE}, default 0;


param AMP := max{v in NODE, c in CONTENT}u[v,l[c]];
# table-nnk
# kth node on shortest path
param g{s in NODE,t in NODE,k in 0..u[s,t]};

#
var x{NODE,CONTENT}, >=0, <=1;
#

param k{v in NODE, c in CONTENT} := u[v,l[c]];
param gi{v in NODE, c in CONTENT, i in 0..u[v,l[c]]} :=  g[v,l[c],i];

# indicator: gain min hops if cache content c in ith node on shortest path
var y{v in NODE, c in CONTENT, i in 0..u[v,l[c]]}, binary;

#
var z{NODE,CONTENT}, >=0;


# read data from tables
table n IN "CSV" "table-n.csv":
     NODE <- [Node], b ~ Capacity;
table c IN "CSV" "table-c.csv":
     CONTENT <- [Content], l ~ Resident, m ~ Size;
table nn IN "CSV" "table-nn.csv":
     [SNode,TNode], u ~ Distance;
table nc IN "CSV" "table-nc.csv":
     [Node,Content], q ~ Request;
table nnk IN "CSV" "table-nnk.csv":
     [SNode,TNode,Index], g ~ KthNode;

# cons
# node capacity
s.t. cacheFloor{v in NODE}: sum{c in CONTENT}x[v,c] * m[c] <= b[v];

set SV := NODE;
# can gain only one min hops if cache on shortest path
s.t. ytotal{v in SV, c in CONTENT}: sum{i in 0..u[v,l[c]]}y[v,c,i] = 1;
s.t. cached{v in SV, c in CONTENT, i in 0..u[v,l[c]]-1}: x[gi[v,c,i],c] >=
y[v,c,i];

s.t. larger2{v in SV, c in CONTENT}: z[v,c] >= k[v,c] - AMP * (1 -
y[v,c,k[v,c]]);
s.t. larger1{v in SV, c in CONTENT, i in 0..u[v,l[c]]-1}: z[v,c] >=
x[gi[v,c,i],c] * i - AMP * (1 - y[v,c,i]);

minimize cost: sum{v in SV, c in CONTENT}q[v,c] * m[c] * z[v,c];

data;

end;
##############################################

Attached tar file contains the mathprog model file and input data

Detail description of the problem can be found in the attached pdf file.

Current I only used the default setting.Any suggestion on tuning the scip
params or reformulating?

Thank you for all you help!
Best Wishes!
---------------------------------------
YangXu
Tsinghua University, Beijing
TEL: +86-15110264737
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20120514/00ad6e7d/attachment.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cache.tar.gz
Type: application/x-gzip
Size: 184121 bytes
Desc: not available
Url : http://listserv.zib.de/mailman/private/scip/attachments/20120514/00ad6e7d/cache.tar.bin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Could in-network caching benefit information-centric	networking.pdf
Type: application/pdf
Size: 419751 bytes
Desc: not available
Url : http://listserv.zib.de/mailman/private/scip/attachments/20120514/00ad6e7d/Couldin-networkcachingbenefitinformation-centricnetworking.pdf