Graphs, Dioids and Semirings
New Models and Algorithms
Page
%P
-
Article
Optimal deterministic and robust selection of electricity contracts
We address the Electricity Contract Selection Problem (ECSP), of finding best parameters of an electricity contract for a client based on his/her past records of electricity consumption over a fixed time perio...
-
Article
Linear size MIP formulation of Max-Cut: new properties, links with cycle inequalities and computational results
We consider the Max-Cut problem on an undirected graph \(G=(V,E)\) G ...
-
Article
Sharp upper and lower bounds for maximum likelihood solutions to random Gaussian bilateral inequality systems
This paper focuses on finding a solution maximizing the joint probability of satisfaction of a given set of (independent) Gaussian bilateral inequalities. A specially structured reformulation of this nonconvex...
-
Article
The Fair OWA One-to-One Assignment Problem: NP-Hardness and Polynomial Time Special Cases
We consider a one-to-one assignment problem consisting of matching n objects with n agents. Any matching leads to a utility vector whose n components measure the satisfaction of the various agents. We want to fin...
-
Article
Global probability maximization for a Gaussian bilateral inequality in polynomial time
The present paper investigates Gaussian bilateral inequalities in view of solving related probability maximization problems. Since the function f representing the probability of satisfaction of a given Gaussian b...
-
Article
Stochastic graph partitioning: quadratic versus SOCP formulations
We consider a variant of the graph partitioning problem involving knapsack constraints with Gaussian random coefficients. In this new variant, under this assumption of probability distribution, the problem can...
-
Article
Convexity of Gaussian chance constraints and of related probability maximization problems
We investigate here conditions for convexity of solutions sets defined by chance constraints, along with conditions for (local) concavity of associated probability functions. Even restricting to the case of coeff...
-
Chapter and Conference Paper
Solving to Optimality a Discrete Lot-Sizing Problem Thanks to Multi-product Multi-period Valid Inequalities
We consider a problem related to industrial production planning, namely the multi-product discrete lot-sizing and scheduling problem with sequence-dependent changeover costs. This combinatorial optimization is...
-
Article
Two-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hard
As shown in previous work, robust linear programming problems featuring polyhedral right-hand side (RHS) uncertainty (a) arise in many practical applications; (b) frequently lead to robust equivalents belongin...
-
Chapter and Conference Paper
On the Solution of a Graph Partitioning Problem under Capacity Constraints
We study a variant of the graph partitioning problem where the weight of a cluster in the partition depends on the edges incident to its nodes. This problem was first proposed in the context of optical network...
-
Article
On 2-stage robust LP with RHS uncertainty: complexity results and applications
We investigate here the class—denoted R-LP-RHSU—of two-stage robust linear programming problems with right-hand-side uncertainty. Such problems arise in many applications e.g: robust PERT scheduling (with unce...
-
Chapter and Conference Paper
Mixed Integer Programming Model for Pricing in Telecommunication
Yield management has been successfully applied in the context of airline companies. However, so far, application to telecommunication industry have been scarce. Using Yield management principles, this paper in...
-
Article
On robust maximum flow with polyhedral uncertainty sets
We address the problem of determining a robust maximum flow value in a network with uncertain link capacities taken in a polyhedral uncertainty set. Besides a few polynomial cases, we focus on the case where t...
-
Reference Work Entry In depth
Maximum Constraint Satisfaction: Relaxations and Upper Bounds
Keywords
-
Reference Work Entry In depth
Robust Linear Programming with Right-Hand-Side Uncertainty, Duality and Applications
Abstract
-
Book
-
Chapter and Conference Paper
Pricing and Resource Allocation for Point-to-Point Telecommunication Services in a Competitive Market: A Bilevel Optimization Approach
With the deregulation of the telecommunication markets worldwide, network operators have to develop and offer new services to their clients in order to gain market share. In this context, yield management tech...
-
Chapter
Multicommodity Network Flow Models and Algorithms in Telecommunications
We present an overview of mathematical optimization models and solution algorithms related to optimal network design and dimensioning in telecommunications. All the models discussed are expressed in terras of ...
-
Article
A Comparison of Heuristics for the Discrete Cost Multicommodity Network Optimization Problem
In this paper, approximate solutions algorithms for discrete cost multicommodity network optimization problems are presented and compared. Firstly, extensions of classical greedy heuristics, based on link-rero...
-
Article
Discrete Cost Multicommodity Network Optimization Problems and Exact Solution Methods
We first introduce a generic model for discrete cost multicommodity network optimization, together with several variants relevant to telecommunication networks such as: the case where discrete node cost functi...
