Questions tagged [linear-programming]

Optimization with a linear objective function, subject to linear equality and linear inequality constraints.

Filter by
Sorted by
Tagged with
2
votes
1answer
145 views

Why does absence of strongly polynomial time algorithm for LP imply restriction to rational instances?

From Bernhard Korte, Jens Vygen, Combinatorial Optimization, Instances of LINEAR PROGRAMMING are vectors and matrices. Since no strongly polynomial-time algorithm for LINEAR PROGRAMMING is known ...
4
votes
1answer
1k views

Find maximum distance between elements given constraints on some

I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements: The element 1 is in position 1, and element N must be ...
5
votes
2answers
544 views

Randomized Rounding of Solutions to Linear Programs

Integer linear programming (ILP) is an incredibly powerful tool in combinatorial optimization. If we can formulate some problem as an instance of an ILP then solvers are guaranteed to find the global ...
2
votes
0answers
145 views

Maximum feasible subsystem problem (MaxFS) in 2 variables

Topic: The maximum feasible subsystem problem, which is generally NP-hard [1]. Question: Are there special algorithms in case of only 2 variables (2D linear constraints)? The problem seems to be a ...
6
votes
1answer
7k views

Formalization of the shortest path algorithm to a linear program

I'm trying to understand a formalization of the shortest path algorithm to a linear programming problem: For a graph $G=(E,V)$, we defined $F(v)=\{e \in E \mid t(e)=v \}$ and $B(v)=\{ e \in E \mid h(...
0
votes
1answer
1k views

Integer LP formulation and the existence of a solution

A film producer is seeking actors and investors for his new movie. There are $n$ available actors; actor $i$ charges $s_i$ dollars. For funding, there are $m$ available investors. Investor $j$ will ...
6
votes
2answers
898 views

A variant of the Assignment Problem

In my variant of the assignment problem I have a set $A$ of agents and a set (of possibly different cardinality) $T$ of tasks. Each agent needs to be assigned exactly $n$ or $n+1$ tasks, and each task ...
3
votes
0answers
44 views

A variant of the assignment problem (?) [duplicate]

Possible Duplicate: A variant of the Assignment Problem (Not a comp.scientist, but have the basic research. Please excuse me if I've overlooked anything obvious.) In my variant of the problem I ...
4
votes
1answer
183 views

Formulating a linear program s.t. only extreme point solutions are found

If there are many solutions to a linear program s.t. the objective function is minimized/maximized (= optimal solutions are on an edge of the polytope), how can I force an LP solver to find only an ...
23
votes
1answer
3k views

Sorting as a linear program

A surprising number of problems have fairly natural reductions to linear programming (LP). See Chapter 7 of [1] for examples such as network flows, bipartite matching, zero-sum games, shortest paths, ...
8
votes
2answers
1k views

Known facets of the Travelling Salesman Problem polytope

For the branch-and-cut method, it is essential to know many facets of the polytopes generated by the problem. However, it is currently one of the hardest problems to actually calculate all facets of ...
11
votes
2answers
1k views

Minimize the maximum component of a sum of vectors

I'd like to learn something about this optimization problem: For given non-negative whole numbers $a_{i,j,k}$, find a function $f$ minimizing the expression $$\max_k \sum_i a_{i,f(i),k}$$ An example ...
2
votes
2answers
3k views

Partition of a set of integer into 3 subsets of approximately equal sum

I'm having a very hard time trying to figure out how to solve this problem efficiently. Let me describe how it goes: "A hard working mom bought several fruits with different nutritional values for ...
3
votes
1answer
450 views

Efficient bandwidth algorithm

Recently I sort of stumbled on a problem of finding an efficient topology given a weighted directed graph. Consider the following scenario: Node 1 is connected to 2,3,4 at 50 Mbps. Node 1 has 100 ...
14
votes
2answers
445 views

Does every NP problem have a poly-sized ILP formulation?

Since Integer Linear Programming is NP-complete, there is a Karp reduction from any problem in NP to it. I thought this implied that there is always a polynomial-sized ILP formulation for any problem ...
11
votes
4answers
1k views

Finding exact corner solutions to linear programming using interior point methods

The simplex algorithm walks greedily on the corners of a polytope to find the optimal solution to the linear programming problem. As a result, the answer is always a corner of the polytope. Interior ...