Search Algorithms for Discrete Optimization Problems Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar


A discrete optimization problem can be expressed as a tuple (S, f). The set is a finite or countably infinite set of all solutions that satisfy specified constraints



Yüklə 0,99 Mb.
səhifə2/23
tarix26.12.2016
ölçüsü0,99 Mb.
#3369
1   2   3   4   5   6   7   8   9   ...   23

A discrete optimization problem can be expressed as a tuple (S, f). The set is a finite or countably infinite set of all solutions that satisfy specified constraints.

  • The function f is the cost function that maps each element in set S onto the set of real numbers R.

  • The objective of a DOP is to find a feasible solution xopt, such that f(xopt) ≤ f(x) for all x S.

  • A number of diverse problems such as VLSI layouts, robot motion planning, test pattern generation, and facility location can be formulated as DOPs.



  • Discrete Optimization: Example

    • In the 0/1 integer-linear-programming problem, we are given an m×n matrix A, an m×1 vector b, and an n×1 vector c.

    • The objective is to determine an n×1 vector whose elements can take on only the value 0 or 1.


    • Yüklə 0,99 Mb.

      Dostları ilə paylaş:
    1   2   3   4   5   6   7   8   9   ...   23




    Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
    rəhbərliyinə müraciət

    gir | qeydiyyatdan keç
        Ana səhifə


    yükləyin