Combinatorial Optimization

Toward Efficient Transportation Electrification of Heavy-Duty Trucks: Joint Scheduling of Truck Routing and Charging

  • Mikhail Bragin
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Transportation Tags

    The timely transportation of goods to customers is an essential component of economic activities. However, heavy-duty diesel trucks that deliver goods contribute significantly to greenhouse gas emissions within many large metropolitan areas, including Los Angeles, New York, and San Francisco. To facilitate freight electrification, this paper proposes joint routing and charging (JRC) scheduling for electric … Read more

    Semi-Infinite Mixed Binary and Disjunctive Programs: Applications to Set-Covering with Infinite Demand Points and Implicit Hitting Set Problems

  • Manish Bansal
    • Categories Combinatorial Optimization, Integer Programming, Semi-infinite Programming

    Sherali and Adams [Discrete Applied Math. 157: 1319-1333, 2009] derived convex hull of semi-infinite mixed binary linear programs (SIMBLPs) using Reformulation-Linearization Technique (RLT). In this paper, we study semi-infinite disjunctive programs (SIDPs — a generalization of SIMBLPs) and present linear programming equivalent and valid inequalities for them. We utilize these results for deriving a hierarchy … Read more

    Recognizing Series-Parallel Matrices in Linear Time

  • Matthias Walter
    • Categories Graphs and Matroids Tags ,

    \(\) A series-parallel matrix is a binary matrix that can be obtained from an empty matrix by successively adjoining rows or columns that are copies of an existing row/column or have at most one 1-entry. Equivalently, series-parallel matrices are representation matrices of graphic matroids of series-parallel graphs, which can be recognized in linear time. We … Read more

    The min-Knapsack Problem with Compactness Constraints and Applications in Statistics

  • Alberto Santini
  • Enrico Malaguti
    • Categories Branch and Cut Algorithms, Dynamic Programming, Statistics Tags , ,

    In the min-Knapsack problem, one is given a set of items, each having a certain cost and weight. The objective is to select a subset with minimum cost, such that the sum of the weights is not smaller than a given constant. In this paper we introduce an extension of the min-Knapsack problem with additional … Read more

    The Hamiltonian p-median Problem: Polyhedral Results and Branch-and-Cut Algorithm

  • Michele Barbato
  • Luís Gouveia
    • Categories Branch and Cut Algorithms, Combinatorial Optimization, Polyhedra Tags , , , ,

    \(\) In this paper we study the Hamiltonian \(p\)-median problem, in which a weighted graph on \(n\) vertices is to be partitioned into \(p\) simple cycles of minimum total weight. We introduce two new families of valid inequalities for a formulation of the problem in the space of natural edge variables. Each one of the … Read more

    A comparison of different approaches for the vehicle routing problem with stochastic demands

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Branch and Cut Algorithms, Production and Logistics, Stochastic Programming Tags , ,

    The vehicle routing problem with stochastic demands (VRPSD) is a well studied variant of the classic (deterministic) capacitated vehicle routing problem (CVRP) where the customer demands are given by random variables. Two prominent approaches for solving the VRPSD model it either as a chance-constraint program (CC-VRPSD) or as a two-stage stochastic program (2S-VRPSD). In this … Read more

    Scalable heuristic algorithm for identifying critical nodes in networks

  • Dalaijargal Purevusren
    • Categories Combinatorial Optimization, Graphs and Matroids, Network Optimization

    This paper presents two heuristic algorithms for the distance-based critical node problem (DCNP) that finds k nodes whose removal minimizes the pairwise connection within D hops in the remaining network. The structural properties of the complex networks have not yet been extensively addressed in the literature. Specifically, the community structure of complex networks needs to … Read more

    Insertion Heuristics for a Class of Dynamic Vehicle Routing Problems

  • Adam N. Letchford
    • Categories Combinatorial Optimization, Transportation Tags ,

    We consider a simple family of dynamic vehicle routing problems, in which we have a fixed fleet of identical vehicles, and customer requests arrive during the route-planning process. For this kind of problem, it is natural to use an insertion heuristic. We test several such heuristics computationally, on two different variants of the problem. It … Read more

    A polyhedral study of multivariate decision trees

  • Carla Michini
  • Zachary Zhou
    • Categories (Mixed) Integer Linear Programming, Data Science Theory, Polyhedra Tags , ,

    Decision trees are a widely used tool for interpretable machine learning. Multivariate decision trees employ hyperplanes at the branch nodes to route datapoints throughout the tree and yield more compact models than univariate trees. Recently, mixed-integer programming (MIP) has been applied to formulate the optimal decision tree problem. To strengthen MIP formulations, it is crucial … Read more

    On Constrained Mixed-Integer DR-Submodular Minimization

  • Qimeng Yu
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming, Polyhedra Tags , , ,

    DR-submodular functions encompass a broad class of functions which are generally non-convex and non-concave. We study the problem of minimizing any DR-submodular function, with continuous and general integer variables, under box constraints and possibly additional monotonicity constraints. We propose valid linear inequalities for the epigraph of any DR-submodular function under the constraints. We further provide … Read more