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

[Thorsten Koch]

Dear 杨旭,

is there the possibility that you provide us with an .lp file
of your problem?

This would make it easier for us to give you an answer to your
question.

best regards,
Thorsten



Am 14.05.2012 15:00, schrieb 杨旭:
> 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
> 
> 
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-- 
The important thing is not to stop questioning.
Curiosity has its own reason for existing.          -- Albert Einstein
______________________________________________________________________
Dr. Thorsten Koch / Konrad-Zuse-Zentrum für Informationstechnik Berlin
www.zib.de/koch  /          Takustraße 7, 14195 Berlin-Dahlem, Germany
koch at zib.de     /                     Phone +49-30-84185-213, Fax -269
_______________/  DFG Research Center "Matheon"  http://www.matheon.de

Kooperativer Bibliotheksverbund Berlin Brandenburg  http://www.kobv.de
______________________________________________________________________