Optimization Techniques II

TD15.1 A General Purpose Simulated Annealing Algorithm for Integer Linear Programming

• Seksan Kiatsupaibul; University of Michigan, Dept. of IOE, 2170 Cram Pl., #14, Ann Arbor, MI 48105; centered@engin.umich.edu
• Robert L. Smith; University of Michigan, Dept. of IOE, Ann Arbor, MI 48109; rlsmith@umich.edu,, http://www-personal.engin.umich.edu/~rlsmith

We propose a Markov chain sampling algorithm to generate points uniformly distributed on an arbitrary bounded region of a high dimensional integer lattice. We use this to construct a general purpose SA algorithm for integer LPs that converges to the global optimum with probability one.

TD15.2 Computational Testing on a Modified Descent Method

• Li-Wen Chen; National Cheng Kung University, Dept. of Civil Eng., 1 Da-Shua Rd., Tainan, 701 , Taiwan; idofmy.bbs@bbs.civil.ncku.edu.tw
• Yusin Lee; National Cheng Kung University, PO Box 7-206, Tainan, 701 , Taiwan; yusin@mail.ncku.edu.tw

The simple descent method get trapped at the first local minimum encountered and it is commonly believed that the performance will not come close to those by more elaborate heuristics. Computational testing shows that a slightly modified version of the descent method can yield results comparable to TS and SA.

TD15.3 Generation Techniques for Strong Covering Units of One-Dimensional Tilings

• Connie G. Fournelle; University of Kentucky, 715 Patterson Office Tower, Lexington, KY 40506-0027; connieg@ms.uky.edu
• Carl W. Lee; University of Kentucky, 715 Patterson Office Tower, Lexington, KY 40506-0027; lee@ms.uky.edu,, http://www.ms.uky.edu/~lee

A strong covering unit of a tiling J is a cluster of tiles which can cover any subfacet star appearing in J. We give techniques for generating strong covering units for one-dimensional aperiodic tilings based on examination of the window used to construct the tiling under the projection method.

TD15.4 Layout of Two-Dimensional Irregular Shapes using Heuristics

• Rym M'Hallah; Institut Superieur de Gestion Sousse, BP 763, Sousse, 4000 , Tunisia; rym.mhallah@irsit.rnrt.tn
• Ahlem Bouziri; IRSIT, PB 212 Cite Mahrajene, Tunis, 1082 , Tunisia; ahlem.bouziri@irsit.rnrt.tn

We present a new heuristic for the layout of irregular 2-dimensional shapes used in the garment industry. The heuristic is very simple and exceptionally fast. Its application to real cases from the garment industry has yielded good results, comparable to those obtained by human markers.

TD15.5 MProbe: What's in your Mathematical Program?

• John W. Chinneck; Carleton University, Systems & Computer Eng., 1125 Colonel By Dr., Ottawa, Ontario, K1S 5B6 , Canada; chinneck@sce.carleton.ca,, http://www.sce.carleton.ca/faculty/chinneck.html

Sometimes you need to know more about your mathematical program than solvers will tell you. What are the shapes of the nonlinear functions and constrained region? How effective are the constraints? Which constraints are redundant. A general analysis tool such as MProbe can answer questions such as these. See http://www.sce.carleton.ca/faculty/chinneck/mprobe.html.