Concept

Branch and bound

Related publications (146)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Polynomial Approximations for Continuous Linear Programs

Daniel Kuhn

Continuous linear programs have attracted considerable interest due to their potential for modeling manufacturing, scheduling, and routing problems. While efficient simplex-type algorithms have been developed for separated continuous linear programs, crude ...

2012

Vectors in a box

Doemoetoer Palvoelgyi

For an integer d a parts per thousand yen 1, let tau(d) be the smallest integer with the following property: if v (1), v (2), . . . , v (t) is a sequence of t a parts per thousand yen 2 vectors in [-1, 1] (d) with , then there is a set of indices, 2 a part ...

Springer2012

Tight Approximation Algorithms for Scheduling with Fixed Jobs and Nonavailability

Ola Nils Anders Svensson, Klaus Jansen

We study two closely related problems in nonpreemptive scheduling of jobs on identical parallel machines. In these two settings there are either fixed jobs or nonavailability intervals during which the machines are not available; in both cases, the objecti ...

Assoc Computing Machinery2012

MPC for tracking periodic reference signals

Colin Neil Jones, Melanie Nicole Zeilinger

This paper is devoted to the design of a predictive controller for constrained linear systems to track periodic references. The only assumption on the dynamics of the reference is that it is periodic and its period is known. It is also assumed that the ref ...

2012

Experimental Real-Time Optimization of a Solid Oxide Fuel Cell Stack via Constraint Adaptation

Dominique Bonvin, Grégory François, Zacharie Wuillemin, Arata Nakajo, Gene Bunin, Leonidas Tsikonis

The experimental validation of a real-time optimization (RTO) strategy for the optimal operation of a solid oxide fuel cell (SOFC) stack is reported in this paper. Unlike many existing studies, the RTO approach presented here utilizes the constraint-adapta ...

2012

An exact algorithm for the integrated planning of berth allocation and quay crane assignment

Michel Bierlaire, Matteo Salani, Ilaria Vacca

In this paper we study the simultaneous optimization of berth allocation and quay crane assignment in seaport container terminals. We propose a model based on an exponential number of variables that is solved via column generation. An exact branch-and-pric ...

2011

Santa Claus schedules jobs on unrelated machines

Ola Nils Anders Svensson

One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines, i.e., job j requires time p ij if processed on machine i. More th ...

ACM2011

Covering Cubes and the Closest Vector Problem

Friedrich Eisenbrand, Martin Niemeier, Nicolai Hähnle

We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest vector problem in the infinity-norm. The running time of our method depends on the dimension n and the approximation guarantee epsilon by 2^(O(n))(log(1/epsilon ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2011

An Efficient Method to Estimate the Suboptimality of Affine Controllers

Daniel Kuhn

We consider robust feedback control of time-varying, linear discrete-time systems operating over a finite horizon. For such systems, we consider the problem of designing robust causal controllers that minimize the expected value of a convex quadratic cost ...

Institute of Electrical and Electronics Engineers2011

An Efficient Method to Estimate the Suboptimality of Affine Controllers

Daniel Kuhn

Institute of Electrical and Electronics Engineers2011