Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Integrated optimization methods - Papers (19)
- Logic and optimization (11)
- Ethics and philosophy (6)
- Cross-cultural issues (3)
- Optimization (2)
-
- Algorithms (1)
- Branching (1)
- Cause-effect relationship (1)
- Computational complexity; renamable Horn problems; satisfiability (1)
- Constraint programming (1)
- Constraint propagation (1)
- Distributive justice (1)
- Duality (1)
- Incomplete observations (1)
- Inference (1)
- Integer programming: Benders decomposition; production/scheduling: planning (1)
- Jeroslaw-Wang rule (1)
- Lexicographic maximum (1)
- Linear programming (1)
- Mathematical programming (1)
- Modeling for optimization (1)
- Modeling language (1)
- Monotone regression (1)
- Network design; routing flow; capacity installation; branch and bound (1)
- Nonlinear programming (1)
- Optimization and decision diagrams (1)
- Optimization method (1)
- Primal–dual strategy (1)
- Rawlsian ethics (1)
- Satisfiability (1)
Articles 31 - 42 of 42
Full-Text Articles in Economics
New Methods For Computing Inferences In First Order Logic, John N. Hooker
New Methods For Computing Inferences In First Order Logic, John N. Hooker
John Hooker
Recent improvements in satisfiability algorithms for propositional logic have made partial instantiation methods for first order predicate logic computationally more attractive. Two such methods have been proposed, one by Jeroslow and a hypergraph method for datalog formulas by Gallo and Rago. We show that they are instances of two general approaches to partial instantiation, and we develop these approaches for a large decidable fragment of first order logic (the ∃∀ fragment).
A Postmodern Critique Of Artificial Intelligence, John N. Hooker
A Postmodern Critique Of Artificial Intelligence, John N. Hooker
John Hooker
I argue that the "postmodern" understanding of language that has developed over the last few decades in Anglo-American philosophy provides the basis for a useful critique of artificial intelligence. This postmodern view corrects an error in the traditional Western conception of language that has led many researchers in AI and cognitive science into taking a rule-based or information-processing approach. Wittgenstein's view that language does not receive its meaning through definition, and Quine's view that neither words nor sentences but only discourse as a whole is the proper unit of meaning, argue against an attempt to formulate rules for understanding language, …
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 …
Determining Lower And Upper Bounds On Probabilities Of Atomic Propositions In Sets Of Logical Formulas Represented By Digraphs, K. A. Andersen, John N. Hooker
Determining Lower And Upper Bounds On Probabilities Of Atomic Propositions In Sets Of Logical Formulas Represented By Digraphs, K. A. Andersen, John N. Hooker
John Hooker
In this paper we consider the problem of determining lower and upper bounds on probabilities of atomic propositions in sets of logical formulas represented by digraphs. We establish a sharp upper bound, as well as a lower bound that is not in general sharp. We show further that under a certain condition the lower bound is sharp. In that case, we obtain a closed form solution for the possible probabilities of the atomic propositions.
Professional Ethics: Does It Matter Which Hat We Wear?, John N. Hooker
Professional Ethics: Does It Matter Which Hat We Wear?, John N. Hooker
John Hooker
Can two professions impose contradictory obligations? If so, how can both be right? What is professional ethics, anyway, as distinguished from ethics in general?
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 …
Detecting Embedded Horn Structure In Propositional Logic, V. Chandru, John N. Hooker
Detecting Embedded Horn Structure In Propositional Logic, V. Chandru, John N. Hooker
John Hooker
We show that the problem of finding a maximum renamable Horn problem within a propositional satisfiability problem is NP-hard but can be formulated as a set packing and therefore a maximum clique problem, for which numerous algorithms and heuristics have been developed.
Postoptimality Analysis For Integer Programming Using Binary Decision Diagrams, Tarik Hadzic, John N. Hooker
Postoptimality Analysis For Integer Programming Using Binary Decision Diagrams, Tarik Hadzic, John N. Hooker
John Hooker
We show how binary decision diagrams (BDDs) can be used to solve and obtain postoptimality analysis for linear and nonlinear integer programming problems with binary or general integer variables. The constraint set corresponds to a unique reduced BDD that represents all feasible or near-optimal solutions, and in which optimal solutions correspond to certain shortest paths. The BDD can be queried in real time for in-depth postoptimality reasoning. The approach is equally effective for linear and nonlinear problems. There are currently no other methods for obtaining such an analysis, short of repeatedly re-solving the problem. We illustrate the analysis on capital …
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.