DOC PREVIEW
A CASE STUDY IN LARGE-SCALE INTERACTIVE OPTIMIZATION

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

A CASE STUDY IN LARGE-SCALE INTERACTIVE OPTIMIZATIONMarkus Chimani∗Institute of Computer Graphics and AlgorithmsVienna University of Technologyemail: [email protected] LeshMitsubishi Electric Research Laboratories201 Broadway, Cambridge, MA, 02139email: [email protected] Mitzenmacher∗†Computer Science DepartmentHarvard Universityemail: [email protected] SidnerMitsubishi Electric Research Laboratories201 Broadway, Cambridge, MA, 02139email: [email protected] TanakaInformation Tech. R&D CenterMitsubishi Electric, Japanemail: [email protected] describe lessons learned in developing a program for in-teractive optimization of large airlift scheduling problems.While for small problems one can create a visualization thatboth shows a complete solution and is editable at the sametime, with large problems, such visualizations provide toohigh a level of aggregation and cannot display the detailnecessary for interaction. We explain how this changesthe interactive process, and the implications for our design,such as the need for automatic focusing on parts on theproblem to ease optimization. An additional problem re-quirement was that the user be enabled to change the prob-lem specification (such as delivery deadlines). As a fur-ther contribution, we provide a specialized repair algorithmthat aims at generating a valid solution after such changes,while introducing as few changes as necessary.KEY WORDSPlanning and Scheduling, Human Computer Interfaces,Human-Guided Tabu-Search, Information Visualization,Minimize Disruption1 IntroductionWhile there has been a considerable amount of work onautomatic optimization systems, very little work has ad-dressed how people can best use or interact with them. Aswith many technologies, the quality of the interface for op-timization systems is often the bottleneck for the real-worlduse of the system. For example, the work we report on hereoriginated because a potential customer is currently solvinglarge airlift scheduling problems manually. The probleminvolves using a given set of airplanes to satisfy a given setof delivery requests using a given set of airports, coveringthe flight operations of a complete year’s cycle. A previousfully automatic system was rejected because the customerwanted more control.The experts who craft the solutions manually have∗This work was done while visiting Mitsubishi Electric Research Lab-oratories.†Supported in part by NSF CAREER Grant CCR-9983832 and an Al-fred P. Sloan Research Fellowship.knowledge which is not fully captured in the problem spec-ification. Thus, the schedules produced by automatic algo-rithms may not be optimal with respect to all the constraintsand preferences known to the experts. This knowledge maybe difficult for the experts to articulate even in natural lan-guage, let alone reduce to a form that can be input to anautomatic optimization algorithm.Research in interactive, or human-in-the-loop, opti-mization systems directly addresses the question of howpeople can effectively interact with optimization systems.The aim is to utilize the users’ knowledge to steer thesearch algorithm towards good solutions, aswell as to makeher understand and trust the solution.In this paper, we report on lessons learned by applyingthe Human-Guided Search (HuGS) framework and toolkit[1, 7, 6] to the above airlift schedule problem. Most pre-vious work on interactive optimization, including our own,has been on small, academic problems. The goals of thispaper are to demonstrate that many advantages of HuGS forthese problems transfer well to large, complex applicationsas well as to present some novel techniques and conceptswe needed to introduce for this application.We can briefly summarize our findings as follows. Aswith previous HuGS applications:P1 Users decide how to invest computational resources,e.g., they can focus an optimization algorithm on im-proving a chosen subset of the current schedule.P2 Users can employ powerful optimization algorithmswhile manually editing and refining the current sched-ule to respect their real-world knowledge.P3 Users can temporarily introduce infeasibilites into thecurrent schedule while finding better schedules.However, we found that large problems require a dif-ferent pattern of interaction than small ones. For both smalland large problems, the user’s activity can be classifiedinto three categories: inspection, modification, and user-controlled reoptimization of the current solution. (We de-scribe these phases in more detail below.) For small prob-lems, the user can constantly and quickly shift betweenthese phases. It is easy for the user to visualize and controlwhat portion of the solution the optimization is currentlyfocused on. If the optimization algorithm changes the so-lution in an undesirable way, the user can easily detect thisproblem, backtrack to a previous solution, change the focusto prevent the undesirable change, and re-invoke the opti-mization. Furthermore, in academic problems the problemspecification remains constant during the entire session. Incontrast, for our current application we needed to develop:N1 Heuristics to help control the focus of the optimizationalgorithm as the user navigates to different views ofthe schedule because it is difficult to control the focuswhen the current complete schedule can not be viewedin detail on one screen.N2 Methods for allowing the user to change the problemspecification during the session, e.g., to add deliveryrequests or change deadlines. These changes oftenmake the current schedule infeasible.N3 A special mode to support refining near-acceptableschedules. In this mode, after the user searchesthrough the schedule for errors (with respect to herreal-world knowledge), she wishes to minimize thenumber of changes made by the optimization algo-rithm in the process of fixing these errors. Minimizingchanges frees the user from re-inspecting much of theschedule.2 BackgroundInteractive systems that leverage the strengths of both hu-mans and computers must distribute the work involved inthe optimization task among these two participants. Ex-isting systems have implemented this division of labor invarious ways. In some interactive systems, the users canonly indirectly affect the solutions to the current problem.For example, in interactive evolution the computergenerates solutions via biologically inspired methods, andthe user selects which solutions will be used to generatenovel


A CASE STUDY IN LARGE-SCALE INTERACTIVE OPTIMIZATION

Download A CASE STUDY IN LARGE-SCALE INTERACTIVE OPTIMIZATION
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view A CASE STUDY IN LARGE-SCALE INTERACTIVE OPTIMIZATION and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A CASE STUDY IN LARGE-SCALE INTERACTIVE OPTIMIZATION 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?