Open Access. Powered by Scholars. Published by Universities.®
- File Type
Articles 1 - 26 of 26
Full-Text Articles in Industrial Organization
A Relaxation Of The Cumulative Constraint, John N. Hooker, Hong Yan
A Relaxation Of The Cumulative Constraint, John N. Hooker, Hong Yan
John Hooker
Hybrid methods that combine constraint programming with mathematical programming make essential use of continuous relaxations for global constraints. We state a relaxation for the cumulative constraint. In particular we identify facet-defining inequalities for problems in which some jobs have the same duration, release time, and resource consumption rate. We also identify a much larger class of valid inequalities that exist in all problems.
A Hybrid Method For Planning And Scheduling, John N. Hooker
A Hybrid Method For Planning And Scheduling, John N. Hooker
John Hooker
We combine mixed integer linear programming (MILP) and constraint programming (CP) to solve planning and scheduling problems. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. Tasks assigned to a facility may run in parallel subject to resource constraints (cumulative scheduling). We solve minimum cost problems, as well as minimum makespan problems in which all tasks have the same release date and deadline. We obtain computational speedups of several orders of magnitude relative to the state of the art in both MILP and CP.
Inference-Based Sensitivity Analysis For Mixed Integer/Linear Programming, M. W. Dawande, John N. Hooker
Inference-Based Sensitivity Analysis For Mixed Integer/Linear Programming, M. W. Dawande, John N. Hooker
John Hooker
A new method of sensitivity analysis for mixed integer/linear programming (MILP) is derived from the idea of inference duality. The inference dual of an optimization problem asks how the optimal value can be deduced from the constraints. In MILP, a deduction based on the resolution method oftheorem proving can be obtained from the branch-and-cut tree that solves the primal problem. One can then investigate which perturbations ofthe problem leave this proof intact. On this basis it is shown that, in a minimization problem, any perturbation that satisfies a certain system of linear inequalities will reduce the optimal value no more …
Solving The Capacitated Local Access Network Design Problem, F. Sibel Salman, R. Ravi, John N. Hooker
Solving The Capacitated Local Access Network Design Problem, F. Sibel Salman, R. Ravi, John N. Hooker
John Hooker
We propose an exact solution method for a routing and capacity installation problem in networks. Given an input graph, the problem is to route traffic from a set of source nodes to a sink node and to install transmission facilities on the edges of the graph to accommodate the flow at minimum cost. We give a branch-and-bound algorithm that solves relaxations obtained by approximating the noncontinuous cost function by its lower convex envelope. The approximations are refined by branching on the flow ranges on selected edges. Our computational experiments indicate that this method is effective in solving moderate-size problems and …
A Search-Infer-And-Relax Framework For Integrating Solution Methods, John N. Hooker
A Search-Infer-And-Relax Framework For Integrating Solution Methods, John N. Hooker
John Hooker
We present an algorithmic framework for integrating solution methods that is based on search, inference, and relaxation and their interactions. We show that the following are special cases: branch and cut, CP domain splitting with propagation, popular global optimization methods, DPL methods for SAT with conflict clauses, Benders decomposition and other nogood-based methods, partial-order dynamic backtracking, various local search metaheuristics, and GRASPs (greedy randomized adaptive search procedures). The framework allows elements of different solution methods to be combined at will, resulting in a variety of integrated methods. These include continuous relaxations for global constraints, the linking of integer and constraint …
Planning And Scheduling To Minimize Tardiness, John N. Hooker
Planning And Scheduling To Minimize Tardiness, John N. Hooker
John Hooker
We combine mixed integer linear programming (MILP) and constraint programming (CP) to minimize tardiness in planning and scheduling. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. We consider two objectives: minimizing the number of late tasks, and minimizing total tardiness. Our main theoretical contribution is a relaxation of the cumulative scheduling subproblem, which is critical to performance. We obtain substantial computational speedups relative to the state of the art in both MILP and CP. We also obtain much better solutions for problems that cannot be solved to optimality.
Optimal Design Of Truss Structures By Logic-Based Branch And Cut, S. Bollapragada, Omar Ghattas, John Hooker
Optimal Design Of Truss Structures By Logic-Based Branch And Cut, S. Bollapragada, Omar Ghattas, John Hooker
John Hooker
The truss design problem is to find the optimal placement and size of structural bars that can support a given load. The problem is nonlinear and, in the version addressed here, the bars must take certain discrete sizes. It is shown that a logic-based method that dispenses with integer variables and branches directly on logical disjunctions can solve substantially larger problems than mixed integer programming, even though the nonlinearities disappear in the mixed integer model. A primary purpose of the paper is to investigate whether advantages of logic-based branching that have been demonstrated elsewhere for linear problems extend to nonlinear …
Mixed Logical-Linear Programming, John Hooker, M. Osorio
Mixed Logical-Linear Programming, John Hooker, M. Osorio
John Hooker
Mixed logical/linear programming (MLLP) is an extension of mixed integer/linear programming (MILP). It can represent the discrete elements of a problem with logical propositions and provides a more natural modeling framework than MILP. It can also have computational advantages, partly because it eliminates integer variables when they serve no purpose, provides alternatives to the traditional continuous relaxation, and applies logic processing algorithms. This paper surveys previous work and attempts to organize ideas associated with MLLP, some old and some new, into a coherent framework. It articulates potential advantages of MLLP's wider choice of modeling and solution options and illustrates some …
Good And Bad Futures For Constraint Programming (And Operations Research), John Hooker
Good And Bad Futures For Constraint Programming (And Operations Research), John Hooker
John Hooker
Two futures are sketched for constraint programming and operations research. In one, they continue their present emphasis on computational methods. In the other, they are empirical sciences dedicated to prescriptive modeling of human activities, with computation playing an ancillary role. The second future is defended as one in which the two fields, which are at root one field, maintain their vitality and make a more effective contribution to solving the problems of an increasingly complex world.
Inference Duality As A Basis For Sensitivity Analysis, John N. Hooker
Inference Duality As A Basis For Sensitivity Analysis, John N. Hooker
John Hooker
The constraint programming community has recently begun to address certain types of optimization problems. These problems tend to be discrete or to have discrete elements. Although sensitivity analysis is well developed for continuous problems, progress in this area for discrete problems has been limited. This paper proposes a general approach to sensitivity analysis that applies to both continuous and discrete problems. In the continuous case, particularly in linear programming, sensitivity analysis can be obtained by solving a dual problem. One way to broaden this result is to generalize the classical idea of a dual to that of an ldquoinference dual,rdquo …
Planning And Scheduling By Logic-Based Benders Decomposition, John N. Hooker
Planning And Scheduling By Logic-Based Benders Decomposition, John N. Hooker
John Hooker
We combine mixed-integer linear programming (MILP) and constraint programming (CP) to solve an important class of planning and scheduling problems. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. Tasks assigned to a facility may run in parallel subject to resource constraints (cumulative scheduling). We solve problems in which the objective is to minimize cost, makespan, or total tardiness. We obtain significant computational speedups, of several orders of magnitude for the first two objectives, relative to the state of the art in both MILP and CP. We also obtain …
Simpl: A System For Integrating Optimization Techniques, Ionuţ Aron, John Hooker, Tallys Yunes
Simpl: A System For Integrating Optimization Techniques, Ionuţ Aron, John Hooker, Tallys Yunes
John Hooker
In recent years, the Constraint Programming (CP) and Operations Research (OR) communities have explored the advantages of combining CP and OR techniques to formulate and solve combinatorial optimization problems. These advantages include a more versatile modeling framework and the ability to combine complementary strengths of the two solution technologies. This research has reached a stage at which further development would benefit from a general-purpose modeling and solution system. We introduce here a system for integrated modeling and solution called SIMPL. Our approach is to view CP and OR techniques as special cases of a single method rather than as separate …
On Integrating Constraint Propagation And Linear Programming For Combinatorial Optimization, John N. Hooker, Greger Ottosson, Erlendur S. Thorsteinsson, Hak-Jin Kim
On Integrating Constraint Propagation And Linear Programming For Combinatorial Optimization, John N. Hooker, Greger Ottosson, Erlendur S. Thorsteinsson, Hak-Jin Kim
John Hooker
Linear programming and constraint propagation are complementary techniques with the potential for integration to benefit the solution of combinatorial optimization problems.
A Framework For Integrating Solution Methods, John Hooker
A Framework For Integrating Solution Methods, John Hooker
John Hooker
We describe a modeling framework that integrates mathematical programming (MP), constraint programming (CP) and heuristic methods.
An Integrated Method For Planning And Scheduling To Minimize Tardiness, John N. Hooker
An Integrated Method For Planning And Scheduling To Minimize Tardiness, John N. Hooker
John Hooker
We combine mixed integer linear programming (MILP) and constraint programming (CP) to minimize tardiness in planning and scheduling. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. We consider two objectives: minimizing the number of late tasks, and minimizing total tardiness. Our main theoretical contribution is a relaxation of the cumulative scheduling subproblem, which is critical to performance. We obtain substantial computational speedups relative to the state of the art in both MILP and CP. We also obtain much better solutions for problems that cannot be solved to optimality.
Logic-Based Benders Decomposition, John Hooker, G. Ottosson
Logic-Based Benders Decomposition, John Hooker, G. Ottosson
John Hooker
Benders decomposition uses a strategy of “learning from one’s mistakes.” The aim of this paper is to extend this strategy to a much larger class of problems. The key is to generalize the linear programming dual used in the classical method to an “inference dual.” Solution of the inference dual takes the form of a logical deduction that yields Benders cuts. The dual is therefore very different from other generalized duals that have been proposed. The approach is illustrated by working out the details for propositional satisfiability and 0-1 programming problems. Computational tests are carried out for the latter, but …
Logic-Based Methods For Optimization, John N. Hooker
Logic-Based Methods For Optimization, John N. Hooker
John Hooker
This tutorial describes a logic-based approach to formulating and solving pure and mixed integer programming problems. It develops logical counterparts for ideas associated with traditional branch-and-cut methods, such as cutting planes, facet-defining cuts, relaxations, etc. The motivations for doing this are a) to exploit the structure of a wide range of problems that are too complex for polyhedral analysis, b) to take advantage of logic processing techniques developed for constraint programming and logic programming, and c) to provide a unified approach to solving the growing number of problems with both qualitative and quantitative elements
Convex Programming Methods For Global Optimization, John N. Hooker
Convex Programming Methods For Global Optimization, John N. Hooker
John Hooker
We investigate some approaches to solving nonconvex global optimization problems by convex nonlinear programming methods. We assume that the problem becomes convex when selected variables are fixed. The selected variables must be discrete, or else discretized if they are continuous. We provide a survey of disjunctive programming with convex relaxations, logic-based outer approximation, and logic-based Benders decomposition. We then introduce a branch-and-bound method with convex quasi-relaxations (BBCQ) that can be effective when the discrete variables take a large number of real values. The BBCQ method generalizes work of Bollapragada, Ghattas and Hooker on structural design problems. It applies when the …
Solving Fixed-Charge Network Flow Problems With A Hybrid Optimization And Constraint Programming Approach, Hak-Jin Kim, John N. Hooker
Solving Fixed-Charge Network Flow Problems With A Hybrid Optimization And Constraint Programming Approach, Hak-Jin Kim, John N. Hooker
John Hooker
We apply to fixed charge network flow (FCNF) problems a general hybrid solution method that combines constraint programming and linear programming. FCNF problems test the hybrid approach on problems that are already rather well suited for a classical 0–1 model. They are solved by means of a global constraint that generates specialized constraint propagation algorithms and a projected relaxation that can be rapidly solved as a minimum cost network flow problem. The hybrid approach ran about twice as fast as a commercial mixed integer programming code on fixed charge transportation problems with its advantage increasing with problem size. For general …
A Constraint Store Based On Multivalued Decision Diagrams, H R. Andersen, Tarik Hadzic, John N. Hooker, Peter Tiedemann
A Constraint Store Based On Multivalued Decision Diagrams, H R. Andersen, Tarik Hadzic, John N. Hooker, Peter Tiedemann
John Hooker
The typical constraint store transmits a limited amount of information because it consists only of variable domains. We propose a richer constraint store in the form of a limited-width multivalued decision diagram (MDD). It reduces to a traditional domain store when the maximum width is one but allows greater pruning of the search tree for larger widths. MDD propagation algorithms can be developed to exploit the structure of particular constraints, much as is done for domain filtering algorithms.We propose specialized propagation algorithms for alldiff and inequality constraints. Preliminary experiments show that MDD propagation solves multiple alldiff problems an order of …
Cost-Bounded Binary Decision Diagrams For 0-1 Programming, Tarik Hadzic, John N. Hooker
Cost-Bounded Binary Decision Diagrams For 0-1 Programming, Tarik Hadzic, John N. Hooker
John Hooker
In recent work binary decision diagrams (BDDs) were introduced as a technique for postoptimality analysis for integer programming. In this paper we show that much smaller BDDs can be used for the same analysis by employing cost bounding techniques in their construction.
A Filter For The Circuit Constraint, Latife Genç-Kaya, John N. Hooker
A Filter For The Circuit Constraint, Latife Genç-Kaya, John N. Hooker
John Hooker
We present an incomplete filtering algorithm for the circuit constraint. The filter removes redundant values by eliminating nonhamiltonian edges from the associated graph. We identify nonhamiltonian edges by analyzing a smaller graph with labeled edges that is defined on a separator of the original graph. The complexity of the procedure for each separator S is approximately O(|S|5).We found that it identified all infeasible instances and eliminated about one-third of the redundant domain elements in feasible instances.
Succinct Relaxations For Some Discrete Problems, John N. Hooker, Hak-Jin Kim
Succinct Relaxations For Some Discrete Problems, John N. Hooker, Hak-Jin Kim
John Hooker
A discrete problem can be relaxed by taking the continuous relaxation of an integer programming formulation. An equivalent relaxation is obtained by projecting this relaxation onto the original continuous variables. The projection is simple for piecewise linear functions, fixed charge problems and some disjunctive constraints. This allows one to solve much smaller relaxations without sacrificing the quality of bounds. In particular the projected relaxations for some classical network design and warehouse location problems are minimum cost network ow problems, a fact that can dramatically accelerate their solution.
Duality In Optimization And Constraint Satisfaction, John N. Hooker
Duality In Optimization And Constraint Satisfaction, John N. Hooker
John Hooker
We show that various duals that occur in optimization and constraint satisfaction can be classified as inference duals, relaxation duals, or both. We discuss linear programming, surrogate, Lagrangean, superadditive, and constraint duals, as well as duals defined by resolution and filtering algorithms. Inference duals give rise to nogood-based search methods and sensitivity analysis, while relaxation duals provide bounds. This analysis shows that duals may be more closely related than they appear, as are surrogate and Lagrangean duals. It also reveals common structure between solution methods, such as Benders decomposition and Davis-Putnam-Loveland methods with clause learning. It provides a framework for …
Mixed Global Constraints And Inference In Hybrid Clp-Ip Solvers, Greger Ottosson, Erlendur Thorsteinsson, John Hooker
Mixed Global Constraints And Inference In Hybrid Clp-Ip Solvers, Greger Ottosson, Erlendur Thorsteinsson, John Hooker
John Hooker
The complementing strengths of Constraint (Logic) Programming (CLP) and Mixed Integer Programming (IP) have recently received significant attention. Although various optimization and constraint programming packages at a first glance seem to support mixed models, the modeling and solution techniques encapsulated are still rudimentary. Apart from exchanging bounds for variables and objective, little is known of what constitutes a good hybrid model and how a hybrid solver can utilize the complementary strengths of inference and relaxations. This paper adds to the field by identifying constraints as the essential link between CLP and IP and introduces an algorithm for bidirectional inference through …
Propagating Separable Equalities In An Mdd Store, Tarik Hadzic, John N. Hooker, Peter Tiedemann
Propagating Separable Equalities In An Mdd Store, Tarik Hadzic, John N. Hooker, Peter Tiedemann
John Hooker
We present a propagator that achieves MDD consistency for a separable equality over an MDD (multivalued decision diagram) store in pseudo-polynomial time.We integrate the propagator into a constraint solver based on an MDD store introduced in [1]. Our experiments show that the new propagator provides substantial computational advantage over propagation of two inequality constraints, and that the advantage increases when the maximum width of the MDD store increases.