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
93 views

Efficient algorithm to compute the diameter of a convex set?

Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set? It is possible to do it efficiently for a set of points, but imagine that the ...
2
votes
1answer
31 views

When LP solution is ILP solution?

For many discrete problems, it's natural to consider their continuous relaxations. A common case is when instead of $x_i \in \{0, 1\}$ we allow $x_i \in [0, 1]$. In certain cases, the original problem ...
2
votes
1answer
32 views

Expressing a constraint of the form $\max(x_1,x_2) \ge q$ in a linear program

I am trying to solve an LP in which one of the constraints is mentioned below, $$\max(x_1,x_2) \ge q,$$ where $x_1 \ge 0$ and $x_2 \ge 0$. Is it possible to do in linear programming?
1
vote
0answers
46 views

Best algorithm/model to establish relevance between events utilizing mixed data type (Tags, Time, x_coordinate, y_coordinate)? [closed]

I'm building a relevance ranking system for incidents occurrence and prevention. My goal is to use four attributes to establish relevance: tag (About 500 tags), x_coordinate, y_coordinate and time. ...
1
vote
1answer
24 views

Finding optimal separating value

Problem description We are given two sorted arrays of even numbers: A and B. Values of A are generally supposed to be smaller than values of B. So we are asked to find a value X where X is an odd ...
0
votes
0answers
16 views

estimating optimal solution for LP with strict inequalities

I have an LP problem with strict inequalities that cannot be relaxed. I understand that most LP solvers require the problem to not have any strict inequalities as it is impossible to find an optimum ...
0
votes
1answer
31 views

Combinatorial optimization algorithm with constraints and objective function

I'm looking for an algorithm that will let me optimally select items from a set. These items have properties which are involved in defining constraints as well as the objective function. .e.g Say each ...
0
votes
0answers
19 views

What is the significance of Bellman-Ford and linear programming for scheduling and makespans?

CLRS exercise 24.4-9 says the following: Show that the Bellman-Ford algorithm, when run on the constraint graph for a system $Ax \leq b$ of difference constraints, minimizes the quantity $\max_i\{x_i\...
2
votes
1answer
20 views

Linear separability

I have an assignment in linear programming and this question was asked: given an input of two data sets $P_1,P_2$ containing points $(x,y)$, create a linear program that finds an equation of a line ...
0
votes
0answers
28 views

How to find the optimal assignment using the Kuhn-Munkres algorithm?

I managed to get through the Wikipedia article until the last step and I have implemented an algorithm that can reach the optimum. Unfortunately the article does not say anything about how can I make ...
0
votes
2answers
52 views

Infeasible linear programming reduce errors to find solution

Most normal linear programming problems look like this: We choose some point in the double shaded area that solves our optimizer and we're good to go. However, I've come across a problem where it's ...
1
vote
1answer
18 views

Approximate LP for vertex cover problem

I am studying the topic of vertex cover on coursera and how it can be solved approximately by linear programming. Suppose the optimal solution for the vertex cover problem is $OPT$. I do not ...
0
votes
0answers
26 views

IF THEN condition in Linear Program

I have the following condition in an LP problem. I have a variable $x_i \in i = 1,2,..7$ and I need to constrain the problem via: if $x_1$ >5 then $x_2 \leq 30$ I'm stumped on how to formulate that ...
2
votes
1answer
28 views

What is the best algorithm to find the optimal path in reducing company's real-estate footprint?

I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it. Here is the problem: A company is in ...
1
vote
0answers
28 views

IP Programming - objective function ist not a function BUT a table

Here is a short description of my problem: Part of my objective function is not a regular function. Instead it's a table. You can see a short extract here: So if the height is smaller or equal to 300 ...
0
votes
1answer
41 views

Integer programming with indicators

I have the following question, and I need to write it as an integer programming problem: A manager of a company wants to by presents to his 100 employers. He can buy the presents from two different ...
1
vote
1answer
21 views

linear time nash equilibirum aproximations for two player zero sum games

I'm working on an AI for a game where I'd like the game where each player has hundreds of moves to select from and so the game matrix has 10s of thousands of entries. The game is however zero sum. ...
0
votes
0answers
27 views

Formulating if-then constraints in linear binary programming

From a stock of various computer accessories of different brands, the optimization problem requires deciding to keep or discard products. The decision should be made maintaining the following if-then ...
-1
votes
3answers
44 views

Which topics of mathematics should I need to learn to be a good app developer?

I'm 29 years old. I couldn't continue my studies after grade 10 due to some financial issues and I didn't have time to practice mathematics. It's been more than 11 years since I left studies. Now I ...
2
votes
0answers
194 views

Strong polynomial time algorithm for deciding LP feasibility

Let $$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
1
vote
2answers
31 views

Linear programming vs integer linear programming

Given $A,b$, let $Ax \le b$ be an instance of linear programming on the variables $x=(x_1,\dots,x_n)$. Assume that the constraints $0 \le x_i$ and $x_i \le 1$ are included in $A,b$. Suppose that ...
0
votes
0answers
12 views

Integer Linear (ILP / MILP) Formulation for Collision Avoidance of Convex Polytopes / Polyhedra

I am looking for a possibility to avoid the collision of two convex polytopes using (mixed integer) linear programming. I know how I can detect a collision (Akgunduz, A., Banerjee, P., and Mehrotra, S....
2
votes
0answers
42 views

Randomized Assignment Problem

Given $x_1,...,x_n,y_1,...,y_n\in \mathbb{R}^d$ find a permutation matrix $P\in\mathbb{S}_d$ that minimizes $\sum_{ij}P_{ij}|x_i-y_j|$. This is an assignment problem and can be solved in $O(n^3+n^2d)$ ...
3
votes
0answers
49 views

Algorithm to cut a sphere in half with a plane and maximize the number of points on the sphere surface on one side of the plane

Consider a sphere with a coordinate system like the earth. There are $N$ points on its surface at random positions. For all the infinite planes that cuts the sphere exactly in half (i.e. the sphere's ...
2
votes
1answer
33 views

In what cases is solving Binary Linear Program easy (i.e. **P** complexity)? I'm looking at scheduling problems in particular

In what cases is solving Binary Linear Program easy (i.e. P complexity)? The reason I'm asking is to understand if I can reformulate a scheduling problem I'm currently working on in such a way to ...
0
votes
0answers
60 views

Is it possible to form this as a linear program?

My problem is as follows: I have some number $n\in \mathbb{N}$ of items all of size $s\in \mathbb{N}$ that need to be fit into a distributed storage of sizes $[b_1, b_2, ..., b_m], \forall i, b_i \in \...
4
votes
0answers
47 views

Repeated linear programming with similar (not identical) problems

I have multiple linear programming problems of the form: $$ Minimize\{c^{T}\cdot x\} s.t. Ax = b, x \ge 0 $$ Where $c$ and $A$ are fixed for all the problems. Is there any way to utilize that for a ...
1
vote
0answers
93 views

Minimum vertex cover and odd cycles [closed]

Suppose we have a graph $G$. Consider the minimum vertex cover problem of $G$ formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $...
1
vote
1answer
66 views

How to prove that the dual linear program of the max-flow linear program indeed is a min-cut linear program?

So the wikipedia page gives the following linear programs for max-flow, and the dual program : While it is quite straight forward to see that the max-flow linear program indeed computes a maximum ...
0
votes
1answer
56 views

Question about the CLRS Linear Programming chapter

I'm currently reading the CLRS Linear Programming chapter and there is something i don't understand. The goal is to prove that given a basic set of variables, the associated slack form is unique They ...
2
votes
1answer
116 views

Minimum vertex cover algorithm with linear programming

Consider the following algorithm: given a graph $G$ with $n$ vertices, set up a linear programming problem LP where there is a variable $x_i$ for each vertex $v_i$ of $G$, each variable can take value ...
6
votes
2answers
203 views

Odd cycle transversal and linear programming

Suppose we have a graph $G$ with $n$ vertices. Suppose LP is a linear programming problem where there is a variable for each vertex of $G$, each variable can take value $≥0$, for each odd cycle of $G$ ...
4
votes
1answer
276 views

How to calculate the dimension of a convex polyhedron?

A convex polyhedron can be represented by a set of linear inequalities. If the inequalities involve $n$ variables, then the polyhedron can be $n$-dimensional, but it can also be of a smaller dimension ...
1
vote
0answers
27 views

Seeking guidance on what to read for Feasibility Binary IP with ''almost total unimodular'' (-1, 0, 1)-Coefficient Matrix and No Obj Function

I am working on an algorithm in graph theory which I wish to prove it's polynomiality/NP-hardness. I am investigating a binary variable (0, 1) integer program which has the coefficient matrix ...
2
votes
0answers
31 views

Ensuring integral result from integral linear program [closed]

An integral linear program is one that has a maximizer that is integral. Sometimes it's possible to prove that a particular LP has this property, for example by proving that it's constraint matrix is ...
0
votes
1answer
50 views

In a LP problem Ax = b, how to solve for A instead of x?

I have a multi-objective linear programming problem of the form Ax = b, where A is a matrix and x and b are vectors. x is known, and I'm looking to minimise each row of b by solving for A. Constraints ...
1
vote
1answer
55 views

Converting If-else integer equation to Linear Programming

I have an if-then-else condition with three binary variables A, B and C: if A + B = 1 then C = 0 How do I express this as an integer linear program with equality ...
0
votes
0answers
45 views

more than one min cut in a net flow

I know the answer to the question, but I still can't understand. I have the max flow and I need to determine whether there is more than one min-cut. I know that I need to run BFS from s in the ...
0
votes
0answers
34 views

Looking for fast LP solver algorithm for my Special case

I am interested to know what is the fastest algorithm (complexity wise) known to us to solve the following linear program. Due to its simplicity, I hope for a very fast algorithm. Your help is greatly ...
2
votes
0answers
18 views

Integrality gap in Online Problems and adaptation to competitive ratio

As we all know, in offline problems it is common practice to calculate the integrality gap to get some bound on the approximation ratio of the integral solution. Now this gap ($IG:=\frac{OPT_{frac}}{...
2
votes
1answer
37 views

Constrain traveling salesman: visit a given city within a given distance from start

I would like to add an additional constraint to the traveling salesman problem: that a given city is visited within a given distance (say 100) from start. Is there ...
2
votes
2answers
84 views

Is there a dynamic programming solution to the student allocation problem?

The student project allocation problem I am trying to solve goes as follows. There is a set $S$ of students and $P$ of projects such that $|S| \leq |P|$. Each student makes a top $3$ of their ...
1
vote
3answers
50 views

Linear Programming Problem - what is feasible size for solution on a PC

I need to get feeling for the feasible size of a LPP, that can be solved on a PC. Say, its a good one (8 cores @ 3+GHz, 64GB RAM). We also assume that number of variables is close to the number of ...
1
vote
1answer
43 views

Check if a row is in the span of a matrix

Suppose I have a matrix $M$ over $GF(2)$ with rows that represent a system of linear equations: A xor B xor C = 1 A xor B xor D = 1 X xor A xor Z = 0 etc... For a new external row, I want the ...
1
vote
1answer
33 views

Finding all rows of 2 variables using Gaussian Elimination

Suppose I have a system of linear equations. Using Gaussian elimination, I can determine whether a solution exists, and even find a valid solution. During the elimination, I can combine rows together,...
3
votes
2answers
168 views

Complexity of linear programming

I have a basic question, if I can model a problem $(P)$ by a linear program, can we say that $(P)$ is polynomial? Linear programs can be solved using simplex, and it was proved that simplex run in ...
0
votes
1answer
45 views

How to write an OR constraint in MILP?

I want to write a constraint with ORs in a MILP. In particular, the following: $$x \ge c \lor x \le -c \lor x=0,$$ where $c$ is just a real number. Can anyone give me some hints?
2
votes
1answer
50 views

Labeled points in $\{0,1\}^n$ such that every linear separator requires exponential weights

I want to find labeled samples in $\{0,1\}^n$ such that the Perceptron algorithm takes $2^{\Omega(n)}$ steps to converge. One way to do this would be to find a sequence of labeled examples that are ...
0
votes
0answers
23 views

Stable matching with dynamic preference lists

I have a set $F$ of $n_1$ families, a set $C$ of $n_2$ children ($n_1<n_2$) and a set $M$ of feasible one-to-one matchings of the families with the children. All the children have the same ...
0
votes
1answer
41 views

Why is a Knapsack problem not an LP problem?

We know that LP can solve optimization problems that have linear constraints and linear objective functions. A knapsack problem can be formulated into a linear objective function (because it is just ...

1
2 3 4 5
7