RE: [Help-glpk] Use of LP for experimental trials

[dhdoyle]

Tabu Search seems an interesting alternative.

Dan 

-----Original Message-----
From: Brady Hunsaker [mailto:address@hidden 
Sent: Thursday, April 20, 2006 2:46 PM
To: dhdoyle
Cc: address@hidden
Subject: Re: [Help-glpk] Use of LP for experimental trials

address@hidden 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
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk


-- 
Brady Hunsaker
Assistant Professor
Industrial Engineering
University of Pittsburgh
http://www.engr.pitt.edu/hunsaker/