Enriching Solutions to Combinatorial Problems via Solution Engineering

Thierry Petit () and Andrew C. Trapp ()
Additional contact information
Thierry Petit: LS2N (TASC), IMT Atlantique (DAPI), CNRS, 44307 Nantes, France; Robert A. Foisie Business School, Worcester Polytechnic Institute, Worcester, Massachusetts 01609
Andrew C. Trapp: Robert A. Foisie Business School, Worcester Polytechnic Institute, Worcester, Massachusetts 01609

INFORMS Journal on Computing, 2019, vol. 31, issue 3, 429–444

Abstract: Existing approaches to identify multiple solutions to combinatorial problems in practice are at best limited in their ability to simultaneously incorporate both diversity among generated solutions and problem-specific desires that may only be discovered or articulated by the user after further analysis of solver output. We propose a general framework for problems of a combinatorial nature that can generate a set of of multiple (near-)optimal, diverse solutions that are further infused with desirable features. We call our approach solution engineering . A key novelty is that desirable solution properties need not be explicitly modeled in advance. We customize the framework to both the mathematical programming and constraint programming technologies, and we subsequently demonstrate its practicality by implementing and then conducting computational experiments on existing test instances from the literature. Our computational results confirm the very real possibility of generating sets of solutions infused with features that might otherwise remain undiscovered.

Keywords: mathematical programming; constraint programming; diversity; quality notions; solution generation framework (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0855 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:3:p:429-444

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().