Optimization Online


Generation techniques for linear and integer programming instances with controllable properties

Simon Bowly (simon.bowly***at***monash.edu)
Kate Smith-Miles (kate.smith-smiles***at***monash.edu)
Davaatseren Baatar (davaatseren.batar***at***monash.edu)
Hans Mittelmann (mittelmann***at***asu.edu)

Abstract: This paper addresses the problem of generating synthetic test cases for experimentation in linear and mixed integer programming. We propose a generation framework to shift instance generation and search processes to an alternative encoded space. The framework is applied to produce a generator for feasible bounded linear programming instances with controllable properties. We show that this method is capable of generating any feasible bounded linear program, and that random generation and search algorithms in this framework generate only instances with this property. Our results demonstrate that controlled random generation and instance space search using this method achieves feature diversity more e ectively than using a direct representation. Furthermore, local search algorithms in the encoded space are able to increase the diculty of generated instances for linear programming algorithms. This research opens further questions as to the suitability of various search algorithms for targeted instance design, convergence of search algorithms in instance space, and appropriate predictive features for LP and MIP algorithm performance.

Keywords: Linear programming, Mixed integer programming, Instance generation

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Optimization Software and Modeling Systems (Other )


Download: [PDF]

Entry Submitted: 04/22/2017
Entry Accepted: 04/24/2017
Entry Last Modified: 04/17/2018

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