valid inequalities

Valid Inequalities and Restrictions for Stochastic Programming Problems with First Order Stochastic Dominance Constraints

  • Nilay Noyan
  • Andrzej Ruszczyński
    • Categories Stochastic Programming Tags , , ,

    Stochastic dominance relations are well-studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance (SSD) constraints can be solved by linear programming (LP). However, problems involving first order stochastic dominance … Read more

    Robust DWDM Routing and Provisioning under Polyhedral Demand Uncertainty

  • Oya Ekin Karasan
  • Mustafa C. Pinar
  • Hande Yaman
    • Categories (Mixed) Integer Linear Programming, Robust Optimization, Telecommunications Tags , , , ,

    We present mixed integer linear programming models that are robust in the face of uncertain traffic demands known to lie in a certain polyhedron for the problem of dense wavelength division multiplexing network routing and provisioning at minimal cost. We investigate the solution of the problem in a set of numerical experiments for two models … Read more

    Manufacturer’s Mixed Pallet Design Problem

  • Alper Sen
  • Hande Yaman
    • Categories (Mixed) Integer Linear Programming, Production and Logistics Tags , , ,

    We study a problem faced by a major beverage producer. The company produces and distributes several brands to various customers from its regional distributors. For some of these brands, most customers do not have enough demand to justify full pallet shipments. Therefore, the company decided to design a number of mixed or “rainbow” pallets so … Read more

    Sequential pairing of mixed integer inequalities

  • Shabbir Ahmed
  • Yongpei Guan
  • George L. Nemhauser
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We present a scheme for generating new valid inequalities for mixed integer programs by taking pair-wise combinations of existing valid inequalities. Our scheme is related to mixed integer rounding and mixing. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that … Read more

    Formulations and Valid Inequalities for the Heterogeneous Vehicle Routing Problem

  • Hande Yaman
    • Categories (Mixed) Integer Nonlinear Programming, Transportation Tags , , , ,

    We consider the vehicle routing problem where one can choose among vehicles with different costs and capacities to serve the trips. We develop six different formulations: the first four based on Miller-Tucker-Zemlin constraints and the last two based on flows. We compare the linear programming bounds of these formulations. We derive valid inequalities and lift … Read more

    Valid inequalities based on simple mixed-integer sets

  • Sanjeeb Dash
  • Oktay Gunluk
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , ,

    In this paper we use facets of mixed-integer sets with two and three variables to derive valid inequalities for integer sets defined by a single equation. These inequalities also define facets of the master cyclic group polyhedron of Gomory. Facets of this polyhedron give strong valid inequalities for general mixed-integer sets, such as the well-known … Read more