TR2004-113

A Case Study in Large-Scale Interactive Optimization


    •  Markus Chimani, Neal Lesh, Michael Mitzenmacher, Candy Sidner, Hidetoshi Tanaka, "A Case Study in Large-Scale Interactive Optimization", Tech. Rep. TR2004-113, Mitsubishi Electric Research Laboratories, Cambridge, MA, September 2004.
      BibTeX Download PDF
      • @techreport{MERL_TR2004-113,
      • author = {Markus Chimani and Neal Lesh and Michael Mitzenmacher and Candy Sidner and Hidetoshi Tanaka},
      • title = {A Case Study in Large-Scale Interactive Optimization},
      • institution = {MERL - Mitsubishi Electric Research Laboratories},
      • address = {Cambridge, MA 02139},
      • number = {TR2004-113},
      • month = sep,
      • year = 2004,
      • url = {https://www.merl.com/publications/TR2004-113/}
      • }

We describe lessons learned in developing a program for interactive optimization of large airlift scheduling problems. While for small problems one can create a visualization that both shows a complete solution and is editable at the same time, with large problems, such as visualizations provide too high a level of aggregation and cannot display the detail necessary for interaction. We explain how this changes the interactive process, and the implications for our design, such as the need for automatic focusing on parts on the problem to ease optimization. An additional problem requirement was that the user be enabled to change the problem specification (such as delivery deadlines). As a further contribution, we provide a specialized repair algorithm that aims at generating a valid solution after such changes, while introducing as few changes as necessary.