Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. EPFL thesis
  4. On the generation of locally consistent solution spaces in mixed dynamic constraint problems
 
doctoral thesis

On the generation of locally consistent solution spaces in mixed dynamic constraint problems

Gelle, Esther
1998

The development of industrial products such as cars, mechanical tools as well as civil engineering structures includes the task of identifying components and arranging them in a product structure. This task is commonly called configuration. It can be formalized as a constraint satisfaction problem (CSP), which provides a concise mathematical model for combinatorial tasks. A CSP is defined by the variables of interest, each with a domain of possible values, and a set of constraints which restrict the allowed value combinations. The formulation of a configuration task as a CSP gives flexibility required to apply complex optimization criteria during search which often cannot be expressed by a single utility function. Solving a CSP corresponds to finding a consistent assignment to the variables that satisfies all constraints. Solution methods for CSPs encompass consistency and search techniques. Consistency techniques are preprocessing methods which remove inconsistent value combinations before search thus reducing the search space; Furthermore, a dynamic CSP model (DCSP) makes possible the introduction of new variables and constraints during problem resolution. However, CSP techniques have been weak for handling mixed (discrete-continuous) as well as dynamic problems. In this thesis, I present a new algorithm for solving DCSPs with mixed, continuous and discrete, constraints. It isolates and approximates the solution sets of a DCSP by local consistency techniques. To this purpose, local consistency techniques for continuous constraints had to be enhanced and integrated with existing discrete local consistency methods. Some advantages of this algorithm are: It can solve problems in which the existence of a variable depends on a decision taken over a continuous value domain. Different locally consistent solution spaces can be compared, thus providing additional information for decision making. Local consistency techniques are also applied to search for a single solution within the resulting locally consistent solution spaces. These techniques are particularly efficient for searching in continuous domains. The algorithm proposed is applied to a number of different problems such as conceptual bridge design, design of steel structures, configuration of trains, and industrial mixers.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

EPFL_TH1826.pdf

Access type

openaccess

Size

3.2 MB

Format

Adobe PDF

Checksum (MD5)

7a013ec05711c24faea61adc2800a410

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés