Properties of some ILP formulations of a class of partitioning problems

DOI10.1016/S0166-218X(98)00046-8MaRDI QIDQ1270767zbMATH OpenFDO

Authors 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

bin packinginteger linear programming formulationspartitioningvertex and edge coloring

Mathematics Subject Classification ID

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

Recommendations

• Formulation of integer linear programs: an example
• A branch-and-price approach for the partition coloring problem
• On a binary-encoded ILP coloring formulation
• Worst-case analyses, linear programming and the bin-packing problem
• Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results

Cites work

• A comparison of two edge-coloring formulations
• An exact algorithm for the dual bin packing problem
• scientific article; zbMATH DE number 4202014 (Why is no real title available?)
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 3614502 (Why is no real title available?)
• Lower bounds and algorithms for the 2-dimensional vector packing problem
• Lower bounds and reduction procedures for the bin packing problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Optimal Scheduling of Tasks on Identical Parallel Processors
• Resource constrained scheduling as generalized bin packing
• Solving binary cutting stock problems by column generation and branch- and-bound
• The strongest facets of the acyclic subgraph polytope are unknown
• Worst-case comparison of valid inequalities for the TSP

Cited in

(13)

• Integer-friendly formulations for the \(r\)-separation problem
• Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems
• A branch-and-cut procedure for the Udine course timetabling problem
• Tighter representations for set partitioning problems
• On a binary-encoded ILP coloring formulation
• Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem
• Formulation of integer linear programs: an example
• Variations and extensions of Proll's integer linear programming formulation techniques for the graph partitioning problem
• Node-Packing Problems with Integer Rounding Properties
• scientific article; zbMATH DE number 7084713 (Why is no real title available?)
• Integer Programming and Combinatorial Optimization
• Lower bounds and algorithms for the 2-dimensional vector packing problem
• A supernodal formulation of vertex colouring with applications in course timetabling

This page was built for publication: Properties of some ILP formulations of a class of partitioning problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1270767)