Publication

Recognition of a class of unimodular functions

Dominique de Werra
1990
Journal Articles

Abstract

For some pseudo-Boolean functions, the problem of maximization reduces to a linear programming problem with a totally unimodular matrix. Among those, we consider the subclass of functions which can be transformed into functions whose nonlinear terms have nonnegative coefficients. A polynomial-time recognition algorithm for such functions is described. The notion of extended graph of a function is introduced; we show that it is bipartite if the linear programming formulation of the optimization problem has a totally unimodular constraint matrix.

Official source

https://infoscience.epfl.ch/entities/publication/f83aed67-356b-4c20-99b0-faed46694ca3

About this result

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.

Graph Chat

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.

Dominique de Werra
1990
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/f83aed67-356b-4c20-99b0-faed46694ca3

About this result

Related concepts (32)

Linear programming

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 by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.

Integer programming

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.

Optimization problem

In mathematics, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete: An optimization problem with discrete variables is known as a discrete optimization, in which an object such as an integer, permutation or graph must be found from a countable set.

Related publications (16)

Recognition of a class of unimodular functions

Chat with Graph Search

Group-and-cut approach for dynamic programming with Fréchet-distributed quantizers

On extremal problems associated with random chords on a circle

MATHICSE Technical Report : A certified reduced basis method for PDE-constrained parametric optimization problems by an adjoint-based approach