Re: intervals for integer programs "R. Baker Kearfott"  wrote: > Actually, what George suggests is a fairly widely-used technique in > global optimization, not confined to interval methods:  One replaces > a constrained minimization problem by another problem whose minimum > is less than or equal to the minimum of the original problem;  this > derived problem is called a "relaxation."  The solution to the > relaxation over a sub-region of the search region then provides a > lower bound over any global optimum constrained to that subregion. > At 06:00 AM 9/9/2004 -0500, George Corliss wrote: > >I cannot point you to references, but I can offer that one approach I > >suppose is considered well known in the community is to apply interval > >methods to the continuous problem.  When the interval of real numbers > >contains only one integer, snap to that integer.  You sort of run a > >continuous algorithm with a tolerance of 0.99. > >> I have recently become interested in interval methods as a means of solving > >> non-linear non-convex optimisation problems and I am looking to employ > them in > >> my own fields of work (traffic and transport engineering and econometrics). > >>  > >> However, part of the problems I'd like to work on with intervals are actually > >> integer programs and I do not have, so far, a clear grasp of how applicable > >> are interval methods in this case. To apply interval methods to MINLPs, one just uses the general recipes from continuous global optimization, with a few modifications to take care of integer constraints: 1. When splitting an interval [a,b] for an integer variable, instead of splitting at, say, the midpoint c one splits at the two integers c_1 and c_2 closest to c, and gets the smaller halves [a,c_1] and [c_2,b]. 2. When using optimality conditions in an interval Newton method, one needs to treat all integer variables as parameters, not as variables; otherwise one might lose solutions. 3. One can use many standard techniques from MIP to add useful cutting planes. You may wish to read Ivo Nowak's work on MINLP: http://www-iam.mathematik.hu-berlin.de/~ivo/minlp.html His work contains a lot of relevant material, although he uses intervals only in a heuristic, nonrigorous fashion. Arnold Neumaier