This is a survey on the infinite group problem, an infinite-dimensional relaxation of integer linear optimization problems introduced by Ralph Gomory and Ellis Johnson in their groundbreaking papers titled “Some continuous functions related to corner polyhedra I, II” [Math. Programming 3 (1972), 23-85, 359-389]. The survey presents the infinite group problem in the modern context … Read more
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
We address combinatorial problems that can be formulated as minimization of a partially separable function of discrete variables (energy minimization in graphical models, weighted constraint satisfaction, pseudo-Boolean optimization, 0-1 polynomial programming). For polyhedral relaxations of such problems it is generally not true that variables integer in the relaxed solution will retain the same values in … Read more
The recent research on the CVRP is being slowed down by the lack of a good set of benchmark instances. The existing sets suff er from at least one of the following drawbacks: (i) became too easy for current algorithms; (ii) are too arti cial; (iii) are too homogeneous, not covering the wide range of characteristics found … Read more
We consider the Robust Network Loading problem with splittable flows and demands that belong to the budgeted uncertainty set. We compare the optimal solution cost and computational cost of the problem when using static routing, volume routing, affine routing, and dynamic routing. For the first three routing types, we compare the compact formulation with a … Read more
Cluster analysis refers to finding subsets of vertices of a graph (called clusters) which are more likely to be joined pairwise than vertices in different clusters. In the last years this topic has been studied by many researchers, and several methods have been proposed. One of the most popular is to maximize the modularity, which … Read more
We contribute to the theory for minimal liftings of cut-generating functions. In particular, we give three operations that preserve the so-called covering property of certain structured cut-generating functions. This has the consequence of vastly expanding the set of undominated cut generating functions which can be used computationally, compared to known examples from the literature. The … Read more
Gas network optimization manages the gas transport by minimizing operating costs and fulfilling contracts between consumers and suppliers. This is an NP- hard problem governed by non-convex and nonlinear gas transport functions that can be modeled by mixed integer linear programming (MILP) techniques. Under these methods, piecewise linear functions describe nonlinearities and bi- nary variables … Read more
In this work we consider the uniform capacitated single-item single-machine lot-sizing problem with continuous start-up costs. A continuous start-up cost is generated in a period whenever there is a nonzero production in the period and the production capacity in the previous period is not saturated. This concept of start-up does not correspond to the standard … Read more
In this paper we propose a methodology for constructing decision rules for integer and continuous decision variables in multiperiod robust linear optimization problems. This type of problems finds application in, for example, inventory management, lot sizing, and manpower management. We show that by iteratively splitting the uncertainty set into subsets one can differentiate the later-period … Read more