Extended formulations in combinatorial optimization
From MaRDI portal
Recommendations
- Extended formulations in combinatorial optimization
- Deriving compact extended formulations via LP-based separation techniques
- Deriving compact extended formulations via LP-based separation techniques
- Compact extended linear programming models
- Combinatorial bounds on nonnegative rank and extended formulations
Cites work
- A characterization of weakly bipartite graphs
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- Approximate extended formulations
- Approximate formulations for 0-1 knapsack sets
- Color-coding
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Compact formulations as a union of polyhedra
- Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus
- Compacting cuts, a new linear formulation for minimum cut
- Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
- Disjunctive programming: Properties of the convex hull of feasible points
- Expressing combinatorial optimization problems by linear programs
- Extended formulations for packing and partitioning orbitopes
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- scientific article; zbMATH DE number 3121293 (Why is no real title available?)
- scientific article; zbMATH DE number 3121294 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 1263275 (Why is no real title available?)
- Lectures on Polytopes
- Matching, Euler tours and the Chinese postman
- Matroids and the greedy algorithm
- Maximum matching and a polyhedron with 0,1-vertices
- Mixing mixed-integer inequalities
- Network Formulations of Mixed-Integer Programs
- Odd Minimum Cut-Sets and b-Matchings
- On cuts and matchings in planar graphs
- On defining sets of vertices of the hypercube by linear inequalities
- On stable set polyhedra for K//(1,3)free graphs
- On the existence of optimal solutions to integer and mixed-integer programming problems
- Packing and partitioning orbitopes
- Polyhedra for lot-sizing with Wagner-Whitin costs
- Polyhedral approaches to mixed integer linear programming
- Production Planning by Mixed Integer Programming
- Projecting an extended formulation for mixed-integer covers on bipartite graphs
- Reducing Matching to Polynomial Size Linear Programming
- Symmetry matters for the sizes of extended formulations
- The Continuous Mixing Polyhedron
- The perfectly matchable subgraph polytope of a bipartite graph
- The perfectly matchable subgraph polytope of an arbitrary graph
- Tight formulations for some simple mixed integer programs and convex objective integer programs
- Tightening simple mixed-integer sets with guaranteed bounds
Cited in
(91)- Complete formulations of polytopes related to extensions of assignment matrices
- An extended formulation of the convex recoloring problem on a tree
- Extended formulation for hop constrained distribution network configuration problems
- Optimal design of switched Ethernet networks implementing the multiple spanning tree protocol
- Compact extended linear programming models
- Surveys in operations research
- Extended formulations for order polytopes through network flows
- On the geometric interpretation of the nonnegative rank
- Combinatorial bounds on nonnegative rank and extended formulations
- Polyhedral approximation of ellipsoidal uncertainty sets via extended formulations: a computational case study
- Extended formulations for vertex cover
- A smaller extended formulation for the odd cycle inequalities of the stable set polytope
- Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles
- Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph
- Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
- Complexity of linear relaxations in integer programming
- Ideal, non-extended formulations for disjunctive constraints admitting a network representation
- Strategic bidding in price coupled regions
- Limits to the scope of applicability of extended formulations theory for LP models of combinatorial optimisation problems
- Arc flow formulations based on dynamic programming: theoretical foundations and applications
- A correct response model in knowledge structure theory
- Theoretical and computational study of several linearisation techniques for binary quadratic problems
- Extended formulations for radial cones
- Balas formulation for the union of polytopes is optimal
- Volume computation for sparse Boolean quadric relaxations
- On the linear extension complexity of stable set polytopes for perfect graphs
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- An upper bound for nonnegative rank
- A generalization of extension complexity that captures P
- Parameterized extension complexity of independent set and related problems
- Some \(0/1\) polytopes need exponential size extended formulations
- The Steiner connectivity problem
- Twelve surveys in operations research
- The projected faces property and polyhedral relations
- Extended formulations for convex heptagons
- Exponential lower bounds for polytopes in combinatorial optimization
- Mixed integer linear programming formulation techniques
- Extension complexity of polytopes with few vertices or facets
- Heuristics for exact nonnegative matrix factorization
- Extended formulation lower bounds via hypergraph coloring?
- Constructing extended formulations from reflection relations
- Finding descriptions of polytopes via extended formulations and liftings
- Cuts over extended formulations by flow discretization
- New formulations for the elementary shortest-path problem visiting a given set of nodes
- Common information and unique disjointness
- Average case polyhedral complexity of the maximum stable set problem
- Branched polyhedral systems
- Strong and compact relaxations in the original space using a compact extended formulation
- The nonnegative rank of a matrix: hard problems, easy solutions
- Extension complexity of independent set polytopes
- Lifting linear extension complexity bounds to the mixed-integer setting
- Small extended formulation for knapsack cover inequalities from monotone circuits
- Symmetry Matters for Sizes of Extended Formulations
- Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
- Regular matroids have polynomial extension complexity
- Distributionally Robust Linear and Discrete Optimization with Marginals
- Network-based approximate linear programming for discrete optimization
- Quadratic reformulations of nonlinear binary optimization problems
- On the \({\mathcal {H}}\)-free extension complexity of the TSP
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
- Tight lower bounds on the sizes of symmetric extensions of permutahedra and similar results
- Forbidden vertices
- Constructing extended formulations from reflection relations
- Advances in Combinatorial Optimization
- A Polyhedral Characterization of Border Bases
- Deriving compact extended formulations via LP-based separation techniques
- Extended formulations in combinatorial optimization
- Deriving compact extended formulations via LP-based separation techniques
- An extended formulation for the 1‐wheel inequalities of the stable set polytope
- Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
- A Unified Framework for Pricing in Nonconvex Resource Allocation Games
- Scheduling-location problem with drones
- Circuits in extended formulations
- Extended formulations via decision diagrams
- Generalized Nash equilibrium problems with mixed-integer variables
- Max-utility matchings with popularity via critical vertices
- Last fifty years of integer linear programming: a focus on recent practical advances
- The extension complexity of polytopes with bounded integral slack matrices
- Still more surveys in operations research\dots
- Extended formulations for polygons
- Reformulations for utilizing separability when solving convex MINLP problems
- Sublinear extensions of polygons
- Optimum turn-restricted paths, nested compatibility, and optimum convex polygons
- Computational aspects of lifted cover inequalities for knapsacks with few different weights
- Branch-and-bound versus lift-and-project relaxations in combinatorial optimization
- Smallest compact formulation for the permutahedron
- Tropical lower bounds for extended formulations
- Uncapacitated flow-based extended formulations
- Extended formulations for convex hulls of some bilinear functions
- Knapsack polytopes: a survey
This page was built for publication: Extended formulations in combinatorial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5900907)
