Valid Inequalities are linear constraints satisfied by all integer feasible solutions but potentially violated by LP relaxation solutions. They strengthen formulations by tightening LP relaxation without eliminating integer solutions. Types include: cover inequalities (knapsack), clique inequalities (set packing), Gomory cuts (derived from simplex tableau), and problem-specific cuts. A valid inequality is a cutting plane if it cuts off current LP solution. Facet-defining inequalities provide strongest possible cuts for a given dimension. Identifying and generating valid inequalities is central to modern integer programming. Research includes: polyhedral combinatorics studying convex hulls of integer solutions, separation algorithms for cut generation, and cut selection strategies.

The Vehicle Routing Problem extends TSP to multiple vehicles serving customers from a depot. Basic VRP: minimize total distance for m vehicles with capacity Q serving n customers with demands dᵢ. Each customer visited exactly once, vehicle capacities respected, all routes start/end at depot. VRP is NP-hard with numerous variants: CVRP (capacitated), VRPTW (time windows), MDVRP (multiple depots), SDVRP (split deliveries), PVRP (periodic), DVRP (dynamic). Solution approaches: exact methods (branch-and-cut, column generation), classical heuristics (Clarke-Wright savings, sweep algorithm), and metaheuristics (genetic algorithms, tabu search, ant colony optimization). Critical for logistics, delivery services, and supply chain optimization.