Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
-
- Integrated optimization methods - Papers (27)
- Logic and optimization (12)
- Ethics and philosophy (6)
- Cross-cultural issues (3)
- Optimization (3)
-
- Constraint programming (2)
- Logic programming. (2)
- Modeling for optimization (2)
- Optimization and decision diagrams (2)
- Algorithms (1)
- Branching (1)
- Cause-effect relationship (1)
- Computational complexity; renamable Horn problems; satisfiability (1)
- Constraint propagation (1)
- Crane scheduling; dynamic programming (1)
- Distributive justice (1)
- Duality (1)
- Feasibility (1)
- Horn clauses. (1)
- Incomplete observations (1)
- Inference (1)
- Integer programming: Benders decomposition; production/scheduling: planning (1)
- Jeroslaw-Wang rule (1)
- Lexicographic maximum (1)
- Linear programming (1)
- Linear programming. (1)
- Logic-based Benders decomposition (1)
- Makespan (1)
- Mathematical programming (1)
- Mixed integer programming (1)
Articles 1 - 30 of 54
Full-Text Articles in Entire DC Network
A Partial Instantiation Based First Order Theorem Prover, Vijay Chandru, John N. Hooker, Anjul Shrivastava, Gabriela Rago
A Partial Instantiation Based First Order Theorem Prover, Vijay Chandru, John N. Hooker, Anjul Shrivastava, Gabriela Rago
John Hooker
Satisfiability algorithms for propositional logic have improved enormously in recent years. This increases the attractiveness of satisfiability methods for first order logic that reduce the problem to a series of ground-level satisfiability problems. Partial Instantiation for first order satisfiability differs radically from standard resolution based methods. Two approaches to partial instantiation based first order theorem provers have been studied by R. Jeroslow and by Plaisted and Zhu. Hooker and Rago have described improvements of Jeroslow's approach by a) extending it to logic with functions b) accelerating it through use of satisfiers as introduced by Gallo and Rago, and c) simplifying …
Predicting Cause-Effect Relationships From Incomplete Discrete Observations, E Boros, P. L. Hammer, John N. Hooker
Predicting Cause-Effect Relationships From Incomplete Discrete Observations, E Boros, P. L. Hammer, John N. Hooker
John Hooker
This paper addresses a prediction problem occurring frequently in practice. The problem consists in predicting the value of a function on the basis of discrete observational data that are incomplete in two senses. Only certain arguments of the function are observed, and the function value is observed only for certain combinations of values of these arguments. The problem is considered under a monotonicity condition that is natural in many applications. Applications to tax auditing, medicine, and real estate valuation are discussed. In particular, a special class of problems is identified for which the best monotone prediction can be found in …
Partial Instantiation Methods For Inference In First-Order Logic, John N. Hooker, G. Rago, V. Chandru, A. Shrivastava
Partial Instantiation Methods For Inference In First-Order Logic, John N. Hooker, G. Rago, V. Chandru, A. Shrivastava
John Hooker
Satisfiability algorithms for propositional logic have improved enormously in recently years. This improvement increases the attractiveness of satisfiability methods for first-order logic that reduce the problem to a series of ground-level satisfiability problems. R. Jeroslow introduced a partial instantiation method of this kind that differs radically from the standard resolution-based methods. This paper lays the theoretical groundwork for an extension of his method that is general enough and efficient enough for general logic programming with indefinite clauses. In particular we improve Jeroslow's approach by (1) extending it to logic with functions, (2) accelerating it through the use of satisfiers, as …
Boolean Regression, E. Boros, P. L. Hammer, John N. Hooker
Boolean Regression, E. Boros, P. L. Hammer, John N. Hooker
John Hooker
We take a regression-based approach to the problem of induction, which is the problem of inferring general rules from specific instances. Whereas traditional regression analysis fits a numerical formula to data, we fit a logical formula to boolean data. We can, for instance, construct an expert system for fitting rules to an expert's observed behavior. A regression-based approach has the advantage of providing tests of statistical significance as well as other tools of regression analysis. Our approach can be extended to nonboolean discrete data, and we argue that it is better suited to rule construction than logit and other types …
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.
A Systematic Approach To Mdd-Based Constraint Programming, Samid Hoda, Willem-Jan Van Hoeve, John N. Hooker
A Systematic Approach To Mdd-Based Constraint Programming, Samid Hoda, Willem-Jan Van Hoeve, John N. Hooker
John Hooker
Fixed-width MDDs were introduced recently as a more refined alternative for the domain store to represent partial solutions to CSPs. In this work, we present a systematic approach to MDD-based constraint programming. First, we introduce a generic scheme for constraint propagation in MDDs. We show that all previously known propagation algorithms for MDDs can be expressed using this scheme. Moreover, we use the scheme to produce algorithms for a number of other constraints, including Among, Element, and unary resource constraints. Finally, we discuss an implementation of our MDD-based CP solver, and provide experimental evidence of the benefits of MDD-based constraint …
Optimization Methods In Logic, John N. Hooker
Optimization Methods In Logic, John N. Hooker
John Hooker
Optimization can make at least two contributions to boolean logic. Its solution methods can address inference and satisfiability problems, and its style of analysis can reveal tractable classes of boolean problems that might otherwise have gone unnoticed.
Optimality Conditions For Distributive Justice, John N. Hooker
Optimality Conditions For Distributive Justice, John N. Hooker
John Hooker
This paper uses optimization theory to address a fundamental question of ethics: how to divide resources justly among individuals, groups, or organizations. It formulates utilitarian and Rawlsian criteria for distributive justice as optimization problems. The formulations recognize that some recipients are more productive than others, so that an inequitable distribution may create greater overall utility. Conditions are derived under which a distribution of resources is utility maximizing, and under which it achieves a lexicographic maximum, which we take as formulating the difference principle of John Rawls. It is found that utility maximization requires at least as much inequality as results …
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 …
Mathematical Programming Methods For Reasoning Under Uncertainty, John N. Hooker
Mathematical Programming Methods For Reasoning Under Uncertainty, John N. Hooker
John Hooker
We survey three applications of mathematical programming to reasoning under uncertainty: a) an application of linear programming to probabilistic logic, b) an application of nonlinear programming to Bayesian logic, a combination of Bayesian inference with probabilistic logic and c) an application of integer programming to Dempster-Shafer theory, which is a method of combining evidence from diffierent sources
A Cross-Cultural View Of Corruption, John N. Hooker
A Cross-Cultural View Of Corruption, John N. Hooker
John Hooker
The world is shrinking, but its cultures remain worlds apart, as do its ethical norms. The West views bribery, kickbacks, cronyism and nepotism as unethical, but they are standard practice in many parts of the world. This poses a familiar dilemma for business firms that operate globally: should they engage in what they see as corrupt behavior in order to do business? The position defended here is that firms should always resist corruption, but at the same time understand it from a broader perspective: as behavior that undermines a cultural system. Behavior that is acceptable in one country may be …
A Generalized Dilworth's Theorem, With Application To Routing And Scheduling, John N. Hooker, N R. Natraj
A Generalized Dilworth's Theorem, With Application To Routing And Scheduling, John N. Hooker, N R. Natraj
John Hooker
Dilworth's theorem states a duality relation between minimum chain decompositions of a directed, acyclic graph and maximum antichains. We generalize the theorem to apply when the chains of the decomposition are required to contain the chains of an initial decomposition. We show that duality obtains precisely when an associated undirected graph is perfect. We apply this result to a vehicle routing and scheduling problem with time windows. Here each chain of the initial decomposition contains nodes that correspond to the pickup, delivery and possibly intermediate stops associated with a piece of cargo.
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 …
Logical Inference And Polyhedral Projection, John N. Hooker
Logical Inference And Polyhedral Projection, John N. Hooker
John Hooker
We explore connections between polyhedral projection and inference in propositional logic. We formulate the problem of drawing all inferences that contain a restricted set of atoms (i.e., all inferences that pertain to a given question) as a logical projection problem. We show that polyhedral projection partially solves this problem and in particular derives precisely those inferences that can be obtained by a certain form of unit resolution. We prove that this unit resolution algorithm is exponential in the number of atoms in the restricted set but is polynomial in the problem size when this number of fixed. We also survey …
Graph Coloring Facets From All-Different Systems, David Bergman, John N. Hooker
Graph Coloring Facets From All-Different Systems, David Bergman, John N. Hooker
John Hooker
We explore the idea of obtaining valid inequalities for a 0-1 model from a constraint programming formulation of the problem. In particular, we formulate a graph coloring problem as a system of all-different constraints. By analyzing the polyhedral structure of all-diff systems, we obtain facet-defining inequalities that can be mapped to valid cuts in the classical 0-1 model of the problem. We focus on cuts corresponding to cyclic structures and show that they are stronger than known cuts. For example, when an existing separation algorithm identifies odd hole cuts, we can supply stronger cuts with no additional calculation. In addition, …
Mixed Logical Linear Programming, John N. Hooker, Maria A. Osorio
Mixed Logical Linear Programming, John N. Hooker, Maria A. Osorio
John Hooker
Abstract: "Mixed logical/linear programming (MLLP) is an extension of mixed integer/linear programming (MLLP). It represents 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 and disadvantages of MLLP and illustrates some of them with computational experiments."
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.
Hybrid Modeling, John N. Hooker
Hybrid Modeling, John N. Hooker
John Hooker
The modeling practices of constraint programming (CP), artificial intelligence, and operations research must be reconciled and integrated if the computational benefits of combining their solution methods are to be realized in practice. This chapter focuses on CP and mixed integer/linear programming (MILP), in which modeling systems are most highly developed. It presents practical guidelines and supporting theory for the two types of modeling. It then suggests how an integrated modeling framework can be designed that retains, and even enhances, the modeling power of CP while allowing the full computational resources of both fields to be applied and combined. A series …
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 …
Logic Cuts For Processing Networks With Fixed Charges, John N. Hooker, Carnegie Mellon University.Engineering Design Research Center.
Logic Cuts For Processing Networks With Fixed Charges, John N. Hooker, Carnegie Mellon University.Engineering Design Research Center.
John Hooker
Abstract: "We show how some simple logical constraints can substantially accelerate the solution of mixed integer linear programming (MILP) models for the design of chemical processing networks. These constraints are easily generated in a preprocessing stage and can be applied either symbolically during a branch-and-bound search or as constraints in the MILP model. Furthermore, they represent a new class of cuts, 'logic cuts,' that generalize traditional cutting planes. A logic cut can cut off feasible points but does not change the optimal solution. We establish some elementary properties of logic cuts and use them to show that our logical constraints …
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.
Tight Representation Of Logical Constraints As Cardinality Rules, John N. Hooker, Hong Yan, Carnegie Mellon University.Engineering Design Research Center.
Tight Representation Of Logical Constraints As Cardinality Rules, John N. Hooker, Hong Yan, Carnegie Mellon University.Engineering Design Research Center.
John Hooker
Abstract: "We address the problem of finding a 'tight' representation of complex logical constraints in a mixed integer programming model by describing a convex hull representation of cardinality rules. A cardinality rule asserts that if at least k of the propositions AΓéü,...,A[subscript m] are true, then at least l of the propositions BΓéü,...,B[subscript n] are true."
A Declarative Modeling Framework That Integrates Solution Methods, John N. Hooker, Hak-Jin Kim, G. Ottosson
A Declarative Modeling Framework That Integrates Solution Methods, John N. Hooker, Hak-Jin Kim, G. Ottosson
John Hooker
Constraint programming offers modeling features and solution methods that are unavailable in mathematical programming but are often flexible and efficient for scheduling and other combinatorial problems. Yet mathematical programming is well suited to declarative modeling languages and is more efficient for some important problem classes. This raises this issue as to whether the two approaches can be combined in a declarative modeling framework. This paper proposes a general declarative modeling system in which the conditional structure of the constraints shows how to integrate any "checker" and any special-purpose "solver". In particular this integrates constraint programming and optimization methods, because the …
Manipulating Mdd Relaxations For Combinatorial Optimization, David Bergman, Willem-Jan Van Hoeve, John N. Hooker
Manipulating Mdd Relaxations For Combinatorial Optimization, David Bergman, Willem-Jan Van Hoeve, John N. Hooker
John Hooker
We study the application of limited-width MDDs (multi-valued decision diagrams) as discrete relaxations for combinatorial optimization problems. These relaxations are used for the purpose of generating lower bounds. We introduce a new compilation method for constructing such MDDs, as well as algorithms that manipulate the MDDs to obtain stronger relaxations and hence provide stronger lower bounds. We apply our methodology to set covering problems, and evaluate the strength of MDD relaxations to relaxations based on linear programming. Our experimental results indicate that the MDD relaxation is particularly effective on structured problems, being able to outperform state-of-the-art integer programming technology by …
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.
Cultural Differences In Business Communication, John N. Hooker
Cultural Differences In Business Communication, John N. Hooker
John Hooker
There is no better arena for observing a culture in action than business. Cultures tend to reveal themselves in situations where much is as stake, because it is here that their resources are most needed. Marriage, family obligations, and such stressful experiences as illness and the death of a loved one bring out much of what is distinctive and fundamental in a culture. The same is true of business, because economic survival is at stake. Business practices are shaped by deeply-held cultural attitudes toward work, power, trust, wealth—and communication.
Why Business Ethics?, John N. Hooker
Why Business Ethics?, John N. Hooker
John Hooker
Everyone agrees that business managers must understand finance and marketing. But is it necessary for them to study ethics?