Optimization Online


Enriching Solutions to Combinatorial Problems via Solution Engineering

Petit Thierry(Thierry.Petit***at***imt-atlantique.fr)
Trapp Andrew(atrapp***at***wpi.edu)

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, as well as problem-specific desires that are apriori unknown, or at least difficult to articulate, for the end-user. We propose a general framework that can generate a set of of multiple (near-)optimal, diverse solutions for problems of a combinatorial nature, that are further infused with user-selected quality notions. 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 constraint programming and mathematical programming technologies, and 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 which otherwise might remain undiscovered.

Keywords: mathematical programming, constraint programming, diversity, quality notions, solution generation framework

Category 1: Combinatorial Optimization

Citation: Technical Report, October 2017 Worcester Polytechnic Institute Robert A. Foisie Business School 100 Institute Road Worcester, MA 01609

Download: [PDF]

Entry Submitted: 10/05/2017
Entry Accepted: 10/07/2017
Entry Last Modified: 10/05/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society