Questions tagged [linear-programming]

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

263 questions
179 views

Linear programming with inequality constraints treated lexicographically

I'm trying to solve optimization problems of the form: $\min\{cx|Ax\preceq b,\;x\geq 0\}$, where $\preceq$ means lexicographic order; that is, the set of linear inequalities need only to be satisfied ...
29 views

Exploiting solution property in MIP

I am having to solve integer programming problem that has the following property: For feasible solution $x$ maps to a large set $S(x)$ or other admissible solutions and I can find the best solution ...
347 views

Why does this not prove $P\neq NP$?

Fiorini, Massar, Pokutta, Tiwary and De Wolf (Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Journal of the ACM 62(2):article 17, 2015; PDF, ArXiv) show any linear program that ...
39 views

Choose N pairs of (job, time slot) with a constraint on the number of different jobs

I am making a solver to choose the best assignment to a set of people for an event, given their availability (chosen in a set $T$ of time slots), jobs preferences (among $J$ possible jobs) and some of ...
76 views

Sorting the number sequence

I have $4$ variables $n_1, n_2, n_3, n_4 \in \mathbb N$ that sum to $N$. $4$ positive real constants $c_1 < c_2 < c_3 < c_4$. Given a particular tuple $(k_1,k_2,k_3,k_4)$, how do I find ...
203 views

Model disjunction in a $\{0,1\}$ integer linear program

How can I model logical OR as an integer linear program? $$(y_3 + y_4 + y_5 + y_6 = 2) \lor (y_2 = 1)$$ where $y_i \in \{0, 1\}$, $1$ = True and $0$ = False.
266 views

Efficiency of 0-1 linear programming w.r.t. number of binary variables

I am working on a problem in which I have to solve 0-1 linear programs, that is linear programs where some of the variables are binary, i.e. either 1 or 0. Lets say I have a fixed number of $n$ ...
92 views

Primal-dual schema in approximation algorithms

I was studying Set Cover via the Primal–Dual Schema on my own that I faced a problem in the following paragraph: Consider an LP-relaxation for an NP-hard problem. In general, the relaxation will not ...
14 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, ...
116 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 ...
58 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,...
198 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 ...
2k 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 ...
58 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$ ...
174 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 ...
52 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 ...
99 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 ...
62 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 ...
123 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, ...
161 views

419 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 ...
546 views

Is knapsack a Linear Programming problem? [closed]

Since Knapsack give Optimal solution as LP so is it also a LP or not ?
123 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 ...
4k views

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 \... 1answer 93 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,... 3answers 529 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 ... 1answer 329 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 ... 0answers 30 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 ... 1answer 321 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: ... 0answers 68 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 ... 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: ... 0answers 44 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 ... 1answer 1k 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 ... 1answer 104 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 ... 0answers 133 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 ... 0answers 37 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} = ]...
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 ...