Some inverse optimization problems under the Hamming distance

Given a feasible solution to a particular combinatorial optimization problem defined on a graph and a cost vector defined on the arcs of the graph, the corresponding inverse problem is to disturb the cost vector such that the feasible solution becomes optimal. The aim is to optimize the difference between the initial cost vector and the disturbed one. This difference can be measured in several ways. We consider the Hamming distance measuring in how many components two vectors are different, where weights are associated to the components. General algorithms for the bottleneck or minimax criterion are described and (after modification) applied to the inverse minimum spanning tree problem, the inverse shortest path tree problem and the linear assignment problem.     

On the K shortest path trees problem

We address the problem of finding the K best path trees connecting a source node with any other non-source node in a directed network with arbitrary lengths. The main result in this paper is the proof that the kth shortest path tree is adjacent to at least one of the previous (k-1) shortest path trees. Consequently, we design an O(f(n,m,C_max)+Km) time and O(K+m) space algorithm to determine the K shortest path trees, in a directed network with n nodes, m arcs and maximum absolute length C_max, where O(f(n,m,C_max)) is the best time needed to solve the shortest simple paths connecting a source node with any other non-source node.     

A robust optimization approach to wine grape harvesting scheduling

Optimization models are increasingly being used in agricultural planning. However, the inherent uncertainties present in agriculture make it difficult. In recent years, robust optimization has emerged as a methodology that allows dealing with uncertainty in optimization models, even when probabilistic knowledge of the phenomenon is incomplete. In this paper, we consider a wine grape harvesting scheduling optimization problem subject to several uncertainties, such as the actual productivity that can be achieved when harvesting. We study how effective robust optimization is solving this problem in practice. We develop alternative robust models and show results for some test problems obtained from actual wine industry problems.     

A dynamic programming approach to adjustable robust optimization

In this paper we consider the adjustable robust approach to multistage optimization, for which we derive dynamic programming equations. We also discuss this from the point of view of risk averse stochastic programming. We consider as an example a robust formulation of the classical inventory model and show that, like for the risk neutral case, a basestock policy is optimal.     

Enumerating K best paths in length order in DAGs

We address the problem of finding the K best paths connecting a given pair of nodes in a directed acyclic graph (DAG) with arbitrary lengths. One of the main results in this paper is the proof that a tree representing the kth shortest path is obtained by an arc exchange in one of the previous (k − 1) trees (each of which contains a previous best path). An O(m + K(n + log K)) time and O(K + m) space algorithm is designed to explicitly determine the K shortest paths in a DAG with n nodes and m arcs. The algorithm runs in O(m + Kn) time using O(K + m) space in DAGs with integer length arcs. Empirical results confirming the superior performance of the algorithm to others found in the literature for randomly generated graphs are reported.     

A robust approach for modeling limited observability in bilevel optimization

Many applications of bilevel optimization contain a leader facing a follower whose reaction deviates from the one expected by the leader due to some kind of bounded rationality. We consider bilinear bilevel problems with follower's response uncertainty due to limited observability regarding the leader's decision and exploit robust optimization to model the decision making of the follower. We show that the robust counterpart of the lower level allows to tackle the problem via the lower level's KKT conditions.     

A branch and bound algorithm for the robust shortest path problem with interval data

Many real problems can be modelled as robust shortest path problems on interval digraphs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the arc costs.A branch and bound algorithm for this problem is presented.     

The robust shortest path problem in series-parallel multidigraphs with interval data

In this paper the robust shortest path problem in edge series-parallel multidigraphs with interval costs is examined. The maximal regret criterion is applied to calculate the optimal solution. It is shown that this problem is NP-hard. A pseudopolynomial algorithm for the studied problem is constructed.     

A robust optimization approach to closed-loop supply chain network design under uncertainty

The concern about significant changes in the business environment (such as customer demands and transportation costs) has spurred an interest in designing scalable and robust supply chains. This paper proposes a robust optimization model for handling the inherent uncertainty of input data in a closed-loop supply chain network design problem. First, a deterministic mixed-integer linear programming model is developed for designing a closed-loop supply chain network. Then, the robust counterpart of the proposed mixed-integer linear programming model is presented by using the recent extensions in robust optimization theory. Finally, to assess the robustness of the solutions obtained by the novel robust optimization model, they are compared to those generated by the deterministic mixed-integer linear programming model in a number of realizations under different test problems.     

Dense trees: a new look at degenerate graphs

Dense trees are undirected graphs defined as natural extensions of trees. They are already known in the realm of graph coloring under the name of k-degenerate graphs. For a given integer k1, a k-dense cycle is a connected graph, where the degree of each vertex is greater than k. A k-dense forest F=(V,E) is a graph without k-dense cycles as subgraphs. If F is connected, then is a k-dense tree. 1-dense trees are standard trees. We have |E|k|V|−k(k+1)/2. If equality holds F is connected and is called a maximal k-dense tree. k-trees (a subfamily of triangulated graphs) are special cases of maximal k-dense trees.We review the basic theory of dense trees in the family of graphs and show their relation with k-trees. Vertex and edge connectivity is thoroughly investigated, and the role of maximal k-dense trees as “reinforced” spanning trees of arbitrary graphs is presented. Then it is shown how a k-dense forest or tree can be decomposed into a set of standard spanning trees connected through a common “root” of k vertices. All sections include efficient construction algorithms. Applications of k-dense trees in the fields of distributed systems and data structures are finally indicated.     

A decision-theoretic approach to some screening problems

Summary Suppose an item is acceptable if its measurement on the variable of interestY isY≦u. It may be expensive (or impossible) to measureY, and a correlated variableX exists which is relatively inexpensive to measure and is used to screen items, i.e., to declare them acceptable ifX≦w. We examine two situations in both of whichl acceptable items are needed. (i) Before use of the item,Y is measured directly to ensure acceptability: ShouldX be used for screening purposes before theY measurement or not? (ii)Y cannot be measured directly before use, but screening is possible to determine the items that are to be used. We assume thatX andY have a bivariate normal distribution for which the parameters are known. Some comments are made about the case when the parameters are not known.     

A robust approach to the chance-constrained knapsack problem

In this paper, the chance-constrained knapsack problem (CKP) is addressed. Relying on robust optimization, a tractable combinatorial algorithm is proposed to solve approximately CKP. For two specific classes of uncertain knapsack problems, it is proved to solve CKP at optimality.     

Choquet-based optimisation in multiobjective shortest path and spanning tree problems

This paper is devoted to the search of Choquet-optimal solutions in finite graph problems with multiple objectives. The Choquet integral is one of the most sophisticated preference models used in decision theory for aggregating preferences on multiple objectives. We first present a condition on preferences (name hereafter preference for interior points) that characterizes preferences favouring compromise solutions, a natural attitude in various contexts such as multicriteria optimisation, robust optimisation and optimisation with multiple agents. Within Choquet expected utility theory, this condition amounts to using a submodular capacity and a convex utility function. Under these assumptions, we focus on the fast determination of Choquet-optimal paths and spanning trees. After investigating the complexity of these problems, we introduce a lower bound for the Choquet integral, computable in polynomial time. Then, we propose different algorithms using this bound, either based on a controlled enumeration of solutions (ranking approach) or an implicit enumeration scheme (branch and bound). Finally, we provide numerical experiments that show the actual efficiency of the algorithms on multiple instances of different sizes.     

Approximation of min–max and min–max regret versions of some combinatorial optimization problems

This paper investigates, for the first time in the literature, the approximation of min–max (regret) versions of classical problems like shortest path, minimum spanning tree, and knapsack. For a constant number of scenarios, we establish fully polynomial-time approximation schemes for the min–max versions of these problems, using relationships between multi-objective and min–max optimization. Using dynamic programming and classical trimming techniques, we construct a fully polynomial-time approximation scheme for min–max regret shortest path. We also establish a fully polynomial-time approximation scheme for min–max regret spanning tree and prove that min–max regret knapsack is not at all approximable. For a non-constant number of scenarios, in which case min–max and min–max regret versions of polynomial-time solvable problems usually become strongly NP-hard, non-approximability results are provided for min–max (regret) versions of shortest path and spanning tree.     

Integrated production planning and order acceptance under uncertainty: A robust optimization approach

The aim of this paper is to formulate a model that integrates production planning and order acceptance decisions while taking into account demand uncertainty and capturing the effects of congestion. Orders/customers are classified into classes based on their marginal revenue and their level of variability in order quantity (demand variance). The proposed integrated model provides the flexibility to decide on the fraction of demand to be satisfied from each customer class, giving the planner the choice of selecting among the highly profitable yet risky orders or less profitable but possibly more stable orders. Furthermore, when the production stage exceeds a critical utilization level, it suffers the consequences of congestion via elongated lead-times which results in backorders and erodes the firm’s revenue. Through order acceptance decisions, the planner can maintain a reasonable level of utilization and hence avoid increasing delays in production lead times. A robust optimization (RO) approach is adapted to model demand uncertainty and non-linear clearing functions characterize the relationship between throughput and workload to reflect the effects of congestion on production lead times. Illustrative simulation and numerical experiments show characteristics of the integrated model, the effects of congestion and variability, and the value of integrating production planning and order acceptance decisions.     

A robust fuzzy k-means clustering model for interval valued data

Summary  In this paper a robust fuzzy k-means clustering model for interval valued data is introduced. The peculiarity of the proposed model is the capability to manage anomalous interval valued data by reducing the effects of such outliers in the clustering model. In the interval case, the concept of anomalous data involves both the center and the width (the radius) of an interval. In order to show how our model works the results of a simulation experiment and an application to real interval valued data are discussed.     

The complementary convex structure in global optimization

We show the importance of exploiting the complementary convex structure for efficiently solving a wide class of specially structured nonconvex global optimization problems. Roughly speaking, a specific feature of these problems is that their nonconvex nucleus can be transformed into a complementary convex structure which can then be shifted to a subspace of much lower dimension than the original underlying space. This approach leads to quite efficient algorithms for many problems of practical interest, including linear and convex multiplicative programming problems, concave minimization problems with few nonlinear variables, bilevel linear optimization problems, etc...     

The optimistic <Emphasis Type="Italic">TU</Emphasis> game in minimum cost spanning tree problems

We associate an optimistic TU game with each minimum cost spanning tree problem. We define the worth of a coalition S as the cost of connecting agents in S to the source assuming that agents in N\S are already connected to the source, and agents in S can connect through agents in N\S. We study the Shapley value of this new game. We thank Hervé Moulin, William Thomson, and two referees for helpful comments. Financial support from the Ministerio de Ciencia y Tecnologia and FEDER through grant SEJ2005-07637-c02-01 is gratefully acknowledged.     

A simple algorithm to detect balance in signed graphs

We develop a natural correspondence between marked graphs and balanced signed graphs, and exploit it to obtain a simple linear time algorithm by which any signed graph may be tested for balance.     

A parallel search algorithm for directed acyclic graphs

A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)²) whenO(n ^2.81/logn) processors are used.