Tabu Search seems an interesting alternative. Dan
-----Original Message----- From: Brady Hunsaker [mailto:[EMAIL PROTECTED] Sent: Thursday, April 20, 2006 2:46 PM To: dhdoyle Cc: help-glpk@gnu.org Subject: Re: [Help-glpk] Use of LP for experimental trials [EMAIL PROTECTED] wrote: > Hi, > > I'd like to know if > I can use glpk to solve a problem where the solver in glpk would call > a function. I'm an engineer who no longer does any real coding. I > used simplex methods years back with good success on several types of problems. > I'm working to determine the best set of test conditions for a > semiconductor chip. These correspond to internal voltage levels and > delays. They are set as bits. There are a total of 55 bits, in 20 > variables for 3E16 combinations. I'd like to try a simplex type algo > that runs a point or trial in X dimensional space, evaluates the > results and selects the vectors for the next trial. Each trial takes 5 minutes. > As Andrew points out, this can't be modeled as an LP/MIP. I would recommend that you consider a local search approach, which is basically what you are outlining below. There is open-source software to do Tabu Search in Java called Open Tabu Search, available at COIN-OR (www.coin-or.org). That's one option for you. Other questions along this line might be best directed to the sci.op-research newsgroup. Brady > > > So the problem > is: > > > > 1) Must be evaluated > as an external function with the values passed in. The return is a > value to be minimized. In other words, there are no constraints or > known equation for the function. > > 2) Should be > efficient in trials, due to the 5 min per iteration (thus my interest > in Simplex over a genetic code) > > 3) I have to be able > to convert it to integer points > > 4) Each variable has > upper and lower limits expressed as 0-7 or 0-15. > > 5) The space has > local minima, so if it can bounce out great. However, I am just > looking for improvement over the current "optimum" not a global > solution. > > 6) I don't need to > evaluate the whole space at once, I can fix X variables and look for > improvements in the settings of 20-X variables. > > 7) A PERL shell > would set up the seed and track outputs. The glpk would be called and > in turn call the function which is really a chip tester. > > 8) The current > method employed is full matrix search on 1-3 variables at a time. > > > > Can glpk work for > this problem? If so which modules should I try and what mods to the code > do I need if any? Is there other software out there better suited to this > application? > > Thanks in advance, > > Dan > > > > > > ------------------------------------------------------------------------ > > Hi, > > I'd like to know if I can use glpk to solve a problem where the solver > in glpk would call a function. I'm an engineer who no longer does any > real coding. I used simplex methods years back with good success on > several types of problems. I'm working to determine the best set of > test conditions for a semiconductor chip. These correspond to internal > voltage levels and delays. They are set as bits. There are a total of > 55 bits, in 20 variables for 3E16 combinations. I'd like to try a > simplex type algo that runs a point or trial in X dimensional space, > evaluates the results and selects the vectors for the next trial. Each > trial takes 5 minutes. > > So the problem is: > > 1) Must be evaluated as an external function with the values passed in. > The return is a value to be minimized. In other words, there are no > constraints or known equation for the function. > 2) Should be efficient in trials, due to the 5 min per iteration (thus > my interest in Simplex over a genetic code) > 3) I have to be able to convert it to integer points > 4) Each variable has upper and lower limits expressed as 0-7 or 0-15. > 5) The space has local minima, so if it can bounce out great. However, > I am just looking for improvement over the current "optimum" not a > global solution. > 6) I don't need to evaluate the whole space at once, I can fix X > variables and look for improvements in the settings of 20-X variables. > 7) A PERL shell would set up the seed and track outputs. The glpk would > be called and in turn call the function which is really a chip tester. > 8) The current method employed is full matrix search on 1-3 variables at > a time. > > Can glpk work for this problem? If so which modules should I try and > what mods to the code do I need if any? Is there other software out > there better suited to this application? > > Thanks in advance, > Dan > > > ------------------------------------------------------------------------ > > _______________________________________________ > Help-glpk mailing list > Help-glpk@gnu.org > http://lists.gnu.org/mailman/listinfo/help-glpk -- Brady Hunsaker Assistant Professor Industrial Engineering University of Pittsburgh http://www.engr.pitt.edu/hunsaker/ _______________________________________________ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk