Combinatorial Methods

TD31.1 An Integral Simplex Algorithm for Solving Combinatorial Optimization Problems Gerald L. Thompson --- Carnegie Mellon Univ., Grad. Sch. of IA, 5000 Forbes Ave., Pittsburgh, PA 15213-3890, (gt04@andrew.cmu.edu)

To solve a set partitioning problem, the local integral simplex¨ method starts with an all artificial basis and pivots on ones as¨ long as possible. If the exhibited integral solution is not optimal,¨ the global integral simplex method creates a subproblem search tree,¨ the solution to at least one of which is the global optimum for the¨ original problem.

TD31.2 Solving Striking Asset Allocation with Defender Suppression Problems Vincent Li, Guy L. Curry, E. Andrew Boyd --- TX A&M Univ., Dept. of IE, College Station, TX 77843-3131, (li@marvin.tamu.edu)

The strike force asset allocation problem with defender suppression¨ consists of grouping strike force assets into attack packages and¨ assigning these packages to targets and defensive assets so as to¨ maximize the strike force damage yield. An NLP formulation is¨ developed and transformed into an MIP problem. Computational¨ approaches and results are discussed.

TD31.3 Bicriteria Assignment Problem J. Teghem, E. L. Ulungu, D. Tuyttens --- Faculte Polytechnique De Mons, Rue De Houdain, 9, Mons, 7000 , Belgium (teghem@mathro.fpms.ac.be)

Our aim is to generate the complete set of efficient solutions,¨ supported and non-supported. We develop 2 exact methods and an¨ adaptation of the SA heuristic to the multicriteria framework.¨ Numerical experiments are made to compare the efficiency of the 3¨ procedures.