this paper presents an improved as well as a completely new version of a mixed integer linear programming (MILP) formulation for solving the quadratic assignment problem (QAP) to global optimum. Both formulations work...
详细信息
One of the most appealing features of constraint programming is its rich constraint language for expressing combinatorialoptimization problems. this paper demonstrates that traditional combinators from constraint pro...
详细信息
ISBN:
(纸本)3540232419
One of the most appealing features of constraint programming is its rich constraint language for expressing combinatorialoptimization problems. this paper demonstrates that traditional combinators from constraint programming have natural counterparts for local search, although their underlying computational model is radically different. In particular, the paper shows that constraint combinators, such as logical and cardinality operators, reification, and first-class expressions can all be viewed as differentiable objects. these combinators naturally support elegant and efficient modelings, generic search procedures, and partial constraint satisfaction techniques for local search. Experimental results on a variety of applications demonstrate the expressiveness and the practicability of the combinators.
Sum-product networks are expressive efficient probabilistic graphical models that allow for tractable marginal inference. Many tasks however require the computation of maximum-a-posteriori configurations, an NP-hard p...
详细信息
Sum-product networks are expressive efficient probabilistic graphical models that allow for tractable marginal inference. Many tasks however require the computation of maximum-a-posteriori configurations, an NP-hard problem for such models. To date there have been very few proposals for computing maximum-a-posteriori configurations in sum-product networks. this is in sharp difference with other probabilistic frameworks such as Bayesian networks and random Markov fields, where the problem is also NP-hard. In this work we propose two approaches to reformulate maximuma-posteriori inference as other combinatorialoptimization problems with widely available solvers. the first approach casts the problem as a similar inference problem in Bayesian networks, overcoming some limitations of previous similar translations. In addition to making available the toolset of maximum-a-posteriori inference on Bayesian networks to sum-product networks, our reformulation also provides further insight into the connections of these two classes of models. the second approach casts the problem as a mixed-integer linear program, for which there exists very efficient solvers. this allows such inferences to be enriched withinteger-linear constraints, increasing the expressivity of the models. We compare our reformulation approaches in a large collection of problems, and against state-of-the-art approaches. the results show that reformulation approaches are competitive.
In this paper, we consider the classical scheduling problem on parallel machines with capacity constraints. We are given m identical machines, where each machine k can process up to ck jobs. the goal is to assign the...
详细信息
Scheduling problems in which agents (users, customers, application masters, resource manager, etc.) have to share the same set(s) of resources are at the frontier of combinatorialoptimization and cooperative game the...
详细信息
ISBN:
(纸本)9783319480572;9783319480565
Scheduling problems in which agents (users, customers, application masters, resource manager, etc.) have to share the same set(s) of resources are at the frontier of combinatorialoptimization and cooperative game theory. this paper deals with scheduling problems arising when two agents, each with a set of nonpreemptive jobs, compete to perform their respective jobs on two common identical parallel machines. Each agent aims at minimizing a certain objective function that depends on the completion times of its jobs only. the objective functions we consider in our study are makespan and number of tardy jobs. the agents may share some jobs and this problem is called non-disjoint multi-agent scheduling problem [3]. Finding the optimal solution for one agent with a constraint on the other agent's cost function is known to be NP-hard. To obtain best compromise solutions for each agent, we propose polynomial and pseudo-polynomial heuristics. Two mixed integer linear programming models are developed to calculate exact non-dominated solutions. Experimental results are conducted to measure the solutions quality given by heuristics.
We are presenting in this special issue selected, peer-reviewed, papers that were presented at the 1st international Symposium and 10th Balkan conference on Operational Research (BALCOR 2011), which was held during Se...
详细信息
We are presenting in this special issue selected, peer-reviewed, papers that were presented at the 1st international Symposium and 10th Balkan conference on Operational Research (BALCOR 2011), which was held during September 22-24, 2011, in thessaloniki, Greece.
We tackle a bi-objective dynamic orienteering problem where customer requests arise as time passes by. the goal is to minimize the tour length traveled by a single delivery vehicle while simultaneously keeping the num...
详细信息
暂无评论