The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [linear-programming]

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

277 questions
Filter by
Sorted by
Tagged with
208 views

Use complementary slackness to prove the LP formulation of max-flow only need polynomial number of path constraints

This is a homework problem for a class that ended 2 years ago, I'm learning it by myself. Consider a directed graph $D=(V,A)$, $s,t\in V$. $A=\{a_1,\ldots,a_n\}$. Let $P=\{p_1,\ldots,p_m\}$ be the ...
94 views

Start simplex method from feasible internal point

I have one algorithm that generates a feasible solution to a linear programming problem. However, it is very likely that this is not a corner point. This makes it not suitable for direct use as an ...
1k views

Algorithm to solve job assignment problem

Can someone suggest an algorithm to solve job assignment problem with condition? With condition means that some jobs cannot be done by some workers. For example table as shown below: In this table x ...
36k views

Express boolean logic operations in zero-one integer linear programming (ILP)

I have an integer linear program (ILP) with some variables $x_i$ that are intended to represent boolean values. The $x_i$'s are constrained to be integers and to hold either 0 or 1 ($0 \le x_i \le 1$)...
82 views

Issues with an optimization problem

I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$. I want to find the ...
104 views

Finding the required value of an algebric expression

I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$. I want to find the ...
1k views

NP complete problems that are solvable in polynomial time if the input (e.g. number of variables) is fixed?

I have seen some problems that are NP-hard but polynomially solvable in fixed dimension. Examples, I think, are Knapsack that is polynomial time solvable if the number of items is fixed and Integer ...
1k views

Job assignment problem

I want to solve job assignment problem using Hungarian algorithm of Kuhn and Munkres in case when matrix is not square. Namely we have more jobs than workers. In this case adding additional row is ...
14k views

Are all Integer Linear Programming problems NP-Hard?

As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming ...
3k views

Solving system of linear inequalities

I am trying to solve a system of inequalities in the following form: $\ x_i - x_j \leq w$ I know these inequalities can be solved using Bellman-Ford algorithm. ...
601 views

Finding a set of maximally different solutions using linear programming or other optimization technique

Traditionally, linear programming is used to find the one optimal solution to a set of constraints, variables and a goal (all described as linear relationships). Sometimes, when the objective is ...
151 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 ...
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 ...
554 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 ...
151 views

Maximum feasible subsystem problem (MaxFS) in 2 variables

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

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 ...
465 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 ...