Given a polytope X, a monotone concave univariate function g, and two vectors c and d, we study the discrete optimization problem of finding a vertex of X that maximizes the utility function c’x + g(d’x). This problem has numerous applications in combinatorial optimization with a probabilistic objective, including estimation of project duration with stochastic … Read more
We consider operators acting on convex subsets of the unit hypercube. These operators are used in constructing convex relaxations of combinatorial optimization problems presented as a 0,1 integer programming problem or a 0,1 polynomial optimization problem. Our focus is mostly on operators that, when expressed as a lift-and-project operator, involve the use of semidefiniteness constraints … Read more
Most real–world optimization problems are of a multi–objective nature, involving objectives which are conflicting and incomparable. Solving a multi–objective optimization problem requires a method which can generate the set of rational compromises between the objectives. In this paper, we propose two distinct bound set based branch–and–cut algorithms for bi–objective combinatorial optimization problems, based on implicitly … Read more
The classical assembly line balancing problem consists of assigning assembly work to workstations. In the presence of setup times that depend on the sequence of tasks assigned to each workstation, the problem becomes more complicated given that two interdependent problems, namely assignment and sequencing, must be solved simultaneously. The hierarchical nature of these two problems … Read more
We study the Knapsack Problem with Conflict Graph (KPCG), an extension of the 0-1 Knapsack Problem, in which a conflict graph describing incompatibilities between items is given. The goal of the KPCG is to select the maximum profit set of compatible items while satisfying the knapsack capacity constraint. We present a new Branch-and-Bound approach to … Read more
When addressing the maximum stable set problem on a graph G = (V,E), rank inequalities prescribe that, for any subgraph G[U] induced by U ⊆ V , at most as many vertices as the stability number of G[U] can be part of a stable set of G. These inequalities are very general, as many of … Read more
The goal of this paper is to identify the most promising sets of closest assignment constraints from the literature, in order to improve mixed integer linear programming formulations for exploration of information flow within a social network. The direct comparison between proposed formulations is performed on standard single source capacitated facility location problem instances. Therefore, … Read more
Valve-point loading affects the input-output characteristics of generating units, bringing the fuel costs nonlinear and nonsmooth. This has been considered in the solution of load dispatch problems, but not in the planning phase of unit commitment. This paper presents a mathematical optimization model for the thermal unit commitment problem considering valve-point loading. The formulation is … Read more
The paper deals with the definition and the computation of surrogate upper bound sets for the bi-objective bi-dimensional binary knapsack problem. It introduces the Optimal Convex Surrogate Upper Bound set, which is the tightest possible definition based on the convex relaxation of the surrogate relaxation. Two exact algorithms are proposed: an enumerative algorithm and its … Read more
In this article we survey mathematical programming approaches to problems in the field of water network optimization. Predominant in the literature are two different, but related problem classes. One can be described by the notion of network design, while the other is more aptly termed by network operation. The basic underlying model in both cases … Read more