Results 11 to 20 of about 132 (51)
A min-max theorem on tournaments [PDF]
, 2007 We present a structural characterization of all tournaments T = (V, A) such that, for any nonnegative integral weight function defined on V, the maximum size of a feedback vertex set packing is equal to the minimum weight of a triangle in T.
Chen, X, Hu, X, Zang, W
core +1 more source
An exploratory computational analysis of dual degeneracy in mixed-integer programming
EURO Journal on Computational Optimization, 2020 Dual degeneracy, i.e., the presence of multiple optimal bases to a linear programming (LP) problem, heavily affects the solution process of mixed integer programming (MIP) solvers. Different optimal bases lead to different cuts being generated, different
Gerald Gamrath +2 more
doaj
Vertex adjacencies in the set covering polyhedron [PDF]
, 2017 We describe the adjacency of vertices of the (unbounded version of the) set covering polyhedron, in a similar way to the description given by Chvatal for the stable set polytope.
Aguilera, Néstor E. +2 more
core +2 more sources
An exact approach for the multi-constraint graph partitioning problem
EURO Journal on Computational Optimization, 2020 In this work, a multi-constraint graph partitioning problem is introduced. The input is an undirected graph with costs on the edges and multiple weights on the nodes. The problem calls for a partition of the node set into a fixed number of clusters, such
Diego Recalde, Ramiro Torres, Polo Vaca
doaj
On the b-stable set polytope of graphs without bad K [PDF]
, 2003 This paper presents a branch-and-cut algorithm for the Time Window Assignment Vehicle Routing Problem (TWAVRP), the problem of assigning time windows for delivery before demand volume becomes known.
Gijswijt, D. (Dion), Schrijver, A. (Lex)
core +5 more sources
An ellipsoidal branch and bound algorithm for global optimization
, 2009 A branch and bound algorithm is developed for global optimization. Branching in the algorithm is accomplished by subdividing the feasible set using ellipses.
Hager, William, Phan, Dzung
core +1 more source
A polyhedral approach for the Equitable Coloring Problem [PDF]
, 2011 In this work we study the polytope associated with a 0,1-integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities.
Bahiense +15 more
core +2 more sources
Mathematical Optimization for the Train Timetabling Problem [PDF]
, 2010 AMS Subj. Classification: 90C57; 90C10;Rail transportation is very rich in terms of problems that can be modelled and solved using mathematical optimization techniques. The train scheduling problem as the most important part of a rail operating policy has
Bojović, Nebojša +4 more
core
FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
, 2006 We show the existence of a fully polynomial-time approximation scheme (FPTAS) for the problem of maximizing a non-negative polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed.
A.I. Barvinok +17 more
core +2 more sources
The Maximum-Weight Stable Matching Problem: Duality and Efficiency [PDF]
, 2012 Given a preference system (G,≺) and an integral weight function defined on the edge set of G (not necessarily bipartite), the maximum-weight stable matching problem is to find a stable matching of (G,≺) with maximum total weight.
Chen, X, Ding, G, Hu, X, Zang, W
core +2 more sources