Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
15 views

Scheduling problem with performance based selection

I would like to solve a scheduling problem where, I am able to maximize the number of consecutive shifts a employee may have, therefore minimizing the likelihood of them not showing up for a single, ...
3
votes
0answers
155 views

2-approximation edge-cover algorithm using primal-dual method

The problem Given an undirected graph $G=\left(V, E\right)$ and positive edge weights $w_e$, design a 2-approximation algorithm based on the primal-dual principle. So far I managed to represent the ...
2
votes
0answers
59 views

Adding linear constraint to continuos LP to improve performance

Consider a standard LP minimization problem of the form $$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & A x = b\\ & x \geq 0\end{array}$$ Should I expect, on average,...
1
vote
1answer
252 views

Warm starting LP solver at non-basic feasible solution

I'm approaching some continuous optimization problems by considering discrete approximations of them at different resolutions. Those discrete approximations can be solved with linear programming ...
2
votes
1answer
4k views

Converting if-then-else condition to integer linear programming with equality constraints

I have an if-then-else condition with three binary variables $A$, $B$ and $C$: if A = 1 then B = 1 else B = C How do I express this as an ...
0
votes
0answers
66 views

Debugging the issues on Megiddo's algorithm

I have done code for the algorithm to obtain the Optimal Basis but as I calculate the optimal solution $Xb=B^{-1}b$, I only get the correct value for some of the variables. For some variables, $Xb_i$ ...
1
vote
1answer
258 views

Maximize pairings subject to distance constraint

I have a list of people's locations on a world map and want to pair nearby people up such that the number of pairs is maximized. For example, subject to the constraint that paired people are within ...
1
vote
0answers
87 views

Simplex algorithm experimental complexity

For a school project I am doing on linear programming, I've implemented the simplex algorithm in Python. I was hoping to check the complexity on a number of matrices. Preferably, they would have ...
0
votes
1answer
109 views

Transform Standard-Dual program to Canonical-Dual program

Say I have the following Standard-Dual linear program: $$max<\vec b, \vec y>$$ $$s.t.:A^Ty \le \vec c$$ $$\vec y \ge \vec 0$$ Is there a way to transform it to a Canonical-Dual and equivalent ...
1
vote
0answers
67 views

Column Generation - Worst dual bound when adding various columns per iteration

I'm implementing a Column Generation algorithm. The pricing problem, in general, find more than one column with negative reduced costs(the master is a min problem). If i add only the most negative ...
1
vote
0answers
138 views

Simplest linear programming solver? [closed]

In a programming contest I've encountered a problem which is for sure a linear programming problem. I know quite a lot about LP (the simplex method, its exponential complexity, interior point methods, ...
2
votes
3answers
169 views

Integer linear programming formulation of formula in DNF

I have multiple sets, e.g., $$\{1, 2\}, \{2, 3, 4\}, \{1, 4\}$$ Each variable $1, 2, 3, 4$ is binary. I need to represent the following condition without additional variables $$(1 \land 2) \lor (2 \...
0
votes
2answers
676 views

When does strong duality fail in linear programming?

When does strong duality fail in linear programming? I have considered the case when both primal and dual solutions are infeasible, but then there are no optimal solutions at all.
1
vote
2answers
150 views

Expressing the condition as a set of linear constraints

Express the condition "$x = 0$ if and only if $y = 0$" as a set of linear constraints, where $x,y$ are integers such that $ - 5 \le x \le 8$ and $0 \le y \le 1$
2
votes
2answers
340 views

Casting to boolean in integer linear programming

I have variables $x \in \{0,1,\dots,5\}$ and $y \in \{0,1\}$, where $$y = \begin{cases} 0 & \text{if } x = 5\\ 1 & \text{if } x \neq 5\end{cases}$$ My problem is to maximize $y$. How can I ...
1
vote
1answer
243 views

Set Cover and additional constraints

Consider the following bipartite graph: Each node in red color represents a warehouse $w = \{ 1,2,3\} $. For this example we have three warehouses located at different locations. Each warehouse has a ...
3
votes
0answers
66 views

Computing the line equations of two crossing tangents in a point set separated by a vertical line?

I have provided a picture as an example. We have two point sets, P and Q. P is to the left of this vertical line (named x = x0), and Q is to the right of it. The goal is to compute the line equations ...
1
vote
0answers
53 views

Computing line equations of two crossing tangents [duplicate]

Pictured is the problem in question. How do I compute the line equations for these two crossing tangents? These lines happen to be supporting two point sets for two convex hulls.
2
votes
0answers
117 views

Formalizing an intuitive linear programming proof

My professor has asked me to prove the following: Prove that we can use an algorithm for linear programming to solve linear inequality feasibility problems. The number of variables and ...
4
votes
3answers
80 views

Need help optimizing the loading of passengers on small airplanes

I work for a small non-profit that provides transportation for people who need medical treatment. We connect volunteer private pilots who fly people in their own (small) aircraft, typically 3-5 seats. ...
3
votes
1answer
2k views

Express a “complex” IF-Statement to Linear Programming

In our current project we need to model the following if-statement in linear programming: If T1 < b < T2 then z = s else z = 0 where T1 and T2 are two ...
3
votes
1answer
1k views

Linear programming formulation for the single-source shortest path problem

In this course lecture; section 5.1, single-source shortest path (SSSP) is formulated as the following linear program (LP): \begin{align} \max &\sum d_u \\ \text{subject to} & \\ d_v &\le ...
1
vote
0answers
381 views

approximation algorithm of k-set packing

For my application problem, I am looking for an easy to implement or source code for approximation algorithm for maximum k-Set Packing problem. Given a universe $U$ and a family $ \mathcal{S} $ of ...
0
votes
0answers
207 views

basic linear programming - how to find feasible solutions

I'm new to linear programming and can't wrap my head around something. Let P be a LP in standard form $$\begin{array}{ll} \text{maximize} & t x\\ \text{subject to} & r x \leq s\\ & x \...
4
votes
1answer
474 views

Minimum spanning tree formulation as integer program

The minimum spanning tree problem can be solved in polynomial time via Kruskal's or Prim's algorithm. However, every integer program I have seen that corresponds to the MST problem require a ...
0
votes
1answer
852 views

Is knapsack a Linear Programming problem? [closed]

Since Knapsack give Optimal solution as LP so is it also a LP or not ?
2
votes
0answers
165 views

Why is my Forrest-Tomlin update worse than recomputing LU?

I wrote a simple C++ implementation of the revised simplex method that recomputes the LU decomposition of the basis from scratch on each iteration. I have to solve problems with many variables but few ...
4
votes
3answers
6k views

“Greater than” condition in integer linear program with a binary variable

How can one model the following condition in an integer linear program? $$A = \begin{cases} 1 & \text{if } B > C\\ 0 & \text{otherwise}\end{cases}$$ where $A \in \{0,1\}$ and $B, C \in \...
2
votes
1answer
112 views

Internal tangent intersection of two point sets in linear time

I need to find the intersection of the internal tangents of two point sets $V_a, V_b$ in $\mathbb{R}^2$, defined via their convex hulls. We can assume that the sets are disjoint and linearly separable,...
2
votes
3answers
604 views

Closest arithmetic progression to an array

Given an array of $N$ integers, having the option to increase or decrease its elements, the problem is to find the closest integer arithmetic progression. That corresponds to the smallest difference ...
2
votes
1answer
436 views

Comparing dual of a canonical primal program - Directly and by dual of the standard program

I have it as a homework question to compare dual programs in the following way: Take a canonical program and write its dual Take the same canonical program, write it as a standard program, take the ...
1
vote
0answers
31 views

Two adjacent vertices in a polytope uniquely minimize some linear form

In linear programming, if we model the solution as a polytope, every vertex is a solution. I'm trying to prove the following statement: If $x$ and $y$ are two solutions with $n-1$ joint ...
1
vote
1answer
595 views

Linear programming, Checking a constraint based on condition

I have a constraint $X \ge Y$ in a Linear programming formulation, where both $X$ and $Y$ are binary. I want to check this constraint on a condition like: ...
1
vote
0answers
75 views

Polynomial LP-based algorithm for cost minimization of DAG weights modification

Given a DAG $G=(V,E)$, with non-negative weights $ w_e \, \forall e\in E$, we want to modify (increase/decrease) the weights such that: $\forall u,v\in V$ and $\forall p_1\neq p_2 $ paths from $u$ to ...
3
votes
1answer
1k views

Converting If-else condition to Linear Programming

I have a constraint in a linear programming formulation with two variables: $X \ge Y$ To which I want to apply the following if-else conditions: ...
0
votes
0answers
46 views

Using Genetic Algorithms for volatile problems

Suppose I am looking at an optimization problem with a large number of interconnected constraints, but the solution is - in some regions - extremely volatile (With volatile I mean: small mutations ...
12
votes
1answer
2k views

Does linear programming admit a strongly polynomial-time algorithm?

The linear programming problem: find a strongly-polynomial time algorithm which for given matrix A ∈ Rm×n and b ∈ Rm decides whether there exists x ∈ Rn with Ax ≥ b. I know that Steve Smale's lists ...
3
votes
1answer
123 views

Performance gain by implementing streamlined simplex

I have to solve linear transportation problems for a research project. Ideally, I should design an application that will recieve the problem data as an input and then show some results. The size of ...
3
votes
0answers
182 views

Enumeration of corner points of a polytope [closed]

Given a linear program, is there any library or available code to enumerate all the corner points of a polytope ?. PS: Simplex method finds one corner point depending on the objective, but I need to ...
1
vote
0answers
46 views

Modelling belonging of a real variable to an interval by a boolean variable

In the context of a MILP, I have variables $x_{t} \in \mathbb{R}$ which have a lower bound $x^{min}$ and an upper bound $x^{max}$. Let $I_{1} = [x^{min},a_{1}], I_{2} = ]a_{1}, a_{2}], ..., I_{n} = ]...
1
vote
1answer
68 views

Minimum covering problem formulation

Shouldn't I post this question on mathematics.stackexchange.com? Let be an airlaine company which has to affect its aircrew to several flights. We group som flights in subset, every flights of a ...
7
votes
1answer
268 views

Given 2 sets of n points: minimize sum of traveled distances

I am given two sets $S, T$ each of $n$ points in $\mathbb{R}^k$, I want to find a bijection $a : S \rightarrow T$, such that $$\sum_{s \in S} d(s, a(s))$$ gets minimized, with $d$ being the Euclidean ...
3
votes
1answer
1k views

How to solve an ILP problem with conditions in an objective function?

I have came accross this link. I have an integer linear programming (ILP) problem $$\max_{(x_1, x_2,\ldots, x_n)}\sum_{i=1}^n x_i\cdot f(x_i),$$ $$\text{subject to } \begin{cases} ..., &(1)\\ L≤...
2
votes
1answer
157 views

A dynamic programming problema on containers and product

We have two production lines - product and container (two integer arrays product_list[N] and container_list[M]). If the volume of a container is equal or larger than that of a product, then we could ...
2
votes
0answers
46 views

Implications of the class of problems with parallel solutions being not P-complete for optimization of matrices

I am not a specialist on computational complexity theory. I do work on optimization and I am currently researching about the implications of the class of problems with parallel solutions (NC) being ...
0
votes
0answers
185 views

Small LP for directed min cut?

Undirected min cut has a well known poly sized LP formulation by expressing the problem as one of finding a certain metric on the vertices minimizing the sum of distances on edges. Can this be ...
8
votes
3answers
2k views

Finding all solutions to an integer linear programming (ILP) problem

My problem is to find all integer solutions to an ILP. As an example, I'm using an ILP with two variables, but I may have more than two variables. I describe the method I currently use to solve this ...
3
votes
0answers
53 views

Heuristic for making set of indexes in an array/matrix with generating functions/patterns

I am trying to find a lead on how to solve or find a heuristic the following kind of problem: Given an array/matrix with entries of only 1s and 0s, using a set of looping functions/patterns of a ...
3
votes
1answer
133 views

An integer linear program

I have the following problem: Given positive integers $a, b, c, d, n$, compute the maximum possible value (which is garuanteed to be less than $10^9$) of the function $$f(x,y) = cx + dy$$ where ...
1
vote
1answer
35 views

Comparing the sizes of two search spaces by comparing their numbers of possibilities

I am trying to solve an optimisation problem and come up with two Integer Linear Programming models. For each model, I am able to find a function that calculate the number of possibilities based on ...

1 2 3
4
5
7