Scribd Logo
Upload

Welcome to Scribd!

  • 95 views

    MATP6620 Integer and Combinatorial Optimization

    Uploaded by

    Arya Chowdhury
    This document provides an introduction to integer and combinatorial optimization. It discusses how these types of optimization problems differ from linear optimization problems in that the variables must take integer values. The document outlines some key concepts like complexity, solution techniques including cutting planes and branch-and-bound, and provides an example of solving an integer optimization problem using branch-and-bound.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    MATP6620 Integer and Combinatorial Optimization

    Uploaded by

    Arya Chowdhury
    95 views4 pages
    This document provides an introduction to integer and combinatorial optimization. It discusses how these types of optimization problems differ from linear optimization problems in that the variables must take integer values. The document outlines some key concepts like complexity, solution techniques including cutting planes and branch-and-bound, and provides an example of solving an integer optimization problem using branch-and-bound.

    Original Description:

    nil

    Original Title

    01A Intro Cut Branch

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides an introduction to integer and combinatorial optimization. It discusses how these types of optimization problems differ from linear optimization problems in that the variables must take integer values. The document outlines some key concepts like complexity, solution techniques including cutting planes and branch-and-bound, and provides an example of solving an integer optimization problem using branch-and-bound.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    95 views4 pages

    MATP6620 Integer and Combinatorial Optimization

    Uploaded by

    Arya Chowdhury
    This document provides an introduction to integer and combinatorial optimization. It discusses how these types of optimization problems differ from linear optimization problems in that the variables must take integer values. The document outlines some key concepts like complexity, solution techniques including cutting planes and branch-and-bound, and provides an example of solving an integer optimization problem using branch-and-bound.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    MATP6620 Integer and Combinatorial Optimization

    Introduction
    John E. Mitchell

    1 Integer and Combinatorial Optimization


    An optimization problem is a problem of the form
    minx f (x)
    subject to x ∈ S
    where f (x) is the objective function and S is the feasible region.
    A combinatorial optimization problem is one where there is only a finite number of
    points in S.
    For example: colorings of the countries of a map, so that no two adjacent coutries
    have the same color.

    In an integer optimization problem, the variables are constrained to take integer values.
    In a mixed integer optimization problem, some of the variables are required to take
    integer values, and the remainder can take fractional values.
    For example, a mixed integer linear optimization problem has the form
    minx∈Rn ,y∈Rp cT x + dT y
    subject to Ax + By ≤ g
    x, y ≥ 0, y integer
    Here, A and B are given matrices, A ∈ Rm×n , B ∈ Rm×p . The remaining parameters c, d,
    g are vectors, c ∈ Rn , d ∈ Rp , g ∈ Rm . All vectors are understood to be column vectors
    in this course. Transpose is denoted by the superscript T . The dot product between two
    vectors c and x can be denoted cT x.
    In a mixed integer nonlinear optimization problem, the objective function and/or the con-
    straints may be nonlinear functions.

    1.1 Complexity
    Linear optimization problems can be solved in polynomial time. This implies the required
    runtime doesn’t grow too quickly as the problem size grows.
    By contrast, integer optimization problems are often NP-hard (to be defined later), which
    means that the runtime can grow very quickly in the problem size in the worst case.
    So mixed integer linear optimization problems are a lot harder to solve to global optimality
    than linear optimization problems.

    1
    1.2 Solution techniques
    Our emphasis will be on methods for finding global optimal solutions to integer opti-
    mization problems. If we have a global minimizer x∗ then there is no other feasible point
    x ∈ S with f (x) < f (x∗ ).
    In order to prove optimality, we will look at relaxations
    The simplest relaxation of a mixed integer linear optimization problem is to ignore integrality,
    giving a linear optimization problem. The principal solution techniques we then examine are

    • cutting planes: try to improve the relaxation

    • branching: subdivide the feasible region.

    1.3 Quadratic constraints and objective functions


    Some combinatorial optimization problems can be formulated with quadratic constraints
    and/or a quadratic objective function. For other problems, it can be helpful to look at a
    quadratic relaxation.
    These problems can sometimes be attacked as semidefinite optimization problems,
    which have a matrix of variables that must be symmetric and positive semidefinite.
    A useful observation: we can replace the requirement that x is a binary variable by the
    requirement that x = x2 .

    2
    2 Cutting planes
    Initial relaxation:
    Solve linear optimization relaxation
    min{cT x : Ax ≤ b, x ≥ 0}
    Cutting plane aT1 x = b1

    Solution to linear optimization relaxation

    Add a cutting plane and reoptimize:

    Solve linear optimization relaxation


    min{cT x : Ax ≤ b, x ≥ 0, aT1 x ≤ b1 }
    Cutting plane aT1 x = b1
    Solution to linear optimization relaxation

    Cutting plane aT2 x = b2

    Add a cutting plane and reoptimize:

    Solve linear optimization relaxation


    min{cT x : Ax ≤ b, x ≥ 0, aT1 x ≤ b1 , aT2 x ≤ b2 }
    Cutting plane aT1 x = b1

    Solution to linear optimization relaxation


    Cutting plane aT2 x = b2

    Solution to relaxation is integral, so it solves the integer optimization problem.

    3
    3 Branch-and-bound: An example
    We look at the integer optimization problem

    minx∈R3 5x1 + 5x2 − 13x3


    subject to x1 + x2 + x3 ≤ 6
    10x1 − 8x2 ≤ 15 (IOP )
    −6x1 − x2 + 9x3 ≤ 9
    xi ≥ 0, xi integer, i = 1, 2, 3

    It’s easy to find a feasible solution for this problem: x = (0, 0, 0). Hence we can initialize
    with z u = 0. We let

    F = {x ∈ R3 : x1 + x2 + x3 ≤ 6, 10x1 − 8x2 ≤ 15, −6x1 − x2 + 9x3 ≤ 9, x1 , x2 , x3 ≥ 0}.

    0. Root node:
    min{cT x : x ∈ F }
    x0 = (1.5, 0, 2), z 0 =
    −18.5
    x1 ≥ 2
    x1 ≤ 1
    T
    1. min{c x : x ∈ F , 2. min{cT x : x ∈ F,
    x1 ≤ 1} x1 ≥ 2}
    x1 = (1, 0, 1 23 ), x2 = (2, 85 , 2 29
    72 ),
    z 1 = −16 23 z 2 = −18 91

    x3 ≥ 2 x3 ≥ 3
    x3 ≤ 1 x3 ≤ 2
    3. min{cT x : x ∈ F,
    4. min{cT x : x ∈ F, 5. min{cT x : x ∈ F, 6. min{cT x : x ∈ F,
    x1 ≤ 1, x3 ≤ 1}
    x1 ≤ 1, x3 ≥ 2} x1 ≥ 2, x3 ≤ 2} x1 ≥ 2, x3 ≥ 3}
    x3 = (0, 0, 1),
    x4 = (1, 3, 2), x5 = (2, 58 , 2), infeasible, z 6 = +∞
    z 3 = −13
    z 4 = −6 z 5 = −12 87 fathom by
    fathom by
    fathom by bounds fathom by bounds infeasibility
    integrality

    Thus, the optimal solution to (IOP ) is x∗ = (0, 0, 1), with value z ∗ = −13.

    You might also like