Industrial Organization Commons^™

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

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 …

A Linear Programming Framework For Logics Of Uncertainty, K. Andersen, John Hooker

John Hooker

Several logics for reasoning under uncertainty distribute “probability mass” over sets in some sense. These include probabilistic logic, Dempster-Shafer theory, other logics based on belief functions, and second-order probabilistic logic. We show that these logics are instances of a certain type of linear programming model, typically with exponentially many variables. We also show how a single linear programming package can implement these logics computationally if one “plugs in” a different column generation subroutine for each logic, although the practicality of this approach has been demonstrated so far only for probabilistic logic.

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

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

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

John Hooker

We describe a modeling framework that integrates mathematical programming (MP), constraint programming (CP) and heuristic methods.

Corruption From A Cross-Cultural Perspective, John Hooker

John Hooker

This paper views corruption as activity that tends to undermine a cultural system. Because cultures operate in very different ways, different activities are corrupting in different parts of the world. The paper analyzes real-life situations in Japan, Taiwan, India, China, North America, sub-Saharan Africa, the Middle East, and Korea to distinguish actions that structurally undermine a cultural system from those that are merely inefficient or are actually supportive. Activities such as nepotism or cronyism that are corrupting in the rule-based cultures of the West may be functional in relationship-based cultures. Behavior that is normal in the West, such as bringing …

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 …

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

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.

Solving The Incremental Satisfiability Problem, John Hooker

John Hooker

Given a set of clauses in propositional logic that have been found satisfiable, we wish to check whether satisfiability is preserved when the clause set is incremented with a new clause. We describe an efficient implementation of the Davis-Putnam-Loveland algorithm for checking the satisfiability of the original set. We then show how to modify the algorithm for efficient solution of the incremental problem, which is NP-complete. We also report computational results.

Resolution And The Integrality Of Satisfiability Problems, John Hooker

John Hooker

No abstract provided.

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?

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

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

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 …

Kant And Cultural Relativism, John N. Hooker

John Hooker

We live an age of cultural relativism that asks how universal moral obligation can be justified. Immanuel Kant took up this challenge. His arguments can be reconstructed in a way that makes sense today

Toward Professional Ethics In Business, John N. Hooker

John Hooker

Before a code of professional ethics can be formulated for business managers, it must be understood why management should be considered a profession and what should be its central mission. This paper proposes answers to these questions

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 …

The Polite And The Rude, John N. Hooker

John Hooker

International managers are aware that business etiquette varies enormously around the world. These minor bits of behavior reflect fundamental differences in culture. By understanding their source, one can not only function with greater confidence but can begin to understand what holds the culture together. Larger behavior patterns that seemed odd or irrational begin to make sense.

Branching Rules For Satisfiability, John N. Hooker, V. Vinay

John Hooker

Recent experience suggests that branching algorithms are among the most attractive for solving propositional satisfiability problems. A key factor in their success is the rule they use to decide on which variable to branch next. We attempt to explain and improve the performance of branching rules with an empirical model-building approach. One model is based on the rationale given for the Jeroslow-Wang rule, variations of which have performed well in recent work. The model is refuted by carefully designed computational experiments. A second model explains the success of the Jeroslow-Wang rule, makes other predictions confirmed by experiment, and leads to …

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

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

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

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

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

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.

Some Business-Related Ethical Issues In Engineering, John Hooker

John Hooker

Engineering has always been related to business, but now more than ever. Engineers are increasingly involved in startup companies in which they make business decisions as well as engineering decisions. Even in large firms, highly integrated product development cycles bring engineers into closer contact with marketing and other business people than in years past. Engineers must now think about ethical issues that were once the province of business managers. In addition, the rapid growth of biotechnology and e-commerce has created a new ethical landscape in which engineers must operate.

The aim here is to examine a few of the issues …

Probabilistic Logic For Belief Nets, K. Andersen, John Hooker

John Hooker

We describe how to combine probabilistic logic and Bayesian networks to obtain a new frame-work ("Bayesian logic") for dealing with uncertainty and causal relationships in an expert system. Probabilistic logic, invented by Boole, is a technique for drawing inferences from uncertain propositions for which there are no independence assumptions. A Bayesian network is a "belief net" that can represent complex conditional independence assumptions. We show how to solve inference problems in Bayesian logic by applying Benders decomposition to a nonlinear programming formulation. We also show that the number of constraints grows only linearly with the problem size for a large …