home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / 18618 < prev    next >
Encoding:
Internet Message Format  |  1993-01-21  |  1.9 KB
  1. Path: sparky!uunet!think.com!mintaka.lcs.mit.edu!ai-lab!great-grain!mdlm
  2. From: mdlm@great-grain.ai.mit.edu (Michael De-la-Maza)
  3. Newsgroups: sci.math
  4. Subject: Novice ?: Availability of LP programs and absolute value tricks
  5. Date: 21 Jan 1993 22:11:00 GMT
  6. Organization: MIT Artificial Intelligence Lab
  7. Lines: 47
  8. Sender: mdlm@great-grain (Michael De-la-Maza)
  9. Distribution: world
  10. Message-ID: <1jn71kINNn04@life.ai.mit.edu>
  11. NNTP-Posting-Host: great-grain.ai.mit.edu
  12.  
  13. I have a couple of questions on the subject of linear (and slightly
  14. nonlinear) programming.
  15.  
  16. 1. Does anyone know where to get free linear programming programs?  
  17.    An ftp site would be best.   
  18.  
  19. 2. I know that there are specific results for the case in which the
  20.    function to be maximized is quadratic.  Are there specific results
  21.    for the case in which the constraints can be quadratic?  Any programs
  22.    that implement these (quadratic)^2 algorithms?
  23.  
  24. 3. Does anyone know of a reference that summarizes tricks for getting 
  25.    rid of absolute values or know of any such tricks?
  26.  
  27.    The most obvious trick is:
  28.  
  29.     |x - y| < a   <=>  (x - y) < a   _and_  (y - x) < a
  30.  
  31.    But this does not generalize to the greater than case:
  32.     
  33.     |x - y| > a   <=>  (x - y) < a   _or_   (y - x) < a 
  34.    
  35.    However,
  36.  
  37.     |x - y| > a <=> -|x - y| < -a
  38.    
  39.    So after multiplying by -1 the greater than case reduces to the
  40.    less than case.
  41.  
  42.    I would like tricks for more complicated absolute value forms, e.g.,
  43.  
  44.     |x1 - x2| + |y1 - y2| < a 
  45.  
  46.    The obvious trick (which is a simple generalization of the 
  47.    |x - y| < a trick) produces a set of equations that is 
  48.    exponential in the number of absolute value expressions, e.g.,
  49.  
  50.     |x1 - x2| + |y1 - y2| < a   <=>
  51.  
  52.      x1 - x2 + y1 - y2 < a     and
  53.      x2 - x1 + y1 - y2 < a     and
  54.      x1 - x2 + y2 - y1 < a     and
  55.      x2 - x1 + y2 - y1 < a     
  56.  
  57.  
  58. Since this is a novice question, please reply to me directly, so as not
  59. to clutter up the net.                
  60.