[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [Help-glpk] Use of LP for experimental trials
From: |
dhdoyle |
Subject: |
RE: [Help-glpk] Use of LP for experimental trials |
Date: |
Fri, 21 Apr 2006 11:06:34 +0400 |
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/