Extended formulations in combinatorial optimization
From MaRDI portal
Publication:5900907
DOI10.1007/s10288-010-0122-zzbMath1219.90193OpenAlexW3022030295MaRDI QIDQ5900907
Giacomo Zambelli, Michele Conforti, Cornuéjols, Gérard
Publication date: 21 May 2010
Published in: 4OR (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10288-010-0122-z
Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items
Extended formulations for convex heptagons, Knapsack polytopes: a survey, Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles, Heuristics for exact nonnegative matrix factorization, Twelve surveys in operations research, New formulations for the elementary shortest-path problem visiting a given set of nodes, Complexity of linear relaxations in integer programming, Ideal, non-extended formulations for disjunctive constraints admitting a network representation, Strategic bidding in price coupled regions, Common information and unique disjointness, Average case polyhedral complexity of the maximum stable set problem, Regular Matroids Have Polynomial Extension Complexity, An extended formulation of the convex recoloring problem on a tree, Distributionally Robust Linear and Discrete Optimization with Marginals, Parameterized extension complexity of independent set and related problems, Extended formulation for hop constrained distribution network configuration problems, Optimal design of switched Ethernet networks implementing the multiple spanning tree protocol, An extended formulation for the 1‐wheel inequalities of the stable set polytope, The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, A Unified Framework for Pricing in Nonconvex Resource Allocation Games, Extension Complexity of Independent Set Polytopes, Some \(0/1\) polytopes need exponential size extended formulations, The Steiner connectivity problem, Strong and compact relaxations in the original space using a compact extended formulation, Deriving compact extended formulations via LP-based separation techniques, Surveys in operations research, Network-Based Approximate Linear Programming for Discrete Optimization, Extended formulations for order polytopes through network flows, Constructing Extended Formulations from Reflection Relations, Arc flow formulations based on dynamic programming: theoretical foundations and applications, A correct response model in knowledge structure theory, Quadratic reformulations of nonlinear binary optimization problems, On the \({\mathcal {H}}\)-free extension complexity of the TSP, Deriving compact extended formulations via LP-based separation techniques, On the geometric interpretation of the nonnegative rank, Extended formulations in combinatorial optimization, A Polyhedral Characterization of Border Bases, Extended formulations for polygons, Parameterized shifted combinatorial optimization, Reformulations for utilizing separability when solving convex MINLP problems, Optimum turn-restricted paths, nested compatibility, and optimum convex polygons, Polyhedral approximation of ellipsoidal uncertainty sets via extended formulations: a computational case study, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Theoretical and computational study of several linearisation techniques for binary quadratic problems, Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles, Mixed Integer Linear Programming Formulation Techniques, Extended formulations from communication protocols in output-efficient time, Balas formulation for the union of polytopes is optimal, Volume computation for sparse Boolean quadric relaxations, Smallest compact formulation for the permutahedron, Tropical lower bounds for extended formulations, Extended formulations, nonnegative factorizations, and randomized communication protocols, Uncapacitated flow-based extended formulations, No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ, On the linear extension complexity of stable set polytopes for perfect graphs, Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program, Extension Complexity of Polytopes with Few Vertices or Facets, Unnamed Item, Extended formulations for convex hulls of some bilinear functions, Lower bounds on matrix factorization ranks via noncommutative polynomial optimization, Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results, Forbidden Vertices, Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph, An upper bound for nonnegative rank, A generalization of extension complexity that captures P, Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles, The projected faces property and polyhedral relations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tightening simple mixed-integer sets with guaranteed bounds
- On cuts and matchings in planar graphs
- The perfectly matchable subgraph polytope of an arbitrary graph
- Packing and partitioning orbitopes
- Compact formulations as a union of polyhedra
- Approximate formulations for 0-1 knapsack sets
- On stable set polyhedra for K//(1,3)free graphs
- Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus
- Expressing combinatorial optimization problems by linear programs
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- On defining sets of vertices of the hypercube by linear inequalities
- Disjunctive programming: Properties of the convex hull of feasible points
- Tight formulations for some simple mixed integer programs and convex objective integer programs
- Polyhedra for lot-sizing with Wagner-Whitin costs
- A characterization of weakly bipartite graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Approximate extended formulations
- The perfectly matchable subgraph polytope of a bipartite graph
- Network Formulations of Mixed-Integer Programs
- Extended Formulations for Packing and Partitioning Orbitopes
- Projecting an Extended Formulation for Mixed-Integer Covers on Bipartite Graphs
- Polyhedral Approaches to Mixed Integer Linear Programming
- Symmetry Matters for the Sizes of Extended Formulations
- Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
- Odd Minimum Cut-Sets and b-Matchings
- On the existence of optimal solutions to integer and mixed-integer programming problems
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Reducing Matching to Polynomial Size Linear Programming
- Lectures on Polytopes
- Color-coding
- Matching, Euler tours and the Chinese postman
- Production Planning by Mixed Integer Programming
- Maximum matching and a polyhedron with 0,1-vertices
- Matroids and the greedy algorithm
- The Continuous Mixing Polyhedron
- Mixing mixed-integer inequalities
