In recent years the use of decision diagrams within the context of discrete optimization has proliferated. This paper continues this expansion by proposing the use of decision diagrams for modeling and solving binary ...
详细信息
In recent years the use of decision diagrams within the context of discrete optimization has proliferated. This paper continues this expansion by proposing the use of decision diagrams for modeling and solving binary optimization problems with quadratic constraints. The model proposes the use of multiple decision diagrams to decompose a quadratic matrix so that each individual diagram has provably limited size. The decision diagrams are then linked through channeling constraints to ensure that the solution represented is consistent across the decision diagrams and that the original quadratic constraints are satisfied. The resulting family of decision diagrams are optimized over by a dedicated cutting-plane algorithm akin to Benders decomposition. The approach is general, in that commercial integer programming solvers can readily apply the technique. A thorough experimental evaluation on both benchmark and synthetic instances exhibits that the proposed decision diagram reformulation provides significant improvements over current methods for quadratic constraints in state-of-the-art solvers.
The application of decision diagrams in combinatorial optimization has proliferated in the last decade. In recent years, authors have begun to investigate how to use not one, but a set of diagrams, to model constraint...
详细信息
The application of decision diagrams in combinatorial optimization has proliferated in the last decade. In recent years, authors have begun to investigate how to use not one, but a set of diagrams, to model constraints and objective function terms. Optimizing over a collection of decision diagrams, the problem we refer to as the consistent path problem (CPP) can be addressed by associating a network-flow model with each decision diagram, jointly linked through channeling constraints. A direct application of integer programming to the ensuing model has already been shown to result in algorithms that provide orders-of-magnitude performance gains over classical methods. Lacking, however, is a careful study of dedicated solution methods designed to solve the CPP. This paper provides a detailed study of the CPP, including a discussion on complexity results and a complete polyhedral analysis. We propose a cut-generation algorithm, which, under a structured ordering property, finds a cut, if one exists, through an application of the classical maximum flow problem, albeit in an exponentially sized network. We use this procedure to fuel a cutting-plane algorithm that is applied to unconstrained binary cubic optimization and a variant of the market split problem, resulting in an algorithm that compares favorably with CPLEX, using standard integer programming formulations for both problems.
We present approximation algorithms for integrated logistics problems that combine elements of facility location and transport network design. We first study the problem where opening facilities incurs opening costs a...
详细信息
We present approximation algorithms for integrated logistics problems that combine elements of facility location and transport network design. We first study the problem where opening facilities incurs opening costs and transportation from the clients to the facilities incurs buy-at-bulk costs, and provide a combinatorial approximation algorithm. We also show that the integer-programming formulation of this problem has small integrality gap. We extend the model to the version when there is a bound on the number of facilities that may be opened.
Two continuous time formulations of the dynamic traffic assignment problem are considered, one that corresponds to system optimization and the other to a version of user optimization on a single mode network using opt...
详细信息
Two continuous time formulations of the dynamic traffic assignment problem are considered, one that corresponds to system optimization and the other to a version of user optimization on a single mode network using optimal control theory. Pontryagin's necessary conditions are analyzed and given economic interpretations that correspond to intuitive notions regarding dynamic system optimized and dynamic user optimized traffic flow patterns. Notably, we offer the first dynamic generalization of Beckmann's equivalent optimization problem for static user optimized traffic assignment in the form of an optimal control problem. The analysis further establishes that a constraint qualification and convexity requirements for the Hamiltonian, which together ensure that the necessary conditions are also sufficient, are satisfied under commonly encountered regularity conditions.
Due to the combinatorial nature of the facility layout problem, current heuristic computer procedures do not always provide better solutions than visual methods. A new algorithm, FLAC (Facility Layout by Analysis of C...
详细信息
Due to the combinatorial nature of the facility layout problem, current heuristic computer procedures do not always provide better solutions than visual methods. A new algorithm, FLAC (Facility Layout by Analysis of Clusters), is described which emulates the visual methods used by industrial engineers in solving facility layout problems. Initially side-stepping the combinatorial nature of the problem, FLAC is found to perform well in problems with high as well as low flow dominance, and in the presence and absence of line dominance. Computation time is attractive, especially on larger problems.
This paper presents an algorithm for determining the optimal allocation to demand points when the distribution system is a capacitated arborescence of N arcs and the cost (return) functions are convex (concave). It is...
详细信息
This paper presents an algorithm for determining the optimal allocation to demand points when the distribution system is a capacitated arborescence of N arcs and the cost (return) functions are convex (concave). It is proved that the algorithm generates an optimal solution by solving at most N(N + 1)/2 single-constraint subproblems. If the cost functions allow the Lagrange multiplier for the subproblems to be evaluated in polynomial time, then this is a polynomial algorithm. The analysis is motivated by the problem of allocating spare capacity in the loop plant portion of telephone networks.
暂无评论