n-step cutset inequalities: facets for multi-module capacitated network design problem

Many real-world decision-making problems can be modeled as network design problems, especially on networks with capacity requirements on links. In network design problems, decisions are made on installation of flow transfer capacities on the links and routing of flow from a set of source nodes to a set of sink nodes through the links. Many … Read more

Facets for Continuous Multi-Mixing Set with General Coefficients and Bounded Integer Variables

Bansal and Kianfar introduced continuous multi-mixing set where the coefficients satisfy the so-called n-step MIR conditions and developed facet-defining inequalities for this set. In this paper, we first generalize their inequalities for the continuous multi-mixing set with general coefficients (where no conditions are imposed on the coefficients) and show that they are facet-defining in many … Read more

Planar Maximum Coverage Location Problem with Partial Coverage and Rectangular Demand and Service Zones

We study the planar maximum coverage location problem (MCLP) with rectilinear distance and rectangular demand zones in the case where “partial coverage” is allowed in its true sense, i.e., when covering only part of a demand zone is allowed and the coverage accrued as a result of this is proportional to the demand of the … Read more

n-step cycle inequalities: facets for continuous n-mixing set and strong cuts for multi-module capacitated lot-sizing problem

In this paper, we introduce a generalization of the continuous mixing set (which we refer to as the continuous n-mixing set). This set is closely related to the feasible set of the multi-module capacitated lot-sizing (MML) problem with(out) backlogging. We develop new classes of valid inequalities for this set, referred to as n’-step cycle inequalities, … Read more

n-step Conic Mixed Integer Rounding Inequalities

We introduce the n-step conic MIR inequalities for the so-called polyhedral second-order conic (PSOC) mixed integer sets. PSOC sets arise in the polyhedral reformulation of the second-order conic mixed integer programs. Moreover, they are an equivalent representation for any mixed integer set defined by two linear constraints. The simple conic MIR inequalities of Atamt├╝rk and … Read more

Mixed n-Step MIR Inequalities: Facets for the n-Mixing Set

Gunluk and Pochet [O. Gunluk, Y. Pochet: Mixing mixed integer inequalities. Mathematical Programming 90(2001) 429-457] proposed a procedure to mix mixed integer rounding (MIR) inequalities. The mixed MIR inequalities define the convex hull of the mixing set $\{(y^1,\ldots,y^m,v) \in Z^m \times R_+:\alpha_1 y^i + v \geq \b_i,i=1,\ldots,m\}$ and can also be used to generate valid … Read more

On n-step MIR and Partition Inequalities for Integer Knapsack and Single-node Capacitated Flow Sets

Pochet and Wolsey [Y. Pochet, L.A. Wolsey, Integer knapsack and flow covers with divisible coefficients: polyhedra, optimization and separation. Discrete Applied Mathematics 59(1995) 57-74] introduced partition inequalities for three substructures arising in various mixed integer programs, namely the integer knapsack set with nonnegative divisible/arbitrary coefficients and two forms of single-node capacitated flow set with divisible … Read more

A Polyhedral Study of Triplet Formulation for Single Row Facility Layout Problem

The Single Row Facility Layout Problem (SRFLP) is the problem of arranging n departments with given lengths on a straight line so as to minimize the total weighted distance between all department pairs. We present a polyhedral study of the triplet formulation of the SRFLP introduced by Amaral [Discrete Applied Mathematics 157(1)(2009)183-190]. For any number … Read more

n-step Mingling Inequalities: New Facets for the Mixed-Integer Knapsack Set

The n-step mixed integer rounding (MIR) inequalities of Kianfar and Fathi are valid inequalities for the mixed-integer knapsack set that are derived by using periodic n-step MIR functions and define facets for group problems. The mingling and 2-step mingling inequalities of Atamturk and Gunluk are also derived based on MIR and they incorporate upper bounds … Read more

n-step MIR Functions: Facets for Finite and Infinite Group Problems

The n-step mixed integer rounding (MIR) functions are used to generate n-step MIR inequalities for (mixed) integer programming problems (Kianfar and Fathi, 2006). We show that these functions are sources for generating extreme valid inequalities (facets) for group problems. We first prove the n-step MIR function, for any positive integer n, generates two-slope facets for … Read more