Graduate
  1. Real Analysis  1.1. Set Theory and Logic  1.1.1. Sets and Operations  1.1.2. Relations and Functions  1.1.3. Logic and Quantifiers  1.1.4. Cardinality of Sets  1.2. Metric Spaces  1.2.1. Open and Closed Sets  1.2.2. Convergence of Sequences  1.2.3. Continuous Functions in Metric Spaces  1.2.4. Compactness and Completeness in Metric Spaces in Real Analysis  1.3. Sequence and Series  1.3.1. Convergence of Sequences  1.3.2. Infinite Series  1.3.3. Uniform Convergence  1.3.4. Power Series  1.4. Differentiation  1.4.1. Mean Value Theorems  1.4.2. Taylor Series  1.4.3. Functions of Several Variables  1.4.4. Partial Derivatives  1.5. Integration  1.5.1. Riemann and Lebesgue Integration  1.5.2. Improper Integrals  1.5.3. Measure Theory  1.5.4. Fubini’s Theorem  1.6. Functional Analysis  1.6.1. Banach Spaces  1.6.2. Hilbert Spaces  1.6.3. Operators on Spaces  1.6.4. Spectral Theory
  2. Abstract Algebra  2.1. Groups  2.1.1. Definitions and Examples in Groups in Abstract Algebra  2.1.2. Group Homomorphisms  2.1.3. Normal Subgroups  2.1.4. Sylow Theorems  2.2. Rings and Fields  2.2.1. Ideals and Factor Rings  2.2.2. Field Extensions  2.2.3. Galois Theory  2.2.4. Polynomial Rings  2.3. Modules  2.3.1. Module Homomorphisms  2.3.2. Free Modules  2.3.3. Tensor Products  2.3.4. Exact Sequences  2.4. Linear Algebra  2.4.1. Vector Spaces  2.4.2. Eigenvalues and Eigenvectors  2.4.3. Inner Product Spaces  2.4.4. Diagonalization
  3. Topology  3.1. General Topology  3.1.1. Open and Closed Sets  3.1.2. Compactness and Connectedness  3.1.3. Continuous Maps  3.1.4. Separation Axioms  3.2. Algebraic Topology  3.2.1. Fundamental Groups  3.2.2. Homotopy and Homology  3.2.3. Simplicial Complexes  3.2.4. Exact Sequences in Homology  3.3. Differential Topology  3.3.1. Manifolds  3.3.2. Smooth Functions  3.3.3. Tangent and Cotangent Spaces  3.3.4. Vector Bundles
  4. Differential Equations  4.1. Ordinary Differential Equations  4.1.1. First-Order Equations  4.1.2. Second-Order Linear Equations  4.1.3. Systems of Differential Equations  4.1.4. Stability Analysis  4.2. Partial Differential Equations  4.2.1. Classification of PDEs  4.2.2. Fourier Series  4.2.3. Green's Functions  4.2.4. Method of Characteristics  4.3. Dynamical Systems  4.3.1. Stability Theory  4.3.2. Limit Cycles  4.3.3. Chaos Theory  4.3.4. Bifurcation Theory
  5. Probability and Statistics  5.1. Probability Theory  5.1.1. Random Variables  5.1.2. Probability Distributions  5.1.3. Law of Large Numbers  5.1.4. Central Limit Theorem  5.2. Statistical Inference  5.2.1. Hypothesis Testing  5.2.2. Confidence Intervals  5.2.3. Bayesian Methods  5.2.4. Maximum Likelihood Estimation  5.3. Stochastic Processes  5.3.1. Markov Chains  5.3.2. Brownian Motion  5.3.3. Poisson Processes  5.3.4. Martingales
  6. Numerical Analysis  6.1. Numerical Solutions of Equations  6.1.1. Root Finding  6.1.2. Iterative Methods  6.1.3. Convergence Analysis  6.1.4. Error Bounds in Numerical Solutions of Equations  6.2. Numerical Linear Algebra  6.2.1. Matrix Factorizations  6.2.2. Eigenvalue Computations  6.2.3. Sparse Matrices  6.2.4. Preconditioning Techniques  6.3. Numerical Integration and Differentiation  6.3.1. Quadrature Methods  6.3.2. Finite Differences  6.3.3. Error Analysis in Numerical Integration and Differentiation  6.3.4. Adaptive Methods
  7. Complex Analysis  7.1. Complex Numbers  7.1.1. Polar Form  7.1.2. Complex Conjugates  7.1.3. Exponential Form  7.1.4. Roots of Unity  7.2. Analytic Functions  7.2.1. Cauchy-Riemann Equations  7.2.2. Power Series  7.2.3. Conformal Mappings  7.2.4. Harmonic Functions  7.3. Integration in the Complex Plane  7.3.1. Cauchy’s Theorem  7.3.2. Residue Theorem  7.3.3. Contour Integration  7.3.4. Integral Transforms
  8. Mathematical Logic and Foundations  8.1. Propositional Logic  8.1.1. Truth Tables  8.1.2. Logical Equivalences  8.1.3. Proof Techniques in Propositional Logic  8.1.4. Resolution  8.2. Predicate Logic  8.2.1. Quantifiers in Predicate Logic  8.2.2. Formal Systems in Predicate Logic  8.2.3. Completeness and Soundness  8.2.4. Model Theory  8.3. Set Theory  8.3.1. Cardinality and Ordinality  8.3.2. Axiomatic Systems  8.3.3. Zermelo-Fraenkel Set Theory  8.3.4. Forcing
  9. Optimization  9.1. Linear Programming  9.1.1. Simplex Method  9.1.2. Duality in Linear Programming  9.1.3. Sensitivity Analysis  9.1.4. Interior Point Methods  9.2. Nonlinear Programming  9.2.1. Gradient Descent  9.2.2. Lagrange Multipliers  9.2.3. Convex Optimization  9.2.4. Quadratic Programming  9.3. Combinatorial Optimization  9.3.1. Graph Algorithms  9.3.2. Integer Programming  9.3.3. Network Flows  9.3.4. Approximation Algorithms
  10. Discrete Mathematics  10.1. Graph Theory  10.1.1. Graph Representations  10.1.2. Planarity and Coloring  10.1.3. Shortest Path Algorithms  10.1.4. Network Flows  10.2. Combinatorics  10.2.1. Permutations and Combinations  10.2.2. Generating Functions  10.2.3. Recurrence Relations  10.2.4. Inclusion-Exclusion Principle  10.3. Cryptography  10.3.1. Number Theory Applications in Cryptography  10.3.2. Symmetric and Asymmetric Cryptography  10.3.3. RSA and Elliptic Curve Cryptography  10.3.4. Post-Quantum Cryptography

Graduate → Optimization → Combinatorial Optimization ↓


Integer Programming


Integer programming is a branch of mathematical optimization or mathematical programming. In this context, "optimization" means selecting the best element from a given set of available alternatives, with respect to some criterion. Integer programming deals specifically with optimization problems where some or all of the variables are restricted to be integers.

Types of integer programming

  • Pure integer programming (PIP): All decision variables are required to take integer values.
  • Mixed integer programming (MIP): Only some of the variables are required to be integers, while others can be non-integers.
  • Binary integer programming: Special case of integer programming where variables are limited to 0 or 1. It is often used for yes/no decisions.

Importance in combinatorial optimization

Many problems in combinatorial optimization can be formulated as integer programming problems. Combinatorial optimization focuses on objects that are discrete or that can be counted. Since integer values are discrete, integer programming is the best way to solve such problems and becomes important in solving it.

Formulation of integer programming problem

The integer programming problem is usually formulated as follows:

Maximize (or Minimize): c 1 x 1 + c 2 x 2 + ... + c n x n 
Subject to: 
a 11 x 1 + a 12 x 2 + ... + a 1n x n ≤ b 1 
a 21 x 1 + a 22 x 2 + ... + a 2n x n ≤ b 2 
... 
a m1 x 1 + a m2 x 2 + ... + a mn x n ≤ b m 
Where: x 1 , x 2 , ..., x n are integers

Here, c i denotes the coefficients of the objective function that you want to maximize or minimize, a ij denotes the coefficients of the constraints, and b i denotes the boundaries of the constraints.

Example: the knapsack problem

Let's consider a classic example of integer programming: the knapsack problem. The objective is to maximize the total value of the items placed in the knapsack, without exceeding its carrying capacity.

Example of a knapsack problem:

  • Items: 4 items with weights w = [2, 3, 4, 5] and values v = [3, 4, 5, 6]
  • Capacity: This bag can carry the weight of maximum 5 people.

Formulate the knapsack problem using integer programming:

Maximize: 3x 1 + 4x 2 + 5x 3 + 6x 4 
Subject to: 2x 1 + 3x 2 + 4x 3 + 5x 4 ≤ 5 
Where: x 1 , x 2 , x 3 , x 4 ∈ {0, 1}

The restriction x i ∈ {0, 1} ensures that each item can either be included in the bag or not.

Visual representation

5 (weight) 4 (weight) 3 (weight) 2 (weight)

This view shows a simplified model of a bag with the weight packed in descending order.

Solving integer programming problems

Integer programming problems are generally NP-hard, meaning that there are no known algorithms that can solve all such problems efficiently (in polynomial time). However, several approaches can be adopted to solve specific problems.

1. Branch and bound

This is a widely used method for solving integer programming problems. The basic idea is to divide the problem into smaller sub-problems (branches) and find the optimal solution by evaluating the bounds of these sub-problems while subproblems are to be systematically eliminated if their boundaries indicate that they cannot contain a better solution (limit).

2. Cutting plane method

This method improves the linear relaxation of the integer programming problem by iteratively inserting linear constraints (cutting planes) into the problem, with the aim of filtering out regions of the solution space that do not have integer solutions.

Practical applications of integer programming

  • Resource allocation: allocation of limited resources among competing activities.
  • Scheduling: Allocating time frames to tasks, such as work schedules, transportation schedules, etc.
  • Network design: design of network paths, specifying bandwidth, etc.
  • Production planning: Planning production activities, such as the quantity of products to be produced.

Example problem: task scheduling

Consider a set of some tasks, each of which has a specific processing time and deadline. The objective is to schedule the tasks in such a way that the total latency is minimized, which is the amount by which the tasks are delayed to complete and takes longer than the deadline.

Example:

  • Jobs: Job 1, Job 2, Job 3, processing times 2, 4, 3 and deadlines 2, 6, 5 respectively.

Formulate this scheduling problem using integer programming:

Minimize: T 1 + T 2 + T 3 
Subject to: 
x 1,1 + x 1,2 + x 1,3 = 1 
x 2,1 + x 2,2 + x 2,3 = 1 
x 3,1 + x 3,2 + x 3,3 = 1 
Completion Constraints: 
C 1 = 2x 1,1 + 4x 2,1 + 3x 3,1 
C 2 = C 1 + 2x 1,2 + 4x 2,2 + 3x 3,2 
C 3 = C 2 + 2x 1,3 + 4x 2,3 + 3x 3,3 
Where: 
T i = max(0, C i - deadline i ) 
x i,j ∈ {0, 1}

Advantages of integer programming

Integer programming provides a powerful framework for solving many complex decision-making problems, because of its ability to model logical requirements within optimization problems. This is particularly beneficial when:

  • Decisions can naturally be represented in on/off terms (e.g., whether or not to invest).
  • Your solution must adhere to strict logical constraints.
  • You will have to solve problems where some of the variables require different values.

Conclusion

Integer programming plays a vital role not only in the broad field of optimization but also in many practical applications across industries. Despite its complexity and computational intensity, there are effective strategies and heuristics that can be used to obtain feasible solutions to real-world problems. As computational power continues to increase, integer programming is becoming more useful and widespread in handling complex decision-making challenges.


Graduate → 9.3.2


U
username
0%
completed in Graduate

← Prev (9.3.1)
Graph Algorithms
Next (9.3.3) →
Network Flows

Comments 



Integer Programming

https://www.buddymath.com/g/9.3.2?bmal=en