**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Integer programming

Summary

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear.
Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.
If some decision variables are not discrete, the problem is known as a mixed-integer programming problem.
Canonical and standard form for ILPs
In integer linear programming, the canonical form is distinct from the standard form. An integer linear program in canonical form is expressed thus (note that it is the \mathbf{x} vector which is to be decided):
: \begin{align}
& \text{maximize} && \mathbf{c}^\mathrm{T} \math

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications (100)

Loading

Loading

Loading

Related people (29)

Related concepts (27)

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exa

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the

Related units (15)

Related courses (36)

ME-454: Modelling and optimization of energy systems

The goal of the lecture is to present and apply techniques for the modelling and the thermo-economic optimisation of industrial process and energy systems. The lecture covers the problem statement, the solving methods for the simulation and the single and multi-objective optimisation problems.

CS-450: Advanced algorithms

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a repertory of basic algorithmic solutions to problems in many domains.

MGT-483: Optimal decision making

This course introduces the theory and applications of optimization. We develop tools and concepts of optimization and decision analysis that enable managers in manufacturing, service operations, marketing, transportation and finance to transform data into insights for making better decisions.

Background: The gene family-free framework for comparative genomics aims at providing methods for gene order analysis that do not require prior gene family assignment, but work directly on a sequence similarity graph. We study two problems related to the breakpoint median of three genomes, which asks for the construction of a fourth genome that minimizes the sum of breakpoint distances to the input genomes. Methods: We present a model for constructing a median of three genomes in this family-free setting, based on maximizing an objective function that generalizes the classical breakpoint distance by integrating sequence similarity in the score of a gene adjacency. We study its computational complexity and we describe an integer linear program (ILP) for its exact solution. We further discuss a related problem called family-free adjacencies for k genomes for the special case of k

2017Future low-carbon societies will need to store vast amounts of electricity to stabilize electricity grids and to power electric vehicles. Vehicle-to-grid allows vehicle owners and grid operators to share the costs of electricity storage by making the batteries of electric vehicles available to the grid. In practice, vehicle owners decide when to reserve their cars for driving and when to make them available for grid services. Vehicle aggregators then decide how to commit the vehicles to grid services. For vehicle-to-grid to succeed, both vehicle owners and grid operators must be able to trust aggregators, i.e., vehicles should be available for driving and for grid services when the aggregators promise they will be. In this thesis, we solve a decision-making problem that ensures reliable commitments by vehicle aggregators for a particular grid service known as primary frequency regulation, considered one of the most profitable applications of vehicle-to-grid. Mathematically, we first formulate a robust optimization problem with functional uncertainties that maximizes the expected profit from selling primary frequency regulation to grid operators and guarantees that vehicle owners can meet their market commitments for all frequency deviation trajectories in an uncertainty set that encodes applicable European Union regulations. Functional uncertainties ensure that vehicle owners and grid operators can trust the decisions of aggregators at all times. Faithfully modeling the energy conversion losses during battery charging and discharging renders the optimization problem nonconvex. By exploiting a total unimodularity property of the proposed uncertainty sets and an exact linear decision rule reformulation, we prove that the nonconvex robust optimization problem with functional uncertainties is equivalent to a tractable linear program. Somewhat counterintuitively, the underlying deterministic problem for a known frequency deviation trajectory does not reduce to a linear program but results in a large-scale mixed-integer linear program, even if time is discretized. We believe that we have thus discovered the first practically interesting class of optimization problems that become dramatically easier through robustification. Through extensive numerical experiments using real-world data, we quantify the economic value of vehicle-to-grid and elucidate the financial incentives of vehicle owners, aggregators, equipment manufacturers, and regulators. In particular, we find that the prevailing penalties for non-delivery of promised regulation power are too low to incentivize aggregators to honor their promises toward grid operators. For general electricity storage devices, we then solve a simplified version of the decision-making problem analytically to understand how the optimal frequency regulation commitments depend on the roundtrip efficiency of the storage device, the dispersion of the frequency deviations, and the EU delivery guarantee. We show how the marginal cost of frequency regulation decreases with roundtrip efficiency and increases with frequency deviation dispersion. For energy-constrained storage devices, we find that the profits from frequency regulation are inversely proportional to the length of time for which storage operators commit regulation power. Establishing an intra-day market for frequency regulation would thus make electricity storage devices more competitive with other regulation providers, such as thermal power plants.

Xinrui Jia, Ola Nils Anders Svensson

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius rho such that there exist balls of radius rho around k of the points that meet the coverage requirements. The motivation behind this problem is twofold. First, from fairness considerations: each color/group should receive a similar service guarantee, and second, from the algorithmic challenges it poses: this problem combines the difficulties of clustering along with the subset-sum problem. In particular, we show that this combination results in strong integrality gap lower bounds for several natural linear programming relaxations. Our main result is an efficient approximation algorithm that overcomes these difficulties to achieve an approximation guarantee of 3, nearly matching the tight approximation guarantee of 2 for the classical k-center problem which this problem generalizes. algorithms either opened more than k centers or only worked in the special case when the input points are in the plane.

Related lectures (102)