Discrete optimization

Discrete optimization is a branch of optimization in applied mathematics and computer science.

As opposed to continuous optimization, the variables used in the mathematical program (or some of them) are restricted to assume only discrete values, such as the integers.

Two notable branches of discrete optimization are:

• combinatorial optimization, which refers to problems on graphs, matroids and other discrete structures
• integer programming

These branches are closely intertwined however since many combinatorial optimization problems can be modeled as integer programs (e.g. shortest path) and conversely, integer programs can often be given a combinatorial interpretation.

Feasible Exhaustive Search Algorithm

An algorithm is a combinatorial optimization protocol for this feasible attack on an NP-complete problem called Exhaustive search.

   //   
   //  ExhaustiveMIS:=procedure(G; IS) global List;
   //  if G=empty graph then
   //  List:=List [ IS //IS is a maximal IS, and the algorithm needs to end its exhaustive search to decide

   //  if it is actually a MIS.
   //  else //we now consider the “pivot” vertex v of smallest label:
   //  ExhaustiveMIS(G ?? v; IS) //assuming v 62 IS.
   //  ExhaustiveMIS(G ?? (v and all its neighbours), IS [ fvg) //assuming v 2 IS
   //  end if
   //  end procedure;
   //  BasicAlgorithm:=procedure(G);
   //  List:=fg; //will contain the list of all the maximal IS.
   //  ExhaustiveMIS(G; fg);
   //  RETURN(the largest sets in List) // this will give the list of the MIS
   //  end;[1]