Motivated by an application in highway pricing, we consider the problem that consists in setting profit-maximizing tolls on a clique subset of a multicommodity transportation network. Following a proof that clique pricing is NP-hard, we propose strong valid inequalities, some of which define facets of the 2-commodity polyhedron. The numerical efficiency of these inequalities is … Read more
Recently minimal and extreme inequalities for continuous group relaxations of general mixed integer sets have been characterized. In this paper, we consider a stronger relaxation of general mixed integer sets by allowing constraints, such as bounds, on the free integer variables in the continuous group relaxation. We generalize a number of results for the continuous … Read more
In recent years there has been growing interest in generating valid inequalities for mixed-integer programs using sets with 2 or more constraints. In particular, Andersen et.al (2007) and Borozan and Cornue’jols (2007) study sets defined by equations that contain exactly one integer variable per row. The integer variables are not restricted in sign. Cutting planes … Read more
Cybersecurity is a growing concern, especially in open grids, where attack propagation is easy because of prevalent collaborations among thousands of users and hundreds of institutions. The collaboration rules that typically govern large science experiments as well as social networks of scientists span across the institutional security boundaries. A common concern is that the increased … Read more
The mixing set with a knapsack constraint arises in deterministic equivalent of probabilistic programming problems with finite discrete distributions. We first consider the case that the probabilistic program has equal probabilities for each scenario. We study the resulting mixing set with a cardinality constraint and propose facet-defining inequalities that subsume known explicit inequalities for this … Read more
The Mobile Oil Recovery (MOR) unit is a truck able to pump marginal wells in a petrol field. The goal of the MOR optimization Problem (MORP) is to optimize both the oil extraction and the travel costs. We describe several formulations for the MORP using a single vehicle or a fleet of vehicles. We have … Read more
We consider an optimization model for determining optimal opportunistic maintenance (that is, component replacement) schedules when data is deterministic. This problem generalizes that of Dickman, Epstein, and Wilamowsky [21] and is a natural starting point for the modelling of replacement schedules when component lives are non-deterministic. We show that this basic opportunistic replacement problem is … Read more
In this work, we establish a parallel between two classes of pricing problems that have attracted the attention of researchers in economics, theoretical computer science and operations research, each community addressing issues from its own vantage point. More precisely, we contrast the problems of pricing a network or a product line, in order to achieve … Read more
If a mathematical program (be it linear or nonlinear) has many symmetric optima, solving it via Branch-and-Bound techniques often yields search trees of disproportionate sizes; thus, finding and exploiting symmetries is an important task. We propose a method for automatically finding the formulation group of any given Mixed-Integer Nonlinear Program, and reformulating the problem so … Read more
We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal-dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is inapproximable within a factor strictly less than … Read more