Properties of some ILP formulations of a class of partitioning problems

DOI10.1016/S0166-218X(98)00046-8zbMath0910.90217MaRDI QIDQ1270767

Alberto Caprara

Publication date: 19 April 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

partitioningbin packinginteger linear programming formulationsvertex and edge coloring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Partitions of sets (05A18) Integer programming (90C10) Linear programming (90C05) Combinatorial optimization (90C27)

Related Items

Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem, A supernodal formulation of vertex colouring with applications in course timetabling, A branch-and-cut procedure for the Udine course timetabling problem, Lower bounds and algorithms for the 2-dimensional vector packing problem, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A comparison of two edge-coloring formulations
• Lower bounds and reduction procedures for the bin packing problem
• Resource constrained scheduling as generalized bin packing
• Solving binary cutting stock problems by column generation and branch- and-bound
• An exact algorithm for the dual bin packing problem
• Worst-case comparison of valid inequalities for the TSP
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• The strongest facets of the acyclic subgraph polytope are unknown
• Optimal Scheduling of Tasks on Identical Parallel Processors
• Lower bounds and algorithms for the 2-dimensional vector packing problem