Re: [Help-glpk] Solving MathProg on your phone
... also worked on Samsung Galaxy S3 using Firefox. Very neat! On Mon, Dec 31, 2012 at 4:44 PM, Jeffrey Kantor kanto...@nd.edu wrote: Here's the current version of a web page based on Henri Gourvest's glpk.js (and with a lot of generous help from Henri) that I'm developing for a course this Spring. The goal is a small footprint, 'zero-install', cross-platform tool, for teaching the application of OR methods to business and operations. I'm still sorting out some bugs with the menus, but thought there might be some interest in this. https://dl.dropbox.com/u/2140549/mathprog/mathprog.html Note that glpk.js is doing all the work within the browser. You can cut and paste your own models into the edit window or load them from your local files. The 'aha' moment for me was solving a MathProg model on my phone (iPhone 4S w/Safari) and iPad (the menus are really broken under iOS, but glpk.js appears to work fine.) Certainly welcome feedback. Jeff ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] binary boolean
Thanks Andrew. Would it make sense then to incorporate Tseitin's transforms into mathprog as a default method for implementing boolean conditions? Thanks Yaron On Sat, May 5, 2012 at 1:49 AM, Andrew Makhorin m...@gnu.org wrote: See also Tseitin's transformations: http://en.wikipedia.org/wiki/Tseitin-Transformation These transformations can be used to describe any Boolean function in a more or less efficient way, in particular, to model any digital circuit logic like adders, multipliers, dividers, etc. The mip preprocessor implemented in glpk uses these transformations to reduce the mip instance to the satisfiablity problem in order to find an integer feasible solution with the Minisat solver (--minisat). ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] binary boolean
Since the conversion from mathematical formulation to constraints is systematic , could this be added to marhprog? On May 3, 2012, at 7:08, Erwin Kalvelagen er...@amsterdamoptimization.com wrote: z = x z = y z = x+y Erwin Kalvelagen Amsterdam Optimization Modeling Group er...@amsterdamoptimization.com http://amsterdamoptimization.com On Thu, May 3, 2012 at 8:29 AM, Zvonko Bregar zvonko.bre...@eimv.si wrote: Hi, My name is Zvonko. I have a question regarding binary variables in GLPK. Is it possible to implement a kind of a boolean addition to binary variables. For example: Let X, Y and Z be binary variables. X and Y ara inputs, Z is a result. X + Y = Z Such that 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 1 So this would be sometning like a logical .OR. addition? Many thanks Regards --Zvonko OPOZORILO: To elektronsko sporočilo in vse njegove morebitne priloge lahko vsebujejo zaupne in/ali privilegirane informacije, ki so last Elektroinštituta Milan Vidmar in so namenjene izključno naslovniku. Če ste sporočilo prejeli pomotoma zaradi napake v naslovu ali pri prenosu sporočila, Vas prosimo, da nas o tem obvestite s povratno pošto. V tem primeru vsebine prejetega sporočila ne smete uporabiti, kopirati, tiskati, objaviti ali distribuirati, ampak ga morate takoj uničiti. DISCLAIMER: This e-mail is for the intended recipient only. It contains proprietary information some or all of which may be legally privileged. If you received this e-mail by mistake please notify us by replying to this e-mail. Consequently, the contents of this e-mail must be deleted and not be used, copied, printed, disclosed or distributed. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] binary boolean
Is there a default that can be applied? It seems that the boolean operator question keeps being asked (infrequently) , and very similar answers provided. Starting with the z=x OR y example- it would be interesting to get several different ways of implementing that, in addition to the one already proposed. On Thu, May 3, 2012 at 9:13 PM, Andrew Makhorin m...@gnu.org wrote: Since the conversion from mathematical formulation to constraints is systematic , could this be added to marhprog? No, it is not. There exist infinitely many mip descriptions of the same integer set. Even z = x OR y can be formulated in infinitely many ways. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Parsing large, sparse mathprog model takes a (very) long time
Hi Andrew This works very well. The parsing time drops from 6 hours to 25 seconds. Thanks a lot! Yaron On Mon, May 2, 2011 at 2:40 AM, Andrew Makhorin m...@gnu.org wrote: I have a mathprog model which takes a long time to parse: The model is of a set-to-set routing problem- There is a bipartite graph, and the objective is to establish connections between the two parts such that a length metric is minimized. There are ~76K nodes in each half of the graph (for a total of ~150K nodes), and a total of 500K edges between the nodes. The model has been parsing (i.e. haven't reached presolving stage yet) for more than an hour now. Memory consumption is increasing, but thus far is quite low (200M). Is this long parse time reasonable? Are there ways of rewriting which would speed up parsing? Since the model is quite large, I put it on http://foodproj.org/set_to_set_routing.zip This is implementation defect, that is, the mathprog translator evaluates all expressions as they are coded performing no optimization. Thus, if you write s.t. every_to_pin_connected_to_one {t in toset} : sum {f in fromset :(f,t) in connection } from_connects_to[f,t] == 1; this statement is evaluated as follows: for {t in toset} { for {f in fromset} { if {(f,t) in connection} ...evaluate constraint expressions... } } and the total evaluation time is |toset| * |fromset| * log |connection| = 75887 * 75887 * 20 = VERY LONG TIME (log is because the logarithmic search is used in innermost if). I changed your model to make it a bit more efficient (see Version A below). However, generating it still takes much time. Ideally, to decrease the evaluation time you need to use two arrays of sets, say, conn1 and conn2 declared as follows: set conn1{f in fromset}, within toset; set conn2{t in toset}, within fromset; This would allow you using a more efficient construction like follows: s.t. every_to_pin_connected_to_one {t in toset} : sum {f in conn2[t] } from_connects_to[f,t] == 1; However, this requires changing the data section. To avoid changing the data section you may use an undocumented feature of mathprog, which allows you generating set data on the fly as if there were appropraite data statements. Please see Version B below; it takes less than a minute to generate the model. Andrew Makhorin Version A - /* set to set routing Copyright Yaron Kretchmer yaronkretch...@gmail.com */ set fromset := {0..75887}; set toset := {0..75887}; set connection dimen 2 ; param distance{(f,t) in connection } ; var overall_distance; var from_connects_to {f in fromset,t in toset : (f,t) in connection}, binary ; /* Every To pin is connected to exactly one from pin i.e. all to pins are connected */ s.t. every_to_pin_connected_to_one {t in toset} : sum {f in fromset :(f,t) in connection } from_connects_to[f,t] == 1; /* Every from pin connected to at most one to pin i.e. some from pins might be disconnected*/ s.t. every_from_pin_connected_to_one_or_zero {f in fromset} : sum {t in toset :(f,t) in connection } from_connects_to[f,t] = 1; s.t. overall_distance_def : overall_distance = sum {(f,t) in connection } from_connects_to[f,t]*distance[f,t]; minimize overall_distance2 : sum {(f,t) in connection} from_connects_to[f,t]; data; . . . Version B - /* set to set routing Copyright Yaron Kretchmer yaronkretch...@gmail.com */ set fromset := {0..75887}; set toset := {0..75887}; set connection dimen 2 ; param distance{(f,t) in connection } ; set conn1{f in fromset}, data connection(1,2), default {}; set conn2{t in toset}, data connection(2,1), default {}; /*display conn1, conn2;*/ var overall_distance; var from_connects_to {(f,t) in connection}, binary ; /* Every To pin is connected to exactly one from pin i.e. all to pins are connected */ s.t. every_to_pin_connected_to_one {t in toset} : sum {f in conn2[t] } from_connects_to[f,t] == 1; /* Every from pin connected to at most one to pin i.e. some from pins might be disconnected*/ s.t. every_from_pin_connected_to_one_or_zero {f in fromset} : sum {t in conn1[f] } from_connects_to[f,t] = 1; s.t. overall_distance_def : overall_distance = sum {(f,t) in connection } from_connects_to[f,t]*distance[f,t]; minimize overall_distance2 : sum {(f,t) in connection} from_connects_to[f,t]; solve ; for {(f,t) in connection : distance[f,t]0 from_connects_to[f,t]0/**/} { printf %s,%s %s %s - %s, from_connects_to[f,t],f,t,distance[f,t];printf \n; } data ; . . . ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Parsing large, sparse mathprog model takes a (very) long time
Hi All. I have a mathprog model which takes a long time to parse: The model is of a set-to-set routing problem- There is a bipartite graph, and the objective is to establish connections between the two parts such that a length metric is minimized. There are ~76K nodes in each half of the graph (for a total of ~150K nodes), and a total of 500K edges between the nodes. The model has been parsing (i.e. haven't reached presolving stage yet) for more than an hour now. Memory consumption is increasing, but thus far is quite low (200M). Is this long parse time reasonable? Are there ways of rewriting which would speed up parsing? Since the model is quite large, I put it on http://foodproj.org/set_to_set_routing.zip Thanks and Best Regards Yaron ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Size of big-M changes solution of MIP problem
Hi All After struggling with the problem below for a couple of days, I thought of asking for help- My big-M formulation is behaving in a way that i can't understand. The problem is a stock hedging problem, with one of the component of a correct hedge being that the strike price of the option is = the value of the stock. The enclosde model should have no solution, since I'm fixing the variable such that the price of the option is does not follow the constaint above. When my big-M = 909, I get the correct No primal feasible answer. But when I increase M to 910, a succesful solution is found, which is not correct. Are there any upper limits to the size of big-M that can be used? Thanks Yaron /* RSU Hedger Yaron Kretchmer ya...@foodproj.org */ /* big M */ param M := 910 /*909*/ ; /* How many RSU grants */ set num_rsus := {1..4}; /* How many options */ set num_options := {1..998}; /* What's a put option? */ set put_option_params := {'cost' ,'strike_price', 'strike_date'}; /* What's an RSU? */ set rsu_params := {'value','quantity' ,'strike_date'}; /* Set of RSU's to protect */ param rsus {n in num_rsus,p in rsu_params} symbolic; param put_options {put in num_options,pop in put_option_params} symbolic ; var put_options_quantity {put in num_options} =0 integer; var option_protects_rsu {rsu in num_rsus, option in num_options} binary ; var option_quantity_larger_than_rsu_quantity {rsu in num_rsus, option in num_options} binary ; var option_date_later_than_rsu_date {rsu in num_rsus, option in num_options} binary ; var option_covers_rsu_value {rsu in num_rsus, option in num_options} binary ; var cost_of_options ; /* Each option quantity and dates is larger than zero*/ /* Each RSU is protected by at least one option */ s.t. each_rsu_is_protected {rsu in num_rsus} : sum{option in num_options} option_protects_rsu[rsu,option] =1 ; /* Each option protects at most one RSU*/ s.t. each_option_protects_at_most_1 {option in num_options} : sum{rsu in num_rsus} option_protects_rsu[rsu,option] =1 ; /* option_quantity_larger_than_rsu_quantity is true if the option quantity is larger than the RSU quantity */ s.t. define_option_quantity_larger_than_rsu_quantity {option in num_options,rsu in num_rsus} : -M = put_options_quantity[option]-floor(rsus[rsu,'quantity'])-option_quantity_larger_than_rsu_quantity[rsu,option]*M=0; /* option_date_later_than_rsu_date is true if the option date is later than the RSU date */ s.t. define_option_strike_price_greater_than_rsu_value {option in num_options,rsu in num_rsus} : (option_covers_rsu_value[rsu,option]-1)*M= put_options[option,'strike_price']-rsus[rsu,'value']; s.t. define_option_strike_price_greater_than_rsu_value_2 {option in num_options,rsu in num_rsus} : put_options[option,'strike_price']-rsus[rsu,'value']=option_covers_rsu_value[rsu,option]*M; s.t. define_option_date_later_than_rsu_date {option in num_options,rsu in num_rsus} : -M = ceil((str2time(put_options[option,'strike_date'],%m/%d/%y)-str2time(rsus[rsu,'strike_date'],%m/%d/%y)) /86400 )-option_date_later_than_rsu_date[rsu,option]*M=0; /* If an option protects an RSU, then its quantity is larger than the RSU quantity This constraint is of the if-then variety, and is modeled as follows A = B which means that if A is 1, B has to be 1, and if A is 0, B can be anything. A is An option protects an RSU, and B is the option quantity is larger than the RSU quantity */ /* s.t. temp1 : option_protects_rsu[2,328] = 1; */ s.t. option_quantity_bigger_than_rsu {option in num_options,rsu in num_rsus} : option_protects_rsu[rsu,option] = option_quantity_larger_than_rsu_quantity[rsu,option]; s.t. option_date_later_than_rsu {option in num_options,rsu in num_rsus} : option_protects_rsu[rsu,option] = option_date_later_than_rsu_date[rsu,option]; s.t. option_strike_price_greater_than_rsu_value {option in num_options,rsu in num_rsus} : option_protects_rsu[rsu,option] =option_covers_rsu_value[rsu,option] ; s.t. temp11 : option_protects_rsu[1,3]=1; s.t. temp12 : option_protects_rsu[2,403]=1; s.t. temp13 : option_protects_rsu[3,928]=1; s.t. temp14 : option_protects_rsu[4,929]=1; /* s.t. temp1 {option in num_options,rsu in num_rsus} : 3*option_protects_rsu[rsu,option] = option_quantity_larger_than_rsu_quantity[rsu,option] + option_date_later_than_rsu_date[rsu,option] + option_covers_rsu_value[rsu,option] ; */ /* If an option protects an RSU, then its date is later than the RSU date. This is done using a similar formulation as above */ /* s.t. temp1 : option_protects_rsu[2,403]=1; */ s.t. cost_of_options_definition : cost_of_options =sum {option in num_options} put_options_quantity[option]*put_options[option,'cost']; minimize cost_of_options_min: cost_of_options; solve; for {option in num_options:put_options_quantity[option]0} : printf
Re: [Help-glpk] Modelling Advice Request - Project Tasks
I solved your enclosed model in 350sec. using SCIP (Answer was 5 ) with no special settings. Some restrictions on the variables vectors that should sum to 1 ( I forgot what the nomenclature for those are) can definitely reduce that further. Cheers Kretch On Wed, Jan 20, 2010 at 4:01 PM, Tawny Owl tow_fo...@hotmail.com wrote: I am modelling a project in which doing some tasks before others will save time. I think that the model is correct - but even though I have only entered the savings for 1 task into the objective function, it is taking too long to run. I believe that the problem lies in my before1 and before2 conditions, each of which contain 15^4=50625 modelling variables. These conditions are needed to enable the before[] variable, where before[a,b]=1 means that task a will be completed before task b. The variable position[] is working correctly (position[5]=3 means that task five will be done third). I could eliminate the huge amount of work being done in the before1 and before2 conditions if I could make use of these position variables. Could anyone advise me how I can achieve the following, please? * if position[a] position[b], then before[a,b] = 0 * if position[a] position[b], then before[a,b] = 1 Thanks for any suggestions! Model appended below: /* The project consists of 15 tasks. Completion of any of these tasks will save time on other tasks in the project as follows: Task 1 savings: 2 hours on task 2: 2 hours on task 4: 1 hours on task 9 Task 2 savings: 2 hours on task 1: 3 hours on task 15 Task 3 savings: 4 hours on task 1: 1 hours on task 5 Task 4 savings: 1 hours on task 1: 1 hours on task 3: 2 hours on task 5: 1 hours on task 10 Task 5 savings: 1 hours on task 2: 1 hours on task 10: 1 hours on task 13: 1 hours on task 14: 1 hours on task 15 Task 6 savings: 1 hours on task 4: 1 hours on task 8: 2 hours on task 11: 1 hours on task 15 Task 7 savings: 2 hours on task 2: 3 hours on task 15 Task 8 savings: 4 hours on task 5: 1 hours on task 11 Task 9 savings: 1 hours on task 2: 2 hours on task 3: 1 hours on task 11: 1 hours on task 13 Task 10 savings: 4 hours on task 11: 1 hours on task 15 Task 11 savings: 1 hours on task 1: 1 hours on task 3: 1 hours on task 8: 1 hours on task 10: 1 hours on task 12 Task 12 savings: 3 hours on task 1: 1 hours on task 4: 1 hours on task 11 Task 13 savings: 2 hours on task 3: 3 hours on task 12 Task 14 savings: 1 hours on task 3: 1 hours on task 6: 1 hours on task 7: 1 hours on task 8: 1 hours on task 12 Task 15 savings: 2 hours on task 6: 2 hours on task 12: 1 hours on task 13 */ var task{1..15, 1..15}, binary; s.t. task1{a in 1..15}: sum{b in 1..15} task[a, b] = 1; s.t. task2{b in 1..15}: sum{a in 1..15} task[a, b] = 1; var position{1..15}, = 0; s.t. position1{a in 1..15}: sum{b in 1..15} b * task[b,a] = position[a]; var before{1..15, 1..15}, binary; s.t. before1{a in 1..15, b in 1..15, c in 1..15, d in 1..15: b a and c != d}: before[c,d] + 1.5 = task[a,c] + task[b,d]; s.t. before2{a in 1..15, b in 1..15, c in 1..15, d in 1..15: a b and c != d}: before[c,d] + task[a,c] + task[b,d] = 2.5; var saving{1..15}, = 0; s.t. s1: saving[1] = 2 * before[1,2] + 2 * before[1,4] + before[1,9]; maximize savings: saving[1]; solve; for {a in 1..15} { for {b in 1..15: task[a,b] = 1} { printf %s. Task %s\n, a, b; } } for {a in 1..15, b in 1..15: before[a,b] = 0.5 and a != b}{ printf task %s is done before task %s\n, a, b; } for {a in 1..15} { printf Position of task %s: %s\n, a, position[a]; } printf \nTotal Savings: %s hours., saving[1]; end; -- Not got a Hotmail account? Sign-up now - Freehttp://clk.atdmt.com/UKM/go/19780/direct/01/ ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Modelling Advice Request - Project Tasks
Soplex, but the heavy MIP lifting is done by scup On Jan 20, 2010, at 17:05, Yingjie Lan lany...@yahoo.com wrote: I solved your enclosed model in 350sec. using SCIP (Answer was 5 ) with no special settings. Seems NEOS SCIP can be hooked up to many different solvers (including GLPK), I wonder which solver are you using behind SCIP? * if position[a] position[b], then before[a,b] = 0 * if position[a] position[b], then before[a,b] = 1 Big-M: M = 15 - 1 given 15 tasks. position[b] - position[a] = M * before[a,b] position[a] - position[b] = M * before[b,a] before[a,b]+before[b,a] == 1 /* The project consists of 15 tasks. Completion of any of these tasks will save time on other tasks in the project as follows: Task 1 savings: 2 hours on task 2: 2 hours on task 4: 1 hours on task 9 Task 2 savings: 2 hours on task 1: 3 hours on task 15 Task 3 savings: 4 hours on task 1: 1 hours on task 5 Task 4 savings: 1 hours on task 1: 1 hours on task 3: 2 hours on task 5: 1 hours on task 10 Task 5 savings: 1 hours on task 2: 1 hours on task 10: 1 hours on task 13: 1 hours on task 14: 1 hours on task 15 Task 6 savings: 1 hours on task 4: 1 hours on task 8: 2 hours on task 11: 1 hours on task 15 Task 7 savings: 2 hours on task 2: 3 hours on task 15 Task 8 savings: 4 hours on task 5: 1 hours on task 11 Task 9 savings: 1 hours on task 2: 2 hours on task 3: 1 hours on task 11: 1 hours on task 13 Task 10 savings: 4 hours on task 11: 1 hours on task 15 Task 11 savings: 1 hours on task 1: 1 hours on task 3: 1 hours on task 8: 1 hours on task 10: 1 hours on task 12 Task 12 savings: 3 hours on task 1: 1 hours on task 4: 1 hours on task 11 Task 13 savings: 2 hours on task 3: 3 hours on task 12 Task 14 savings: 1 hours on task 3: 1 hours on task 6: 1 hours on task 7: 1 hours on task 8: 1 hours on task 12 Task 15 savings: 2 hours on task 6: 2 hours on task 12: 1 hours on task 13 */ can reduce the before[,] variables somehow, create variable pair: before[a,b] and before[b,a] only if task a, b are related in savings. Cheers, Yingjie ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Is GLPK the software that I have been looking for?
Try scip, which can give you all solutions. It's free for academic or personal use,as far as I know Sent from my iPhone On Nov 3, 2009, at 10:10 AM, Erik esi...@gmail.com wrote: I have been searching around for a program to find solutions to little problems like this: An item of meat costs 160. An item of fish costs 30. An item of milk costs 15. Someone spent 700 and bought at most 6 items. What did he buy? What I want is to just input some constraints: k * 160 + m * 30 + n * 15 = 700 k + m + n ≤ 6 and then get all solutions: k = 4, m = 2, n = 0 Is GLPK the right tool for this kind of problem? I started to read the documentation, but GLPK seems more about finding an optimal solution than finding all solutions. That might be a problem. First I looked at logilab-constraint and PuLP, that are supposed to be able to solve it. But I read about them, and they seem to be Python frontends for GLPK (or some other solver), and since I do not know Python so well, I might just try to use GLPK directly. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] More conditional variables fun
Alex,Michael,Andrew,Larry- Thanks a lot for all the help and the great discussion. I'll summarize the different approaches in a separate email for future reference. Regards Kretch. On Wed, Oct 14, 2009 at 1:45 AM, Alexander Schnell le...@web.de wrote: Hi there, i have found out a formulation for your problem but the linear formulation is quite long: the nonlinear formulation is quite short: c = d*b*(b-a)+ e*a*(a-b). So now you can substitute the term d*b*(b-a) by the variable x and the term e*a*(a-b) by the variable y. b*(b-a) is the produkt of the binary variable b and the variable (b-a) in {-1,0,1} and substituted by z. (z is binary) a*(a-b) is also the product of the binary variable a and the variable (a-b) in {-1,0,1} and substituted by w. (w is binary) so we yield the following equations: 1) c = x + y 2) x = d * z 3) y = e * w 4) z = b*(b-a) 5) w = a*(a-b) Now you can reformulate 2)- 5) to yield linear equations: 2a) x = M1 *z where M1 is an upper bound for the variable x 2b) x - d = M2 * (1-z) where M2 is an upper bound for the difference x - d 2c) d - x = M3 * (1-z) where M3 is an upper bound for the difference d - x this reformulation of 2) can only be done as z is binary. Now 3) can be reformulated equivalently as w is binary: 3a) y = M4 *w where M4 is an upper bound for the variable y 3b) y - e = M5 * (1-w) where M5 is an upper bound for the difference y - e 3c) e -y = M6 * (1-w) where M6 is an upper bound for the difference e - y As b is a binary variable, you can formulate 4) and 5) as follows: 4a) z = b 4b) z - b + a = 2 * (1 - b) 2 is an upper bound for z - (b-a) 4c) b - a - z = 1 * (1 - b) 1 is an upper bound for (b - a) - z and analogly 5) 5a) w = a 5b) w - a + b = 2 * (1 - a) 2 is an upper bound for w - (a-b) 5c) a - b - w = 1 * (1 - a) 1 is an upper bound for (a - b) - w So by contraints 1), 2a)-c), 3a)-c), 4a)- c) and 5a)- c) and forcing z and w to be binary you can formulate a model in mathprog for your problem. Best Regards, Alex ___ Neu: WEB.DE DSL bis 50.000 kBit/s und 200,- Euro Startguthaben! http://produkte.web.de/go/02/ ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] More conditional variables fun
Michael, I'm sorry, but I didn't understand your explanation below- This is due to my limited LP/MIP understanding- sigh.. But, looking at the examples on http://www.aimms.com/aimms/download/manuals/AIMMS3OM_IntegerProgrammingTricks.pdfand doing some math led me to the following formulation: ---begin formulation-- not_a_and_b = (1-a) not_a_and_b = b not_a_and_b = b-a not_b_and_a = (1-b) not_b_and_a = a not_b_and_a = a-b d_if_not_a_and_b = U*not_a_and_b d_if_not_a_and_b = d d_if_not_a_and_b = d -U*(1-not_a_and_b) d_if_not_a_and_b = 0 e_if_not_b_and_a = U*not_b_and_a e_if_not_b_and_a = e e_if_not_b_and_a = e-U*(1-not_b_and_a) e_if_not_b_and_a = 0 d_if_not_a_and_b_or_e_if_not_b_and_a = d_if_not_a_and_b+e_if_not_b_and_a -end formulation-- Is this close to what you were suggesting? Thanks Kretch On Tue, Oct 13, 2009 at 10:16 AM, Michael Hennebry henne...@www.cs.ndsu.nodak.edu wrote: On Mon, 12 Oct 2009, Yaron Kretchmer wrote: Thanks Michael Yes, the differences (and the variables themselves) are bounded. We can denote the the upper/lower limit for each variable/difference by the constants l(x) and u(x). First, I made a mistake: The sets have seven extreme points each, one for one value of (a,b) and two each for the others. What would the formulation be in that case? I think I'll let you do the math. Each constraint will be tight at three of the extreme points. That gives you three equations in four variables. Scaling is allowed, so one of the variables may be fixed. Check to make sure that the other extreme points satisfy the constraint. If some slacks are positive and others negative, the facet you have been deriving is invalid. If all are nonpositive and three are zero, then the direction is wrong. Note that you do not have to use constant bounds. If the bounds depend on (a,b) that is just fine. The narrower the bounds, the tighter the linear relaxation will be. Narrowing bounds might be worth considerable effort. ][Michael Hennebry wrote:] the feasible sets of (a,b,c-d) and (a,b,c-e) have four extreme points. Their convex hulls are tetrahedra. ]Yaron Kretchmer wrote: Now I'd like to be able to model conditional non-binary variables. Does ]]][Yaron Kretchmer wrote:] anybody know how to formulate this in mathprog? --Begin Description --- *) a,b are binary *) c,d,e is continuous. *) I'd like c to be - 0 if a=b=0 - d if a=0,b=1 - e if a=1,b=0 - 0 if a=b=1 --End Description -- Michael henne...@web.cs.ndsu.nodak.edu Pessimist: The glass is half empty. Optimist: The glass is half full. Engineer: The glass is twice as big as it needs to be. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] More conditional variables fun
Hi There. Using feedback I got from the mailing list, I was able to formulate binary conditional variables. Now I'd like to be able to model conditional non-binary variables. Does anybody know how to formulate this in mathprog? --Begin Description --- *) a,b are binary *) c,d,e is continuous. *) I'd like c to be - 0 if a=b=0 - d if a=0,b=1 - e if a=1,b=0 - 0 if a=b=1 --End Description Thanks much Kretch ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] More conditional variables fun
Thanks Larry. What I was looking for is for a way of forcing the C variable to equal values per the truth table. If C was binary I could achieve this by a series of inequalities without big M, and I'm just wondering what would be the formulation for non-binary variables. Regards Kretch On Mon, Oct 12, 2009 at 1:41 PM, D'Agostino, Larry - TX Larry.D'agost...@gmacrescap.com larry.d%27agost...@gmacrescap.com wrote: Try thinking in terms of a Big M or large variable method. For instance… continuous variable expression ** (some large number) (binary variable) so you may do expression = M * (a + b) where M is a very large number -- *From:* help-glpk-bounces+larry.d'agostino=gmacrescap@gnu.org [mailto: help-glpk-bounces+larry.d'agostinohelp-glpk-bounces%2Blarry.d%27agostino =gmacrescap@gnu.org] *On Behalf Of *Yaron Kretchmer *Sent:* Monday, October 12, 2009 3:24 PM *To:* help-glpk *Subject:* [Help-glpk] More conditional variables fun Hi There. Using feedback I got from the mailing list, I was able to formulate binary conditional variables. Now I'd like to be able to model conditional non-binary variables. Does anybody know how to formulate this in mathprog? --Begin Description --- *) a,b are binary *) c,d,e is continuous. *) I'd like c to be - 0 if a=b=0 - d if a=0,b=1 - e if a=1,b=0 - 0 if a=b=1 --End Description Thanks much Kretch ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] More conditional variables fun
Yes, but since b,d,e,a are all variables I can't just multiply. Regards Kretch On Mon, Oct 12, 2009 at 1:53 PM, D'Agostino, Larry - TX Larry.D'agost...@gmacrescap.com larry.d%27agost...@gmacrescap.com wrote: Sorry for double posting. Actually you might want to try something to the affect of c = d*b + e*a -- *From:* help-glpk-bounces+larry.d'agostino=gmacrescap@gnu.org [mailto: help-glpk-bounces+larry.d'agostinohelp-glpk-bounces%2Blarry.d%27agostino =gmacrescap@gnu.org] *On Behalf Of *D'Agostino, Larry - TX *Sent:* Monday, October 12, 2009 3:42 PM *To:* Yaron Kretchmer; help-glpk *Subject:* RE: [Help-glpk] More conditional variables fun Try thinking in terms of a Big M or large variable method. For instance… continuous variable expression ** (some large number) (binary variable) so you may do expression = M * (a + b) where M is a very large number -- *From:* help-glpk-bounces+larry.d'agostino=gmacrescap@gnu.org [mailto: help-glpk-bounces+larry.d'agostinohelp-glpk-bounces%2Blarry.d%27agostino =gmacrescap@gnu.org] *On Behalf Of *Yaron Kretchmer *Sent:* Monday, October 12, 2009 3:24 PM *To:* help-glpk *Subject:* [Help-glpk] More conditional variables fun Hi There. Using feedback I got from the mailing list, I was able to formulate binary conditional variables. Now I'd like to be able to model conditional non-binary variables. Does anybody know how to formulate this in mathprog? --Begin Description --- *) a,b are binary *) c,d,e is continuous. *) I'd like c to be - 0 if a=b=0 - d if a=0,b=1 - e if a=1,b=0 - 0 if a=b=1 --End Description Thanks much Kretch ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Problem glpk using mysql, error string literal too long.
Can this be changed? Limitations on string lengths are a bit passe IMHO, in the era of C++ and STL Regards Yaron On Fri, Oct 9, 2009 at 11:58 PM, Andrew Makhorin m...@gnu.org wrote: I have problem with glpk debian package in Lenny in discusses with help-glpk list, I receive sugestions to change constant in src/glpmpl.h file to MAX_LENGTH 1000 according as email following down. MAX_LENGTH (in glpmpl.h) must not be greater than 255; this is limited by underlying data structure (DMP) used to store character strings. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] very small infeas= values in glpsol
Thanks Andrew. How can you tell that the model is degenerate? (and what does degenerate mean?) Also, how do I use the cutting plane options? Thanks Yaron On Sat, Oct 10, 2009 at 12:29 AM, Andrew Makhorin m...@gnu.org wrote: I'm solving a semiconductor routing problem, and running glpsol, I'm running into very long solution times, accompanied by very small infeasibility numbers. Some questions: *) What do the infeasibility numbers mean? Does it matter that they're very small? Once a next node subproblem is selected, the mip solver uses the dual simplex to find optimal solution to its lp relaxation. If the solution takes more than 5 seconds, the underlying simplex solver starts terminal output to prevent a dead screen, so you see something like this: . . . +129044: mip = not found yet = 2.4e+002(14; 9) |130400: obj = 2.4e+002 infeas = 0.000e+000 (664) |130600: obj = 2.4e+002 infeas = 0.000e+000 (663) |130800: obj = 2.4e+002 infeas = 1.988e-014 (662) |131000: obj = 2.4e+002 infeas = 0.000e+000 (662) . . . 'infeas' is the sum of scaled dual infeasibilities usually reported by the glpk simplex solvers. Normally it must be close to zero, because on re-optimization the current basic solution is always dual feasible within a working precision. *) Is there a way/runtime-option I can use to speed up the solution times? Your instance seems to be highly degenerate and therefore hard for the glpk mip solver. You could try either reformulating it or using cutting plane options. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Re: GLPK vs. SCIP for solving MIP Click to flag this post
Yes, I've checked it out. It's similar in concept , but has some differences -I do not believe you get database connectivity with Zimpl - Zimpl allowes you to model if-then-else relationships between variable, dealing with the conditional variables under the hood, whereas GLPK forces you to make everything explicit. The path Mathprog-GLPK-LP-SCIP works fine. Cheers Kretch On Sat, Oct 3, 2009 at 12:54 AM, Tawny Owl tow_fo...@hotmail.com wrote: I've grown used to GMPL, I haven't used it myself, but the modelling language Zimpl, which can be used with SCIP, appears to have similarities with MathProg. http://zimpl.zib.de/ Use Hotmail to send and receive mail from your different email accounts. Find out how. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] GLPK vs. SCIP for solving MIP
Ali- Excellent suggestion. I followed your advice, translated into LP, and got scip to solve my problem (with no extra settings) in less than 20min. I also tried writing out to MPS (both wmps and freemps), but for some reason scip produced incorrect results. Thanks Yaron On Fri, Oct 2, 2009 at 4:30 AM, Ali Baharev ali.baha...@gmail.com wrote: Hi, SCIP implements more heuristics than GLPK. In certain cases this can make a significant difference. Why don't you just use GLPK to translate your GMPL model into cplex lp format and than use SCIP to solve that? In this way you do not have to learn anything new. Of course, you have to find the proper settings to make SCIP solve your problems quickly. Good luck, Ali ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] very small infeas= values in glpsol
Hi All. I'm solving a semiconductor routing problem, and running glpsol, I'm running into very long solution times, accompanied by very small infeasibility numbers. Some questions: *) What do the infeasibility numbers mean? Does it matter that they're very small? *) Is there a way/runtime-option I can use to speed up the solution times? Thanks Yaron Here's an example: Begin Example--- c:\gusek\glpsol.exe --mostf -m ..--cuts GLPSOL: GLPK LP/MIP Solver 4.39 Reading model section from Sep26_Giles_mcf.mod... Reading data section from Sep26_Giles_mcf.mod... 3856 lines were read ... Generating obj... Model has been successfully generated ipp_basic_tech: 276317 row(s) and 221492 column(s) removed ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced ipp_basic_tech: 0 row(s) and 0 column(s) removed ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced glp_intopt: presolved MIP has 58300 rows, 34866 columns, 163658 non-zeros glp_intopt: 34866 integer columns, all of which are binary Scaling... A: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000 Problem data seem to be well scaled Constructing initial basis... Size of triangular part = 58300 Solving LP relaxation... 0: obj = 0.0e+000 infeas = 1.532e+003 (0) ... * 20600: obj = 2.33000e+002 infeas = 2.545e-015 (0) * 20682: obj = 2.4e+002 infeas = 2.643e-015 (0) OPTIMAL SOLUTION FOUND Integer optimization begins... Gomory's cuts enabled MIR cuts enabled Cover cuts enabled Clique cuts enabled Creating the conflict graph... The conflict graph is either empty or too big + 20682: mip = not found yet = +inf(1; 0) | 22200: obj = 2.4e+002 infeas = 1.517e-013 (0) | 22400: obj = 2.4e+002 infeas = 7.154e-014 (0) | 22600: obj = 2.4e+002 infeas = 5.790e-016 (0) | 22800: obj = 2.4e+002 infeas = 2.508e-014 (0) | 23000: obj = 2.4e+002 infeas = 3.359e-014 (0) ... ... +124073: mip = not found yet = 2.4e+002(14; 9) Time used: 999.5 secs. Memory used: 763.1 Mb. |125200: obj = 2.4e+002 infeas = 0.000e+000 (709) |125400: obj = 2.4e+002 infeas = 5.262e-014 (708) |125600: obj = 2.4e+002 infeas = 2.227e-015 (708) |125800: obj = 2.4e+002 infeas = 0.000e+000 (708) |126000: obj = 2.4e+002 infeas = 0.000e+000 (708) |126200: obj = 2.4e+002 infeas = 8.301e-014 (698) |126202: obj = 2.4e+002 infeas = 8.301e-014 (698) +126202: mip = not found yet = 2.4e+002(14; 9) |127400: obj = 2.4e+002 infeas = 0.000e+000 (693) |127600: obj = 2.4e+002 infeas = 0.000e+000 (693) |127800: obj = 2.4e+002 infeas = 0.000e+000 (693) |128000: obj = 2.4e+002 infeas = 0.000e+000 (693) |128200: obj = 2.4e+002 infeas = 0.000e+000 (693) |128400: obj = 2.4e+002 infeas = 4.223e-014 (693) |128600: obj = 2.4e+002 infeas = 0.000e+000 (681) |128800: obj = 2.4e+002 infeas = 0.000e+000 (677) |129000: obj = 2.4e+002 infeas = 0.000e+000 (677) |129044: obj = 2.4e+002 infeas = 0.000e+000 (677) +129044: mip = not found yet = 2.4e+002(14; 9) |130400: obj = 2.4e+002 infeas = 0.000e+000 (664) |130600: obj = 2.4e+002 infeas = 0.000e+000 (663) |130800: obj = 2.4e+002 infeas = 1.988e-014 (662) |131000: obj = 2.4e+002 infeas = 0.000e+000 (662) |131075: obj = 2.4e+002 infeas = 0.000e+000 (662) +131075: mip = not found yet = 2.4e+002(14; 9) Time used: 1065.0 secs. Memory used: 763.3 Mb. |132400: obj = 2.4e+002 infeas = 1.216e-014 (659) |132600: obj = 2.4e+002 infeas = 0.000e+000 (637) |132800: obj = 2.4e+002 infeas = 0.000e+000 (631) |133000: obj = 2.4e+002 infeas = 0.000e+000 (631) |133102: obj = 2.4e+002 infeas = 0.000e+000 (631) +133102: mip = not found yet = 2.4e+002(15; 9) |134400: obj = 2.4e+002 infeas = 0.000e+000 (719) |134600: obj = 2.4e+002 infeas = 0.000e+000 (716) |134800: obj = 2.4e+002 infeas = 1.084e-014 (716) |135000: obj = 2.4e+002 infeas = 0.000e+000 (714) |135200: obj = 2.4e+002 infeas = 3.699e-014 (710) |135275: obj = 2.4e+002 infeas = 0.000e+000 (709) +135275: mip = not found yet = 2.4e+002(16; 9) |136600: obj = 2.4e+002 infeas = 0.000e+000 (629) |136800: obj = 2.4e+002 infeas = 5.870e-015 (629) |137000: obj = 2.4e+002 infeas = 0.000e+000 (629) |137045: obj = 2.4e+002 infeas = 4.670e-014 (629) +137045: mip = not found yet = 2.4e+002(15; 10) |138400: obj = 2.4e+002 infeas = 0.000e+000 (627) |138450: obj = 2.4e+002 infeas = 0.000e+000 (627) +138450: mip = not found yet = 2.4e+002
[Help-glpk] modeling variable chains
Hi All. I'm working on a chip routing problem using LP, where you have *) Some resources you need to connect *) Some desirable combinations of resources (a.k.a paths) you want to achieve. There is an X/Y array of locations for the resources. I've modeled the resources, and created an array of binary variables which describe whether a certain resource exists in a certain X/Y location. I'm having difficulties modeling the paths. My difficulty is this: - Each path maps to a pattern of resources (for instance R1-R2-R2-R1). I can successfully describe the path contents (i.e. the fact that it contains 2 R1's, and 2 R2's), but how can I describe the order i.e. how do I capture the fact the pattern has to contain adjacent resources (i.e. you don't want a path to include disjoint resources that are spread around your chip, you want resources that are in adjanct X/Y coordinates. So my question: *) How do I model the constraint that the resources mapping to a path need to have consecutive X or Y coordinates? Any help would be most welcome :) Cheers Kretch ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] modeling variable chains
Yes, I haven't thought of that- is that similar to eliminating subtours in TSP? Thanks Michael. Kretch On Thu, Aug 13, 2009 at 3:00 PM, Michael Hennebry henne...@web.cs.ndsu.nodak.edu wrote: On Thu, 13 Aug 2009, Yaron Kretchmer wrote: I've modeled the resources, and created an array of binary variables which describe whether a certain resource exists in a certain X/Y location. I'm having difficulties modeling the paths. My difficulty is this: - Each path maps to a pattern of resources (for instance R1-R2-R2-R1). I can successfully describe the path contents (i.e. the fact that it contains 2 R1's, and 2 R2's), but how can I describe the order i.e. how do I capture the fact the pattern has to contain adjacent resources (i.e. you don't want a path to include disjoint resources that are spread around your chip, you want resources that are in adjanct X/Y coordinates. So my question: *) How do I model the constraint that the resources mapping to a path need to have consecutive X or Y coordinates? This is a lot like finding a path in a sparse graph. Try having binary variables for the arcs instead of the nodes. -- Michael henne...@web.cs.ndsu.nodak.edu Pessimist: The glass is half empty. Optimist: The glass is half full. Engineer: The glass is twice as big as it needs to be. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] logical operators
Hi All My apologies if this has been recently asked- I looked in the archives and didn't find anything Anyways: a,b,c are binary variables. I want c to be 1 if and only if a=b=1. What Big-M forumlation do I need? Thanks Kretch ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Re: Fwd: Gusek question
Perfect- thanks Luiz. As an example of why this is useful: *) let's say that you wanted to automatically ftp the results of your solve to a remote server every time you do a solve. *) You would follow Luiz's advice below, with the os.run line being os.run('cmd /c ruby ftp_me.rb',1,true) where ftp_me.rb is --- require 'open-uri' open(glpk_result.out,r).read(open(ftp://username:passw...@host:port/remote_glpk_result.out;, :proxy=http://proxyhost:proxyport;).write) Then after every solve, the file gets automatically transferred. Nifty! Cheers Yaron On Thu, Jul 30, 2009 at 4:16 PM, Luiz M. M. Bettoni bett...@cpgei.ct.utfpr.edu.br wrote: Hello, Yaron. One way to do that you want is using the properties files and some Lua script. In Gusek, select Options Open User Options File. Paste the following four lines: command.go.$(file.patterns.gmpl)= dostring \ if ($(opnout)~=) then scite.Open($(opnout)) end \ if ($(opnbnd)~=) then scite.Open($(opnbnd)) end \ os.run('cmd /c mybatch.bat',1,true) NOTES: 1. The mybatch.bat file MUST reside in the same model folder or in your path. 2. Please note that this will affect EVERY .mod file that you run in your machine. Even if it is a glpk sample (not a good practice, ya?). To avoid this, you can use the Local Options File besides. It will create a SciTE.properties file in the folder of the active model, and the change will affect only models in this same folder. If you have interest, you can read more about SciTE and make better changes =) Regards, Luiz Yaron Kretchmer escreveu: Thanks Luiz. Can I change the gusek properties so that when I press the Go (shoes) button 1) glpsol.exe will be run 2) After glpsol finishes, the batch.bat file is run If this is possible, how do I do it? Thanks Yaron On Thu, Jul 30, 2009 at 1:45 PM, Luiz Bettoni bett...@cpgei.ct.utfpr.edu.br wrote: Hi, Yaron. Gusek was made like a fork of the SciTE editor dedicated to GLPK. So, you can use SciTE native resources like: A) Edit / include menus to run external tools /scripts (http://www.scintilla.org/SciTEFAQ.html#ToolsMenu) See gmpl.properties: Menu options - open gmpl.properties B) Use Lua Scripting See http://www.scintilla.org/SciTELua.html C) Directly run batch files Open a batch file in Gusek then run it. For example: you can run a custom batch file from Gusek, calling glpsol.exe to solve your model, and then performing another tasks, like this: glpsol.exe --cuts -m test.mod call mybatch.bat delete *.tmp The batch output will be show in the Gusek output pane. Tip: you can use GMPL to generate dynamic batch files too, echoing commands like below, and call them from another batch file. param myfile symbolic := test.bat; printf echo off\n myfile; printf echo Hello, there!\n myfile; printf pause\n myfile; end; Wish this tips helps. Regards! Luiz Yaron Kretchmer escreveu: Luiz- Here's a Gusek question for you: Can I specify a post-processing script (like a shell script ) that will be run once Gusek is done solving? Regards from California Yaron -- Forwarded message -- From: Yaron Kretchmer yaronkretch...@gmail.com Date: Thu, Jul 30, 2009 at 10:36 AM Subject: Gusek question To: help-glpk@gnu.org Hi There. I'd like to run a post-processing script (i.e. some shell script of windows batch) after GLPK has been run, so as the results are better formatted. Is there a hook in Gusek to do that? Thanks Yaron ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] 2D packing with linear programming
Hi All. Here's a model I wrote to do 2D packing with linear programming, including some examples of packing squares. Reason to use linear programming is that packing is just a part of a bigger algorithm I'm writing, but I was so pleased with myself for coming up with the packing part that i decided to share it :) I'm interested in getting feedback on whether there are programatic changes that would speed up the runtime, or any suggestions on improving the code. Also, I noticed that the runtime drops signifcantly when using --mostf . Is that a coincidence? Thanks Kretch spatial.mod Description: Binary data ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Implementing conditional amount constraints using binary variables
a,b should be positive On Wed, Jun 3, 2009 at 12:19 AM, L Sundaravalli sundar1...@yahoo.comwrote: Are values of a and b restricted - or they can be 0 or +ve or -ve? Sundar --- On *Wed, 6/3/09, Yaron Kretchmer yaronkretch...@gmail.com* wrote: From: Yaron Kretchmer yaronkretch...@gmail.com Subject: Re: [Help-glpk] Implementing conditional amount constraints using binary variables To: L Sundaravalli sundar1...@yahoo.com Date: Wednesday, June 3, 2009, 12:11 PM Thanks Sundar, but won't that formulation allow for (for instance), b=5, a=4, which doesn't meet my criteria? Thanks Kretch On Tue, Jun 2, 2009 at 11:13 PM, L Sundaravalli sundar1...@yahoo.comhttp://us.mc05g.mail.yahoo.com/mc/compose?to=sundar1...@yahoo.com wrote: Hi, Assuming your b is positive, this should work: b - a = 0 Regards. Sundar --- On *Wed, 6/3/09, Yaron Kretchmer yaronkretch...@gmail.comhttp://us.mc05g.mail.yahoo.com/mc/compose?to=yaronkretch...@gmail.com * wrote: From: Yaron Kretchmer yaronkretch...@gmail.comhttp://us.mc05g.mail.yahoo.com/mc/compose?to=yaronkretch...@gmail.com Subject: [Help-glpk] Implementing conditional amount constraints using binary variables To: help-glpk@gnu.orghttp://us.mc05g.mail.yahoo.com/mc/compose?to=help-g...@gnu.org Date: Wednesday, June 3, 2009, 9:54 AM Hi All. I would like to implement the following condition on two variables: *) If the amount of variable *a* is greater than 0, then the amount of variable *b* needs to be equal to that of a. *) If the amount of variable a is zero, then the amount of variable b is not restricted. I have a hunch this can be done with binary helper variables *a_bin,b_bin *which describe if a0 and b0, but I can't find a way of describing the relationship. Any insights welcome Kretch -Inline Attachment Follows- ___ Help-glpk mailing list Help-glpk@gnu.orghttp://us.mc05g.mail.yahoo.com/mc/compose?to=help-g...@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Implementing conditional amount constraints using binary variables
Both a and b can be bounded by a large M. So let me reformulate my problem: 0 = a = M if a 0 : a=b if a=0 : 0=b=M Thanks Kretch On Wed, Jun 3, 2009 at 8:42 AM, Michael Hennebry henne...@web.cs.ndsu.nodak.edu wrote: On Tue, 2 Jun 2009, Yaron Kretchmer wrote: I would like to implement the following condition on two variables: *) If the amount of variable *a* is greater than 0, then the amount of variable *b* needs to be equal to that of a. How much greater? Absent a finite number, I suspect that there is no MILP representation. If there is only one such pair of variables, the best solution might be to represent it as two separate problems. *) If the amount of variable a is zero, then the amount of variable b is not restricted. -- Michael henne...@web.cs.ndsu.nodak.edu Pessimist: The glass is half empty. Optimist: The glass is half full. Engineer: The glass is twice as big as it needs to be. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Implementing conditional amount constraints using binary variables
Hi Xypron Perfect- this works. How did you come up with that notation? (I mean, except for experience :) ) Thanks Kretch On Wed, Jun 3, 2009 at 1:24 PM, Xypron xypron.g...@gmx.de wrote: Hello Yaron, param M := 1000; var a, =0, = M; var b, =0, = M; var x, binary; minimize opt: a - .3 * b; s.t. c0: a = x * M; s.t. c1: a - b = ( 1 - x ) * M; s.t. c2: b - a = ( 1 - x ) * M; solve; display a, b, x; end; Best regards Xypron Yaron Kretchmer wrote: Both a and b can be bounded by a large M. So let me reformulate my problem: 0 = a = M if a 0 : a=b if a=0 : 0=b=M Thanks Kretch ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Implementing conditional amount constraints using binary variables
Hi All. I would like to implement the following condition on two variables: *) If the amount of variable *a* is greater than 0, then the amount of variable *b* needs to be equal to that of a. *) If the amount of variable a is zero, then the amount of variable b is not restricted. I have a hunch this can be done with binary helper variables *a_bin,b_bin *which describe if a0 and b0, but I can't find a way of describing the relationship. Any insights welcome Kretch ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] mipgap accuracy and distance from optimal result
Greetings I'm curious about the results glpsol displays during integer optimization- What is the relationship (if any) between the percentage displayed, and the distance of the result from the optimal. So, for instance, if during MIP optimization I see this line * 1285: mip = 1.825885747e+000 = 1.667684907e+000 8.7% (74; 1728)* * * Is there a relationship between the 8.7% number and the distance between the current best solution(1.825...) and the optimum? Thanks much Kretch ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] mipgap accuracy and distance from optimal result
Great- thanks Andrew. Kretch On Mon, Apr 27, 2009 at 10:25 AM, Andrew Makhorin m...@gnu.org wrote: I #39;m curious about the results glpsol displays during integer optimization- What is the relationship (if any) between the percentage displayed, and the distance of the result from the optimal. So, for instance, if during MIP optimization I see this line 1285: mip = 1.825885747e+000 = 1.667684907e+000 8.7% (74; 1728) Is there a relationship between the 8.7% number and the distance between the current best solution(1.825...) and the optimum? The percentage says that the current objective value 1.825885747e+000 cannot decrease (or increase, in case of maximization) more than on 8.7% of 1.825885747e+000 ~= 0.159. This means the same that the optimal solution cannot be better than 1.667684907e+000, but expressed in %%. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] how to make matrix multiply with mathprog
Xypron- Any thoughts on how to how to model sparse matrix multiplication? this is usually with linked lists, but I'm sure that there's a smart way to use sets to do the modeling Thanks kretch On Tue, Feb 24, 2009 at 10:29 AM, xypron xypron.g...@gmx.de wrote: Hello! hhb83 wrote: I still could not work it out. Here, the Up,i is var, so should I take the Xp,i as param or var? If param, it always said expression following := has invalid type. And if I define it as var, and take the formulation as constraint like this: s.t. position{i in I, j in J, m in K}: X[i,j,m] = if i==1 then X0[j,m] else sum{k in K} A[m,k]*X[i-1,j,k] + B[m,k]*U[i-1,j,k]; you can find a working example below. Best regards Xypron # hhb83: how to make matrix multiply with mathprog set I := {1..9}; set J := {1..3}; set K := {1..3}; set M := {1..3}; param A{j in J, k in K}; param B{j in J, k in K}; param X0{j in J, k in K}; param U{i in I, j in J, k in K}; param X{i in I, j in J, m in M} := if i==1 then X0[j,m] else sum{k in K} ( A[m,k]*X[i-1,j,k] + B[m,k]*U[i-1,j,k] ); display X; data; param A: 1 2 3 := 1 1 2 3 2 4 5 6 3 7 8 9; param B: 1 2 3 := 1 1 2 3 2 4 5 6 3 7 8 9; param X0: 1 2 3 := 1 1 2 3 2 4 5 6 3 7 8 9; param U:= [1,*,*]: 1 2 3 := 1 1 2 3 2 4 5 6 3 7 8 9 [2,*,*]: 1 2 3 := 1 1 2 3 2 4 5 6 3 7 8 9 [3,*,*]: 1 2 3 := 1 1 2 3 2 4 5 6 3 7 8 9 [4,*,*]: 1 2 3 := 1 1 2 3 2 4 5 6 3 7 8 9 [5,*,*]: 1 2 3 := 1 1 2 3 2 4 5 6 3 7 8 9 [6,*,*]: 1 2 3 := 1 1 2 3 2 4 5 6 3 7 8 9 [7,*,*]: 1 2 3 := 1 1 2 3 2 4 5 6 3 7 8 9 [8,*,*]: 1 2 3 := 1 1 2 3 2 4 5 6 3 7 8 9 [9,*,*]: 1 2 3 := 1 1 2 3 2 4 5 6 3 7 8 9; end; -- View this message in context: http://www.nabble.com/how-to-make-matrix-multiply-with-mathprog-tp22077225p22187619.html Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] The good enough set covering problem
Thank you Andrew- I implemented your advice and it works fine. Regarding the problem size- are we talking about memory limitations? (I'll be using a 64bit machine with 32G RAM) Thanks again Kretch On Mon, Feb 9, 2009 at 11:13 AM, Andrew Makhorin m...@gnu.org wrote: I have a problem to solve at work which at best can be described as a good enough set covering problem. I #39;m appreciate the forum #39;s advice on how to tackle it. Coming from an engineering background, my nomenclature may be deficient- my apologies for that. So here goes: *) As with a regular set covering problem, I have a large domain ( up to 600K elements) which should be covered by a small set of groups (out of a maximum of about 1000 different groups). Please note that your problem may be hard for glpk due to its size. The good enough part is that it is not mandatory to cover the entire domain - we just need to cover most of the domain (most is defined as a percentage of the number of elements in the domain, and given as a parameter to the problem). *) I came up with a formulation of the classic set covering problem (enclosed) , but am struggling on how to convert it to a good enough covering problem. You need to relax the covering constraints. For example: s.t. covers{m in Ys}: sum{r in Z} A[r,m]*Route[r] = z[m]; s.t. foo: sum{m in Ys}: z[m] = percentage * card(Ys); where z[m] is a binary variable: z[m] = 1, if set m is covered, and 0 otherwise. *) Also, what command-line options are recommended for solving set covering problems? Are there any gotchas I should be aware of (except for set covering being NP complete? (^_^) ) ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] The good enough set covering problem
Got it. What influences the runtime - the number of sets, or the size of the domain? The reason I'm asking is that it's pretty easy to break the domain up into smaller domains, find good coverages for each of the smaller domains, then take a union of all the resulting minimum sets. Optimality is not a requirement here, just a good enough solution. Regards Kretch On Mon, Feb 9, 2009 at 11:47 AM, Andrew Makhorin m...@gnu.org wrote: Regarding the problem size- are we talking about memory limitations? (I #39;ll be using a 64bit machine with 32G RAM) No. The glpk mip solver may take too long time to solve your problem to optimality. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] [annonce] ffi-glpk extension demonstrator for jruby
Maurice- Will that work with Ruby MRI as well? Thanks Yaron On Tue, Jan 27, 2009 at 12:16 PM, Diamantini Maurice maurice.diamant...@gmail.com wrote: Bonjour à tous, I'm trying to test a new extension provide with jruby which allows to write a binding for a C library directly in ruby without writing a C line of code. This (ffi) extension is now part of the standard Jruby version. That allows to use mixing of java library (like choco constraint solver), C extensions (like glpk) directly in (j)ruby code. As Pierre asked (on the Glpk list) for a java or other binding for Glpk, I write this pseudo-annonce although ffi-glpk is just a demonstrator for now. But it allows to write the glpk documentation minimal example in **full (j)ruby** code! The demonstrator is available at : http://www.ensta.fr/~diam/ruby/online/pub/http://www.ensta.fr/%7Ediam/ruby/online/pub/ The code provided is the mimimum for writing the glpk doc mini example in ruby. Hope this help, -- Maurice Diamantini Here is the README : == ## what is it This directory contains a test exemple to validate Glpk interface to (J)Ruby thanks to the new ffi Ruby package. - Glpk is the Gnu Library tookit for Linear Programming written in C by Andrew Makhorin, http://www.gnu.org/software/glpk/ - Ruby is a wonderfull true objet oriented programming scripting language written in C - JRuby is a Ruby (100% compatible) version written in Java and fully supported by Sun. It is also fully integrated with the java world and is as fast as the new native Ruby-1.9 version http://jruby.org/ - FFI is a new package which allow to write 100% Ruby interface to C library!! FFI is currently fully integrated with JRuby language. and can be installed for Ruby native language. http://kenai.com/projects/ruby-ffi/pages/Home ## The provided exemple allow to solve the following problem : max z = 10x1 + 6x2 + 4x3 s.c. x1 + x2 + x3 = 100 10x1 + 4x2 + 5x3 = 600 2x1 + 2x2 + 6x3 = 300 x1 = 0 x2 = 0 x3 = 0 This directory contains : - a file miniglpk.c which is exactly the glpk exemple provide with the glpk documentation. You should be able to test this programme to make sure glpk is installed on your system, but a compilator is not required for using glpk from (J)ruby - a file ffi-glpk.rb wich contains the minimum for writing the low level API used in the tutorial example, - the file mini_glpk.rb which is the the ruby version of the tutorial. ## Execution of the test the C version For compiling and running the C exemple, you should set two environment variables : - GLPK_LIB should be set the path were the library file libglpk.so or libglpk.dylib is located, For sample export GLPK_LIB=/usr/local/lib - GLPK_INCLUDE should be set the path were the library file glpk.h is located For sample export GLPK_LIB=/usr/local/lib Then compile by: gcc -I$GLPK_INCLUDE -L$GLPK_LIB -l glpk -o mini_glpk mini_glpk.c and run by: ./mini_glpk The following result should appear: * 0: obj = 0.0e+00 infeas = 0.000e+00 (0) * 2: obj = 7.3e+02 infeas = 0.000e+00 (0) OPTIMAL SOLUTION FOUND z = 733.333; x1 = 33.; x2 = 66.6667; x3 = 0 ## Execution the jruby test You should have the last jruby version (jruby-1.6) which contains FFI out of the box, or ruby and install ffi with gem install ffi (not tested) Also, the glpk lib should be discover aumoticaly on osx leopard or recent linux distrib, but for now, you can specify the path path (i.e. bu using the previous GLPK_LIB variable. See the start ffi-glpk.rb if you have problems then run ./mini_glpk.rb It's all ! ## Remark about the ffi-glpk.rb interface file This kind of file could become the low level interface to the glpk library. It seems that the FFI community converge to the idea that there should be one standard **low** level interface to a C library. It is essentialy a sort of mapping of the include file and should be easy to maintain (ideally automically generated from the include file). Then it could exist several higher level API to make this interface more Object Oriented ou more Ruby frendly. ## ./ ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] How to analyze which constraint (or combination of constraints) is causing the model to become unsolvable?
Great idea Ali - Thanks. Would the following work : *) Create companion binary variables to the xp,xn debugging variables, called bxp,bxn. *) Each companion variable denotes whether the original debugging variables are bigger than zero. *) Try to minimize the sum of bxp + bxn. That way , we would get the smallest subset of violating constraints, which might help ease debugging. Do you think that makes sense? Thanks Kretch On Wed, Jan 14, 2009 at 1:07 PM, Ali Baharev ali.baha...@gmail.com wrote: Hello, I am afraid it is ambiguous which constraints are causing the trouble. You could probably try the following. Introduce two new continuous variables xp = 0 and xn = 0 to each constraint. For example: x1 + 2 x2 = 3 after introducing the variables x1 + 2 x2 + (xp - xn) = 3 and change the objective function: minimize: sum xp + sum xn This problem must have a solution. For those constraints which are violated the corresponding xp or xn will not equal zero. Unfortunately it may turn out that all constraints are violated... If you are lucky there will be only a few constraints with non-zero xp and xn variables. Good luck, Ali ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] How to analyze which constraint (or combination of constraints) is causing the model to become unsolvable?
Thanks Ali. If finding the minimal set of conflicting constraints is a well known problem, are there any solutions provided in GLPK for it? Or is this outside of the scope of GLPK? And if it is, what other tools could be used to find out the minimal set? Regards Kretch On Wed, Jan 14, 2009 at 2:34 PM, Ali Baharev ali.baha...@gmail.com wrote: Do you think that makes sense? If i were you i would try the proposal without binary variables. Maybe it turns out that there is only one violated constraint. *) Each companion variable denotes whether the original debugging variables are bigger than zero. Well, i do not know anything about your problem but i am afraid it would result in a big M formulation. If you have thousands of constraints, it would yield thousands of new binary variables. Please do not forget the fact that the conflicting constraints are ambiguous. Please also keep in mind that we are re-inventing the wheel, i.e. finding the minimal set of conflicting constraints is a well-known problem. Good luck, Ali ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] How to analyze which constraint (or combination of constraints) is causing the model to become unsolvable?
Thanks much Lou! I'll do that On Wed, Jan 14, 2009 at 5:04 PM, Lou Hafer l...@cs.sfu.ca wrote: Yaron, Try http://www.sce.carleton.ca/faculty/chinneck/minosiis.html. You might want to contact John directly, this is one of his interests. Lou ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Splitting one model into several files
Thanks Oscar- I managed to get this to work as you advised. Regards Kretch On Thu, Jan 8, 2009 at 2:42 AM, Oscar Gustafsson osc...@isy.liu.se wrote: Hi Yaron! As far as I know glpsol only deals with one model. Since a rather recent version it can multiple data files though. The solution would probably be to use some sort of file system concatenation of the files, which would depend on the operating system you are using. (for linux: cat file1.mod file2.mod ... allfiles.mod) Regards Oscar ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Splitting one model into several files
Hi There. I'm working on a complex model in mathprog, and would like to split into several files which will be later on combined by a top-level model - how can I do that i.e. how do I include portions of a model from the top level? any examples would be most welcome. Regards Yaron ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Displaying non-zero values only
Hi All. I'm solving a diet problem, and would like to display only the values of foods which have non-zero quantities. I'm using tables to formulate both input and output, so any information which would enable me to write just the non-zero variables to a table would be most appreciated. Thanks Yaron ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Displaying non-zero values only
This works- perfect! Thanks Xypron Regards Yaron On Sat, Oct 25, 2008 at 8:52 PM, xypron [EMAIL PROTECTED] wrote: Hello Yaron, set I := 1..8; set J := 1..8; set A dimen 3 := { (3, 4, 2), (7, 8, 1) }; var v{i in I, j in J}, = 0; minimize sum : sum{i in I, j in J} v[i,j]; s.t. constraint {(i,j,x) in A}: v[i,j] = x; solve; table result { i in I, j in J : v[i,j] 0 } OUT 'iODBC' 'DSN=glpk;UID=glpk;PWD=gnu' 'DROP TABLE IF EXISTS yaron_result' 'CREATE TABLE yaron_result (i INT, j INT, v INT )' 'yaron_result' : i, j, v[i,j]; printf Non-zero results\n; for { i in I, j in J : v[i,j] 0 } printf v[%d, %d] = %d\n, i, j, v[i,j]; end; Best regards Xypron kretch wrote: Hi All. I'm solving a diet problem, and would like to display only the values of foods which have non-zero quantities. I'm using tables to formulate both input and output, so any information which would enable me to write just the non-zero variables to a table would be most appreciated. Thanks Yaron -- View this message in context: http://www.nabble.com/Displaying-non-zero-values-only-tp20163644p20163877.html Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Sparse matrix representation in GLPK?
Hi There For a VLSI application, I'm trying to solve a variant of the warehouse location problem. My problem stems from the fact that there are ~5K customers and warehouses, which translates into a 5K by 5K matrix. This leads me to wonder whether GLPK supports some sort of sparse matrix representation, one which support mathprog matrix multiplcations etc. ? Thanks Yaron ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] How to generate glpk DLL with visuall C++ 2008 express edition?
Hi All I'm trying to compile glpk as a DLL so I can integrate it with Ruby. Can anyone share experiences of doing that? Thanks Yaron ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] glpk on a machine with little memory
Hi All I have a large model which I want to run on a machine with small amount of memory (80M), which leads to xmalloc errors. Is there a way of capping memory consumption (i.e. by caching to disk)? I realize this would impact performance. Thanks Yaron ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] complex constraints in glpk
Hi all Is it possible to capture constraints of the form max(a,b) - min(c,d) X or max(e,f) - min(g,h) Y in glpk? Thanks much Yaron ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] 2D packing problem glpk?
Hi There Has anyone used glpk to solve a 2D packing problem? Any pointers/code would be most welcome Thanks! Yaron ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Compiling results: Clueless
Use PERL's Excel package- you can split the results into multiple pages, each with 64K lines Good luck Yaron On 5/17/07, Andrew Makhorin [EMAIL PROTECTED] wrote: Am really impressed with GnuMathProg - I prepare the datafile through and excel interface I slapped together and outputs with another excel workbook. However, my results files are getting so big that excel bombs (I am over 65000 lines) is there an easy way of sorting and sticking the results into some database? If there is please let me know. Glpk has no database/spreadsheet interface. However, you can easily write it using glpk api routines, if necessary. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk