Browsing by Author "Hnich, Brahim"

Now showing 1 - 20 of 27

Citation - WoS: 5
Citation - Scopus: 13
Among, Common and Disjoint Constraints
(Springer-Verlag Berlin, 2006) Bessiere, Christian; Hebrard, Emmanuel; Hnich, Brahim; Kiziltan, Zeynep; Walsh, Toby
AMONG, COMMON and DISJOINT are global constraints useful in modelling problems involving resources. We study a number of variations of these constraints over integer and set variables. We show how computational complexity can be used to determine whether achieving the highest level of consistency is tractable. For tractable constraints, we present a polynomial propagation algorithm and compare it to logical decompositions with respect to the amount of constraint propagation. For intractable cases, we show in many cases that a propagation algorithm can be adapted from a propagation algorithm of a similar tractable one.
Citation - WoS: 26
Citation - Scopus: 32
The Complexity of Reasoning With Global Constraints
(Springer, 2007) Bessiere, Christian; Hebrard, Emmanuel; Hnich, Brahim; Walsh, Toby
Constraint propagation is one of the techniques central to the success of constraint programming. To reduce search, fast algorithms associated with each constraint prune the domains of variables. With global (or non-binary) constraints, the cost of such propagation may be much greater than the quadratic cost for binary constraints. We therefore study the computational complexity of reasoning with global constraints. We first characterise a number of important questions related to constraint propagation. We show that such questions are intractable in general, and identify dependencies between the tractability and intractability of the different questions. We then demonstrate how the tools of computational complexity can be used in the design and analysis of specific global constraints. In particular, we illustrate how computational complexity can be used to determine when a lesser level of local consistency should be enforced, when constraints can be safely generalized, when decomposing constraints will reduce the amount of pruning, and when combining constraints is tractable.
Citation - WoS: 27
Citation - Scopus: 33
Computing the Non-Stationary Replenishment Cycle Inventory Policy Under Stochastic Supplier Lead-Times
(Elsevier, 2010) Rossi, Roberto; Tarim, S. Armagan; Hnich, Brahim; Prestwich, Steven
In this paper we address the general multi-period production/inventory problem with non-stationary stochastic demand and supplier lead-time under service level constraints. A replenishment cycle policy (RS) is modeled, where R is the nth replenishment cycle length and S is the respective order-up-to-level. We propose a stochastic constraint programming approach for computing the optimal policy parameters. In order to do so, a dedicated global chance-constraint and the respective filtering algorithm that enforce the required service level are presented. Our numerical examples show that a stochastic supplier lead-time significantly affects policy parameters with respect to the case in which the lead-time is assumed to be deterministic or absent. (C) 2010 Elsevier B.V. All rights reserved.
Citation - WoS: 30
Citation - Scopus: 36
Confidence-Based Optimisation for the Newsvendor Problem Under Binomial, Poisson and Exponential Demand
(Elsevier Science Bv, 2014) Rossi, Roberto; Prestwich, Steven; Tarim, S. Armagan; Hnich, Brahim
We introduce a novel strategy to address the issue of demand estimation in single-item single-period stochastic inventory optimisation problems. Our strategy analytically combines confidence interval analysis and inventory optimisation. We assume that the decision maker is given a set of past demand samples and we employ confidence interval analysis in order to identify a range of candidate order quantities that, with prescribed confidence probability, includes the real optimal order quantity for the underlying stochastic demand process with unknown stationary parameter(s). In addition, for each candidate order quantity that is identified, our approach produces an upper and a lower bound for the associated cost. We apply this approach to three demand distributions in the exponential family: binomial, Poisson, and exponential. For two of these distributions we also discuss the extension to the case of unobserved lost sales. Numerical examples are presented in which we show how our approach complements existing frequentist e.g. based on maximum likelihood estimators or Bayesian strategies. (C) 2014 Elsevier B.V. All rights reserved.
Citation - WoS: 90
Citation - Scopus: 104
Constraint Models for the Covering Test Problem
(Springer, 2006) Hnich, Brahim; Prestwich, Steven D.; Selensky, Evgeny; Smith, Barbara M.
Covering arrays can be applied to the testing of software, hardware and advanced materials, and to the effects of hormone interaction on gene expression. In this paper we develop constraint programming models of the problem of finding an optimal covering array. Our models exploit global constraints, multiple viewpoints and symmetry-breaking constraints. We show that compound variables, representing tuples of variables in our original model, allow the constraints of this problem to be represented more easily and hence propagate better. With our best integrated model, we are able to either prove the optimality of existing bounds or find new optimal solutions, for arrays of moderate size. Local search on a SAT-encoding of the model is able to find improved solutions and bounds for larger problems.
Citation - WoS: 10
Citation - Scopus: 11
Constraint Programming for Stochastic Inventory Systems Under Shortage Cost
(Springer, 2012) Rossi, Roberto; Tarim, S. Armagan; Hnich, Brahim; Prestwich, Steven
One of the most important policies adopted in inventory control is the replenishment cycle policy. Such a policy provides an effective means of damping planning instability and coping with demand uncertainty. In this paper we develop a constraint programming approach able to compute optimal replenishment cycle policy parameters under non-stationary stochastic demand, ordering, holding and shortage costs. We show how in our model it is possible to exploit the convexity of the cost-function during the search to dynamically compute bounds and perform cost-based filtering. Our computational experience show the effectiveness of our approach. Furthermore, we use the optimal solutions to analyze the quality of the solutions provided by an existing approximate mixed integer programming approach that exploits a piecewise linear approximation for the cost function.
Citation - WoS: 8
Citation - Scopus: 10
Cost-Based Filtering Techniques for Stochastic Inventory Control Under Service Level Constraints
(Springer, 2009) Tarim, S. Armagan; Hnich, Brahim; Rossi, Roberto; Prestwich, Steven
This paper(1) considers a single product and a single stocking location production/inventory control problem given a non-stationary stochastic demand. Under a widely-used control policy for this type of inventory system, the objective is to find the optimal number of replenishments, their timings and their respective order-up-to-levels that meet customer demands to a required service level. We extend a known CP approach for this problem using three cost-based filtering methods. Our approach can solve to optimality instances of realistic size much more efficiently than previous approaches, often with no search effort at all.
Citation - Scopus: 2
Covering Points With Minimum/Maximum Area Orthogonally Convex Polygons
(Elsevier Science Bv, 2016) Evrendilek, Cem; Genc, Burkay; Hnich, Brahim
In this paper, we address the problem of covering a given set of points on the plane with minimum and/or maximum area orthogonally convex polygons. It is known that the number of possible orthogonally convex polygon covers can be exponential in the number of input points. We propose, for the first time, an O(n(2)) algorithm to construct either the maximum or the minimum area orthogonally convex polygon if it exists, else report the non-existence in O (n log n). (C) 2016 Elsevier B.V. All rights reserved.
Citation - WoS: 1
Citation - Scopus: 1
Covering Points With Orthogonal Polygons
(Elsevier, 2014) Evrendilek, Cem; Genc, Burkay; Hnich, Brahim
We address the problem of covering points with orthogonal polygons. Specifically, given a set of n points in the plane, we investigate the existence of an orthogonal polygon such that there is a one-to-one correspondence between the points and the edges of the polygon. In an earlier paper, we have shown that constructing such a covering with an orthogonally convex polygon, if any, can be done in O(n log n) time. In case an orthogonally convex polygon cannot cover the point set, we show in this paper that the problem of deciding whether such a point set can be covered with any orthogonal polygon is NP-complete. The problem remains NP-complete even if the orientations of the edges covering each point are specified in advance as part of the input. (C) 2012 Elsevier B.V. All rights reserved.
Citation - WoS: 4
Citation - Scopus: 5
Covering Points With Orthogonally Convex Polygons
(Elsevier, 2011) Genç, Burkay; Evrendilek, Cem; Hnich, Brahim
In this paper, we address the problem of covering points with orthogonally convex polygons. In particular, given a point set of size n on the plane, we aim at finding if there exists an orthogonally convex polygon such that each edge of the polygon covers exactly one point and each point is covered by exactly one edge. We show that if such a polygon exists, it may not be unique. We propose an O(n log n) algorithm to construct such a polygon if it exists, or else report the non-existence in the same time bound. We also extend our algorithm to count all such polygons without hindering the overall time complexity. Finally, we show how to construct all k such polygons in O(n log n + kn) time. All the proposed algorithms are fast and practical. (C) 2010 Elsevier B.V. All rights reserved.
Citation - WoS: 12
Citation - Scopus: 13
Filtering Algorithms for Global Chance Constraints
(Elsevier Science Bv, 2012) Hnich, Brahim; Rossi, Roberto; Tarim, S. Armagan; Prestwich, Steven
Stochastic Constraint Satisfaction Problems (SCSPs) are a powerful modeling framework for problems under uncertainty. To solve them is a PSPACE task. The only complete solution approach to date - scenario-based stochastic constraint programming - compiles SCSPs clown into classical CSPs. This allows the reuse of classical constraint solvers to solve SCSPs, but at the cost of increased space requirements and weak constraint propagation. This paper tries to overcome these drawbacks by automatically synthesizing filtering algorithms for global chance constraints. These filtering algorithms are parameterized by propagators for the deterministic version of the chance constraints. This approach allows the reuse of existing propagators in current constraint solvers and it has the potential to enhance constraint propagation. Our results show that, for the test bed considered in this work, our approach is superior to scenario-based stochastic constraint programming. For these instances, our approach is more scalable, it produces more compact formulations, it is more efficient in terms of run time and more effective in terms of pruning for both stochastic constraint satisfaction and optimization problems. (C) 2012 Elsevier B.V. All rights reserved.
Citation - WoS: 4
Citation - Scopus: 7
Filtering Algorithms for the Multiset Ordering Constraint
(Elsevier, 2009) Frisch, Alan M.; Hnich, Brahim; Kiziltan, Zeynep; Miguel, Ian; Walsh, Toby
Constraint programming (CP) has been used with great success to tackle a wide variety of constraint satisfaction problems which are computationally intractable in general. Global constraints are one of the important factors behind the success of CP. In this paper, we study a new global constraint, the multiset ordering constraint, which is shown to be useful in symmetry breaking and searching for leximin optimal solutions in CP. We propose efficient and effective filtering algorithms for propagating this global constraint. We show that the algorithms maintain generalised arc-consistency and we discuss possible extensions. We also consider alternative propagation methods based on existing constraints in CP toolkits. Our experimental results on a number of benchmark problems demonstrate that propagating the multiset ordering constraint via a dedicated algorithm can be very beneficial. (C) 2008 Elsevier B.V. All rights reserved.
Citation - WoS: 25
Citation - Scopus: 34
Filtering Algorithms for the Nvalue Constraint
(Springer, 2006) Bessiere, Christian; Hebrard, Emmanuel; Hnich, Brahim; Kiziltan, Zeynep; Walsh, Toby
The NVALUE constraint counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing even the lower bound on the number of values is NP-hard. We therefore study different approximation heuristics for this problem. We introduce three new methods for computing a lower bound on the number of values. The first two are based on the maximum independent set problem and are incomparable to a previous approach based on intervals. The last method is a linear relaxation of the problem. This gives a tighter lower bound than all other methods, but at a greater asymptotic cost.
Citation - WoS: 6
Citation - Scopus: 6
Finding Reliable Solutions: Event-Driven Probabilistic Constraint Programming
(Springer, 2009) Tarim, S. Armagan; Hnich, Brahim; Prestwich, Steven; Rossi, Roberto
Real-life management decisions are usually made in uncertain environments, and decision support systems that ignore this uncertainty are unlikely to provide realistic guidance. We show that previous approaches fail to provide appropriate support for reasoning about reliability under uncertainty. We propose a new framework that addresses this issue by allowing logical dependencies between constraints. Reliability is then defined in terms of key constraints called events, which are related to other constraints via these dependencies. We illustrate our approach on three problems, contrast it with existing frameworks, and discuss future developments.
Citation - WoS: 25
Citation - Scopus: 32
A Global Chance-Constraint for Stochastic Inventory Systems Under Service Level Constraints
(Springer, 2008) Rossi, Roberto; Tarim, S. Armagan; Hnich, Brahim; Prestwich, Steven
We consider a class of production/inventory control problems that has a single product and a single stocking location, for which a stochastic demand with a known non-stationary probability distribution is given. Under the widely-known replenishment cycle policy the problem of computing policy parameters under service level constraints has been modeled using various techniques. Tarim and Kingsman introduced a modeling strategy that constitutes the state-of-the-art approach for solving this problem. In this paper we identify two sources of approximation in Tarim and Kingsman's model and we propose an exact stochastic constraint programming approach. We build our approach on a novel concept, global chance-constraints, which we introduce in this paper. Solutions provided by our exact approach are employed to analyze the accuracy of the model developed by Tarim and Kingsman.
Citation - WoS: 8
Citation - Scopus: 10
Learning Market Prices in Real-Time Supply Chain Management
(Pergamon-Elsevier Science Ltd, 2008) Burke, David A.; Brown, Kenneth N.; Tarim, S. Armagan; Hnich, Brahim
This paper proposes a model for dynamic pricing that combines knowledge of production capacity and existing commitments, reasoning about uncertainty and learning of market conditions in an attempt to optimise expected profits. In particular, the market conditions are represented as a set of probabilities over the success rate of product prices, and those prices are learned online as the market develops. The dynamic pricing model is integrated into a real-time supply chain management agent using the Trading Agent Competition Supply Chain Management game as a test framework. We evaluate the agent experimentally in competition with other supply chain agents, and demonstrate the benefits of incorporating more market data into the dynamic pricing mechanism. (c) 2007 Elsevier Ltd. All rights reserved.
Citation - WoS: 3
Citation - Scopus: 4
A Note on Liu-iwamura's Dependent-Chance Programming
(Elsevier Science Bv, 2009) Rossi, Roberto; Tarim, S. Armagan; Hnich, Brahim; Prestwich, Steven; Guran, Cahit
Sometimes a complex stochastic decision system undertakes multiple tasks called events, and the decision-maker wishes to maximize the chance functions which are defined as the probabilities of satisfying these events. Originally introduced by Liu and Iwamura [B. Liu, K. Iwarnura, Modelling stochastic decision systems using dependent-chance programming, European journal of Operational Research 101 (1997) 193-203], dependent-chance programming is aimed at maximizing some chance functions of events in an uncertain environment. In this work. we show that the original dependent chance-programming framework needs to be extended in order to capture an exact reliability measure for a given plan. (C) 2008 Elsevier B.V. All rights reserved.
Citation - WoS: 37
Citation - Scopus: 41
Parallel Machine Scheduling With Tool Loading
(Elsevier Science Inc, 2016) Özpeynirci, Selin; Gokgur, Burak; Hnich, Brahim
This paper presents a mixed integer programming approach that integrates the tool assignment and scheduling problems arising in parallel machine environments. There are a number of operations to be processed on parallel machines. Each operation requires a set of tools; however, the number of available tools are limited. Our objective is to minimize the makespan, i.e. the completion time of the final operation. We propose two different mathematical programming models for this problem. Since the problem is strongly NP hard in general, finding the optimal solution requires extremely long computational times as the problem size increases. We therefore develop a tabu search algorithm in order to find near-optimal solutions within reasonable times. (C) 2016 Elsevier Inc. All rights reserved.
Citation - WoS: 48
Citation - Scopus: 58
Parallel Machine Scheduling With Tool Loading: a Constraint Programming Approach
(Taylor & Francis Ltd, 2018) Gokgur, Burak; Hnich, Brahim; Özpeynirci, Selin
This paper presents constraint programming models that aim to solve scheduling and tool assignment problems in parallel machine environments. There are a number of jobs to be processed on parallel machines. Each job requires a set of tools, but limited number of tools are available in the system due to economic restrictions. The problem is to assign the jobs and the required tools to machines and to determine the schedule so that the makespan is minimised. Three constraint programming models are developed and compared with existing methods described in the literature.
Citation - WoS: 4
Citation - Scopus: 6
Partial Symmetry Breaking by Local Search in the Group
(Springer, 2012) Prestwich, Steve D.; Hnich, Brahim; Simonis, Helmut; Rossi, Roberto; Tarim, S. Armagan
The presence of symmetry in constraint satisfaction problems can cause a great deal of wasted search effort, and several methods for breaking symmetries have been reported. In this paper we describe a new method called Symmetry Breaking by Nonstationary Optimisation, which interleaves local search in the symmetry group with backtrack search on the constraint problem. It can be tuned to break each symmetry with an arbitrarily high probability with high runtime overhead, or as a lightweight but still powerful method with low runtime overhead. It has negligible memory requirement, it combines well with static lex-leader constraints, and its benefit increases with problem hardness.