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

Tue May 15 15:41:35 MEST 2012

Thank you for your advice. As you mentioned, it's more simple for just focus on an approximation solution rather than an optimal one. Now I am tring a greedy search algorithm. hope it works. Also thank you for the papers you recommended，they are of great help.  I think i need to do more homework on understanding MIP and LP.  :)

best,
YangXu

Nick Downing <downing.nick at gmail.com>编写：

>Well firstly if you are a researcher I suggest a literature search, I
>did a quick one, see:
>  http://studia.complexica.net/Art/RI090304.pdf
>In that one it says that the MIP gap is normally a problem for CFLP
>(actually in their case SSCFLP).  It also says "Tightening MIP
>formulations by deriving Lifted Cover Inequalities from knapsack
>constraints is now a common technique, embedded into most of the MIP
>solvers", is this the case for SCIP?
>  http://igitur-archive.library.uu.nl/math/2006-1221-201233/aardal_96_reformulation.pdf
>That one is by Karen Aardal who appears to have a large number of
>papers on the topic.  But if you are new to the field, implementing a
>custom branch-and-cut is going to be out of your reach, have you
>considered using heuristics?  I mean, does the problem really need to
>be solved to optimality or is a "good solution" enough?  See
>  http://www.springerlink.com/content/jgx457v7219451h0/
>This involves a Lagrangean relaxation which is also probably not
>suitable for a novice to try to implement but maybe you can find
>simpler (less accurate) heuristics?
>
>Secondly you can just try to understand how the large MIP gap arises.
>For example suppose I have an integer variable x in range 0..105 and a
>Boolean variable a which controls whether x <= 5, that is, there's a
>constraint "not a -> (x <= 5)".  Then this would be entered into the
>solver as "x <= 5 + 100a" so that the constraint has no effect (x <=
>105) when a is 1 (true).  This is called a big-M constraint where M
>refers to the large coefficient of a.  Such a formulation has a weak
>relaxation because, for example, suppose the solver wants to set x <=
>15, it can achieve this by setting a=0.1 which is cheating since a is
>Boolean (0 or 1).  So it would only pay 1/10 the "true cost" of
>setting a=true, and the difference appears in the MIP gap.  So if you
>can avoid using these kinds of big-M or similar constraints in your
>formulation, things will improve.
>
>cheers, Nick
>
>cheers, Nick
>
>On Tue, May 15, 2012 at 5:39 AM, Thorsten Koch <koch at zib.de> wrote:
>> 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
>> ______________________________________________________________________
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip