Overview and Graph Coloring

Glossary

  • Graph Density = # of edges in graph/ # of possible edges in a graph
  • Max # of possible edges in graph = V*(V-1)/2 for an undirected graph where V - # of vertices

Hints:

  • For the graph coloring problem:
    • the higher the degree of node, higher the node is constrained. This information should be useful when solving the problem

Other Notes

Q: What is an optimization problem?

The goal of optimization is to find the best solution to a problem out of a large set of possible solutions. (Sometimes you'll be satisfied with finding any feasible solution; OR-Tools can do that as well.)

Optimization problems have the following elements:

The objective—the quantity you want to optimize. To set up an optimization problem, you need to define a function that calculates the value of the objective for any possible solution. This is called the objective function.

An optimal solution is one for which the value of the objective function is the best. ("Best" can be either a maximum or a minimum.)

constraints—restrictions on the set of possible solutions, based on the specific requirements of the problem.

A feasible solution is one that satisfies all the given constraints for the problem, without necessarily being optimal. The first step in solving an optimization problem is identifying the objective and constraints.

Q: Types of Optimisation problems

  • Linear optimization: linear optimization problem is one in which the objective function and the constraints are linear expressions in the variables
  • Constraint optimization: Constraint optimization, or constraint programming (CP), identifies feasible solutions out of a very large set of candidates, where the problem can be modeled in terms of arbitrary constraints. CP is based on feasibility (finding a feasible solution) rather than optimization (finding an optimal solution) and focuses on the constraints and variables rather than the objective function. However, CP can be used to solve optimization problems, simply by comparing the values of the objective function for all feasible solutions.
  • Mixed-integer optimization: A mixed integer optimization problem is one in which some or all of the variables are required to be integers. An example would be : the variable can take only 0 or 1 value in the context of an assigment problem, in which a group of workers needs be assigned to a set of tasks
  • Bin packing: Bin packing is the problem of packing a set of objects of different sizes into containers with different capacities. The goal is to pack as many of the objects as possible, subject to the capacities of the containers. A special case of this is the knapsack problem, in which there is just one container.
  • Network flows: Many optimization problems can be represented by a directed graph consisting of nodes and directed arcs between them. For example, transportation problems, in which goods are shipped across a railway network, can be represented by a graph in which the arcs are rail lines and the nodes are distribution centers. In the maximum flow problem, each arc has a maximum capacity that can be transported across it. The problem is to assign the amount of goods to be shipped across each arc so that the total quantity being transported is as large as possible.
  • Assignment: Assignment problems involve assigning a group of agents (say, workers or machines) to a set of tasks, where there is a fixed cost for assigning each agent to a specific task. The problem is to find the assignment with the least total cost. Assignment problems are actually a special case of network flow problems.
  • Scheduling: Scheduling problems involve assigning resources to perform a set of tasks at specific times. An important example is the job shop problem, in which multiple jobs are processed on several machines. Each job consists of a sequence of tasks, which must be performed in a given order, and each task must be processed on a specific machine. The problem is to assign a schedule so that all jobs are completed in as short an interval of time as possible.
  • Routing: Routing problems involve finding the optimal routes for a fleet of vehicles to traverse a network, defined by a directed graph.