References of "Spieksma, Frits C.R"
     in
Bookmark and Share    
Full Text
See detailTesting revealed preference: An algorithmic outlook
Smeulders, Bart ULiege; Crama, Yves ULiege; Spieksma, Frits C.R.

E-print/Working paper (2017)

Revealed preference theory is a domain within economics that studies rationalizability of behavior by (certain types of) utility functions. Given observed behavior in the form of choice data, testing ... [more ▼]

Revealed preference theory is a domain within economics that studies rationalizability of behavior by (certain types of) utility functions. Given observed behavior in the form of choice data, testing whether certain conditions are satisfied gives rise to a variety of computational problems that can be analyzed using operations research techniques. In this survey, we provide an overview of these problems, their theoretical complexity, and available algorithms for tackling them. We focus on consumer choice settings, in particular individual choice, collective choice and stochastic choice settings. [less ▲]

Detailed reference viewed: 36 (3 ULiège)
Full Text
Peer Reviewed
See detailExact algorithms for the Equitable Traveling Salesman Problem
Kinable, Joris; Smeulders, Bart ULiege; Delcour, Eline et al

in European Journal of Operational Research (2017)

Given a weighted graph G = (V,E), the Equitable Traveling Salesman Problem (ETSP) asks for two perfect matchings in G such that (1) the two matchings together form a Hamiltonian cycle in G and (2) the ... [more ▼]

Given a weighted graph G = (V,E), the Equitable Traveling Salesman Problem (ETSP) asks for two perfect matchings in G such that (1) the two matchings together form a Hamiltonian cycle in G and (2) the absolute difference in costs between the two matchings is minimized. The problem is shown to be NP-Hard, even when the graph G is complete. We present two integer programming models to solve the ETSP problem and compare the strength of these formulations. One model is solved through branch-and-cut, whereas the other model is solved through a branch-and-price framework. A simple local search heuristic is also implemented. We conduct computational experiments on different types of instances, often derived from the TSPLib. It turns out that the behavior of the different approaches varies with the type of instances. For small and medium sized instances, branch-and-bound and branch-and-price produce comparable results. However, for larger instances branch-and- bound outperforms branch-and-price. [less ▲]

Detailed reference viewed: 20 (4 ULiège)
See detailDatasets for Testing Probabilistic Models of Choice using Column Generation
Spieksma, Frits C.R.; Davis-Stober, Clint; Regenwetter, Mike et al

Textual, factual or bibliographical database (2017)

Detailed reference viewed: 32 (1 ULiège)
Full Text
Peer Reviewed
See detailRevealed preference tests of collectively rational consumption behavior: formulations and algorithms
Talla Nobibon, Fabrice; Cherchye, Laurens; Crama, Yves ULiege et al

in Operations Research (2016), 64(6), 11971216

This paper focuses on revealed preference tests of the collective model of household consumption. We start by showing that the decision problems corresponding to testing collective rationality are {\sc np ... [more ▼]

This paper focuses on revealed preference tests of the collective model of household consumption. We start by showing that the decision problems corresponding to testing collective rationality are {\sc np}-complete. This makes the application of these tests problematic for (increasingly available) large(r) scale data sets. We then present two approaches to overcome this negative result. First, we introduce exact algorithms based on mixed-integer programming ({\sc mip}) formulations of the collective rationality tests, which can be usefully applied to medium sized data sets. Next, we propose simulated annealing heuristics, which allow for efficient testing of the collective model in the case of large data sets. We illustrate our methods by a number of computational experiments based on Dutch labor supply data. [less ▲]

Detailed reference viewed: 107 (14 ULiège)
Full Text
Peer Reviewed
See detailMulti-Dimensional Vector Assignment Problems
Dokka, Trivikram; Crama, Yves ULiege; Spieksma, Frits C.R.

in Discrete Optimization (2014), 14

We consider a special class of axial multi-dimensional assignment problems called multi- dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by m disjoint sets, each of ... [more ▼]

We consider a special class of axial multi-dimensional assignment problems called multi- dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by m disjoint sets, each of which contains the same number n of p-dimensional vectors with nonnegative integral components, and a cost function defined on vectors. The cost of an m-tuple of vectors is defined as the cost of their component-wise maximum. The problem is now to partition the m sets of vectors into n m-tuples so that no two vectors from the same set are in the same m-tuple and so that the sum of the costs of the m-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We consider a particular class of polynomial-time heuristics for MVA, namely the sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, sequential heuristics have a finite approximation ratio for every fixed m. Moreover, we establish smaller approximation ratios when the cost function is submodular and, for a specific sequential heuristic, when the cost function is additive. We provide examples to illustrate the tightness of our analysis. Furthermore, we show that the MVA problem is APX-hard even for the case m = 3 and for binary input vectors. Finally, we show that the problem can be solved in polynomial time in the special case of binary vectors with fixed dimension p. [less ▲]

Detailed reference viewed: 28 (9 ULiège)
Full Text
See detailApproximation Algorithms for Multi-Dimensional Vector Assignment Problems
Dokka, Trivikram; Crama, Yves ULiege; Spieksma, Frits C.R.

E-print/Working paper (2013)

We consider a special class of axial multi-dimensional assignment problems called multi-dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by $m$ disjoint sets, each ... [more ▼]

We consider a special class of axial multi-dimensional assignment problems called multi-dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by $m$ disjoint sets, each of which contains the same number $n$ of $p$-dimensional vectors with nonnegative integral components, and a cost function defined on vectors. The cost of an $m$-tuple of vectors is defined as the cost of their component-wise maximum. The problem is now to partition the $m$ sets of vectors into $n$ $m$-tuples so that no two vectors from the same set are in the same $m$-tuple and so that the total cost of the $m$-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We consider two classes of polynomial-time heuristics for MVA, namely, hub heuristics and sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, hub heuristics, as well as sequential heuristics, have finite approximation ratio for every fixed $m$. Moreover, we establish better approximation ratios for certain variants of hub heuristics and sequential heuristics when the cost function is monotone and submodular, or when it is additive. We provide examples to illustrate the tightness of our analysis. Furthermore, we show that the MVA problem is APX-hard even for the case $m=3$ and for binary input vectors. Finally, we show that the problem can be solved in polynomial time in the special case of binary vectors with fixed dimension $p$. [less ▲]

Detailed reference viewed: 136 (11 ULiège)
Full Text
Peer Reviewed
See detailThe interval ordering problem
Durr, Christophe; Queyranne, Maurice; Spieksma, Frits C.R. et al

in Discrete Applied Mathematics (2012)

Detailed reference viewed: 17 (0 ULiège)
Full Text
Peer Reviewed
See detailCounting and enumerating aggregate classifiers
Adem, Jan; Crama, Yves ULiege; Gochet, Willy et al

in Discrete Applied Mathematics (2008), 156(3), 2459-2468

We propose a generic model for the "weighted voting" aggregation step performed by several methods in supervised classification. Further, we construct an algorithm to count the number of distinct ... [more ▼]

We propose a generic model for the "weighted voting" aggregation step performed by several methods in supervised classification. Further, we construct an algorithm to count the number of distinct aggregate classifiers that arise in this model. When there are only two classes in the classification problem, we show that a class of functions that arises from aggregate classifiers coincides with the class of self-dual positive threshold Boolean functions. [less ▲]

Detailed reference viewed: 44 (14 ULiège)
Full Text
Peer Reviewed
See detailThe tool switching problem revisited
Crama, Yves ULiege; Moonen, Linda S; Spieksma, Frits CR et al

in European Journal of Operational Research (2007), 182(2), 952-957

In this note we study the tool switching problem with non-uniform tool sizes. More specifically, we consider the problem where the job sequence is given as part of the input. We show that the resulting ... [more ▼]

In this note we study the tool switching problem with non-uniform tool sizes. More specifically, we consider the problem where the job sequence is given as part of the input. We show that the resulting tooling problem is strongly N P-complete, even in case of unit loading and unloading costs. On the other hand, if the capacity of the tool magazine is also given as part of the input, we show that the problem is solvable in polynomial time. These results settle the complexity of a relevant variant of the tool switching problem. (C) 2006 Elsevier B.V. All rights reserved. [less ▲]

Detailed reference viewed: 35 (6 ULiège)
Full Text
Peer Reviewed
See detailProduction planning problems in printed circuit board assembly
Crama, Yves ULiege; van de Klundert, Joris; Spieksma, Frits CR

in Discrete Applied Mathematics (2002), 123(1-3), 339-361

This survey describes some of the main optimization problems arising in the context of production planning for the assembly of printed circuit boards. The discussion is structured around a hierarchical ... [more ▼]

This survey describes some of the main optimization problems arising in the context of production planning for the assembly of printed circuit boards. The discussion is structured around a hierarchical decomposition of the planning process into distinct optimization subproblems, addressing issues such as the assignment of board types to machine groups, the allocation of component feeders to individual machines, the determination of optimal production sequences, etc, The paper reviews the literature on this topic with an emphasis on the most recent developments, on the fundamental structure of the mathematical models and on the relation between these models and some 'environmental' variables such as the layout of the shop or the product mix. (C) 2002 Elsevier Science B.V, All rights reserved. [less ▲]

Detailed reference viewed: 403 (7 ULiège)
Full Text
Peer Reviewed
See detailThe assembly of printed circuit boards: A case with multiple machines and multiple board types
Crama, Yves ULiege; Flippo, Olaf E.; Van de Klundert, Joris et al

in European Journal of Operational Research (1997), 98

In this paper a typical situation arising in the assembly of printed circuit boards is investigated. The planning problem we face is how to assemble boards of different types using a single line of ... [more ▼]

In this paper a typical situation arising in the assembly of printed circuit boards is investigated. The planning problem we face is how to assemble boards of different types using a single line of placement machines. From a practical viewpoint, the multiplicity of board types adds significantly to the complexity of the problem, which is already very hard to solve in the case of a single board type. In addition, relatively few studies deal with the multiple board type case. We propose a solution procedure based on a hierarchical decomposition of the planning problem. An important subproblem in this decomposition is the so-called feeder rack assignment problem. By taking into account as much as possible the individual board type characteristics (as well as the machine characteristics) we heuristically solve this problem. The remaining subproblems are solved using constructive heuristics and local search methods. The solution procedure is tested on real-life instances. It turns out that, in terms of the makespan, we can substantially improve the current solutions. [less ▲]

Detailed reference viewed: 51 (2 ULiège)
Full Text
Peer Reviewed
See detailThe component retrieval problem in printed circuit board assembly
Crama, Yves ULiege; Flippo, Olaf E.; Van de Klundert, Joris et al

in International Journal of Flexible Manufacturing Systems (1996), 8

The minimization of the makespan of a printed circuit board assembly process is a complex problem. Decisions involved in this problem concern the specification of the order in which components are to be ... [more ▼]

The minimization of the makespan of a printed circuit board assembly process is a complex problem. Decisions involved in this problem concern the specification of the order in which components are to be placed on the board, and the assignment of component types to the feeder slots of the placement machine. If some component types are assigned to multiple feeder slots, then the additional problem emerges of selecting, for each placement on the board, the feeder slot from which the related component type is to be retrieved. In this paper, we consider this Component Retrieval Problem for placement machines that operate in a similar way as the Fuji CP II. We explain why a simple forward dynamic programming scheme cannot provide an efficient solution to this problem, thereby invalidating the correctness of an earlier published approach. We then present a polynomial algorithm that solves the problem to optimality. The analysis of the Component Retrieval Problem is greatly facilitated by its reformulation as a longest path problem in a PERT/CPM network with design aspects. Finding the minimal makespan of the assembly process thus amounts to identifying a design for which the longest path in the induced network is shortest. As an alternative interpretation, the Component Retrieval Problem can be viewed as a shortest path problem with side-constraints. The complexity of these network problems is analysed, and it is proven that the polynomial solvability of the Component Retrieval Problem is caused by the specific structure it inflicts on the arc lengths in the network. In the absence of this structure, the network problems are shown to be NP- hard in general. [less ▲]

Detailed reference viewed: 46 (1 ULiège)
Full Text
Peer Reviewed
See detailScheduling jobs of equal length: complexity, facets and computational results
Crama, Yves ULiege; Spieksma, Frits C.R.

in Mathematical Programming (1996), 72

The following problem was originally motivated by a question arising in the automated assembly of printed circuit boards. Given aren jobs, which have to be performed on a single machine within a fixed ... [more ▼]

The following problem was originally motivated by a question arising in the automated assembly of printed circuit boards. Given aren jobs, which have to be performed on a single machine within a fixed timespan [0,T], subdivided into T unit-length subperiods. The processing time (or length) of each job equals p,p ∈ ℕ. The processing cost of each job is an arbitrary function of its start-time. The problem is to schedule all jobs so as to minimize the sum of the processing costs. This problem is proved to be NP-hard, already for p=2 and 0–1 processing costs. On the other hand, when T=np+c, with c constant, the problem can be solved in polynomial time. A partial polyhedral description of the set of feasible solutions is presented. In particular, two classes of facet-defining inequalities are described, for which the separation problem is polynomially solvable. Also, we exhibit a class of objective functions for which the inequalities in the LP-relaxation guarantee integral solutions. Finally, we present a simple cutting plane algorithm and report on its performance on randomly generated problem instances. [less ▲]

Detailed reference viewed: 19 (3 ULiège)
See detailProduction Planning in Automated Manufacturing
Crama, Yves ULiege; Oerlemans, Alwin G.; Spieksma, Frits C.R.

Book published by Springer Science & Business Media B.V. - Second, revised and enlarged edition. (First edition: 1994) (1996)

Detailed reference viewed: 23 (1 ULiège)
See detailProduction Planning in Automated Manufacturing
Crama, Yves ULiege; Oerlemans, Alwin G.; Spieksma, Frits C.R.

Book published by Springer-Verlag - First edition. (Second, revised and enlarged edition: 1996) (1994)

Detailed reference viewed: 60 (18 ULiège)
Full Text
Peer Reviewed
See detailMinimizing the number of tool switches on a flexible machine
Crama, Yves ULiege; Kolen, Anton W.J.; Oerlemans, Alwin G. et al

in International Journal of Flexible Manufacturing Systems (1994), 6

This article analyzes a tool switching problem arising in certain flexible manufacturing environments. A batch of jobs have to be successively processed on a single flexible machine. Each job requires a ... [more ▼]

This article analyzes a tool switching problem arising in certain flexible manufacturing environments. A batch of jobs have to be successively processed on a single flexible machine. Each job requires a subset of tools, which have to be placed in the tool magazine of the machine before the job can be processed. The tool magazine has a limited capacity, and, in general, the number of tools needed to produce all the jobs exceeds this capacity. Hence, it is sometimes necessary to change tools between two jobs in a sequence. The problem is then to determine a job sequence and an associated sequence of loadings for the tool magazine, such that the total number of tool switches is minimized. This problem has been previously considered by several authors; it is here revisited, both from a theoretical and from a computational viewpoint. Basic results concerning the computational complexity of the problem are established. Several heuristics are proposed for its solution, and their performance is computationally assessed. [less ▲]

Detailed reference viewed: 12 (0 ULiège)
Full Text
Peer Reviewed
See detailApproximation algorithms for multi-dimensional assignment problems with decomposable costs
Bandelt, Hans-Jürgen; Crama, Yves ULiege; Spieksma, Frits C.R.

in Discrete Applied Mathematics (1994), 49

The k-dimensional assignment problem with decomposable costs is formulated as follows. Given is a complete k-partite graph G = (X_0 U ... U X_{k-1}, E), with lX_il = p for each i, and a nonnegative length ... [more ▼]

The k-dimensional assignment problem with decomposable costs is formulated as follows. Given is a complete k-partite graph G = (X_0 U ... U X_{k-1}, E), with lX_il = p for each i, and a nonnegative length function defined on the edges of G. A clique of G is a subset of vertices meeting each X_i in exactly one vertex. The cost of a clique is a function of the lengths of the edges induced by the clique. Four specific cost functions are considered in this paper; namely, the cost of a clique is either the sum of the lengths of the edges induced by the clique (sum costs), or the minimum length of a spanning star (star costs) or of a traveling salesman tour (tour costs) or of a spanning tree (tree costs) of the induced subgraph. The problem is to find a minimumcost partition of the vertex set of G into cliques. We propose several simple heuristics for this problem, and we derive worst-case bounds on the ratio between the cost of the solutions produced by these heuristics and the cost of an optimal solution. The worst-case bounds are stated in terms of two parameters, viz. k and z, where the parameter z indicates how close the edge length function comes to satisfying the triangle inequality. [less ▲]

Detailed reference viewed: 22 (0 ULiège)
Full Text
See detailThe complexity of scheduling short tasks with few starting times
Crama, Yves ULiege; Spieksma, Frits C.R.

E-print/Working paper (1992)

The following problem is proved to be NP-complete: given n tasks, such that each task has processing time \tau=2, and has no more than k=3 possible starting times, does there exist a feasible schedule for ... [more ▼]

The following problem is proved to be NP-complete: given n tasks, such that each task has processing time \tau=2, and has no more than k=3 possible starting times, does there exist a feasible schedule for these tasks on a single processor? This result establishes a sharp borderline between NP-complete and polynomially solvable versions of this problem with respect to the parameters \tau and k. [less ▲]

Detailed reference viewed: 44 (1 ULiège)
Full Text
Peer Reviewed
See detailApproximation algorithms for three-dimensional assignment problems with triangle inequalities
Crama, Yves ULiege; Spieksma, Frits C.R.

in European Journal of Operational Research (1992), 60

The three-dimensional assignment problem (3DA) is defined as follows. Given are three disjoint n-sets of points, and nonnegative costs associated with every triangle consisting of exactly one point from ... [more ▼]

The three-dimensional assignment problem (3DA) is defined as follows. Given are three disjoint n-sets of points, and nonnegative costs associated with every triangle consisting of exactly one point from each set. The problem is to find a minimum-weight collection of n triangles covering each point exactly once. We consider the special cases of 3DA where a distance (verifying the triangle inequalities) is defined on the set of points, and the cost of a triangle is either the sum of the lengths of its sides (problem TΔ ) or the sum of the lengths of its two shortest sides (problem SΔ ). We prove that TΔ and SΔ are NP-hard. For both TΔ and SΔ , we present 1/2- and 1/3-approximate algorithms, i.e. heuristics which always deliver a feasible solution whose cost is at most 3/2, resp. 4/3, of the optimal cost. Computational experiments indicate that the performance of these heuristics is excellent on randomly generated instances of TΔ and SΔ . [less ▲]

Detailed reference viewed: 19 (0 ULiège)
Full Text
Peer Reviewed
See detailThroughput rate optimization in the automated assembly of printed circuit boards
Crama, Yves ULiege; Kolen, Anton W.J.; Oerlemans, Alwin G. et al

in Annals of Operations Research (1990), 26

The electronics industry relies heavily on numerically controlled machines for the placement of electronic components on the surface of printed circuit boards (PCB). This paper proposes a heuristic ... [more ▼]

The electronics industry relies heavily on numerically controlled machines for the placement of electronic components on the surface of printed circuit boards (PCB). This paper proposes a heuristic hierarchical approach to the problem of optimizing the throughput rate of a line of several such machines, devoted to the assembly of a single type of PCB. A number of well-known NP-hard problems emerge, for which mathematical models and heuristic solution methods are developed. The approach is tested on a real-life problem, for which it is shown to perform well. [less ▲]

Detailed reference viewed: 30 (0 ULiège)