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

Maximize the number of edges in subgraph

We are given a graph $G=(V,E)$ and we want an algorithm to find a set of vertices $U$ to maximize the following quantity : $\frac{|E(U)|}{|U|}$ where $E(U)$ denotes the number of edges in the subgraph ...
0
votes
1answer
227 views

LP formulation and integer solution existance

I’m trying to prove that the following problem has an integer optimal solution. This will hold if the corresponding linear program would have totally unimodular constraint matrix. We have $m$ pieces ...
0
votes
1answer
40 views

Why is the target function minimized at (0,0) if I can get to a negative number?

I just started learning LP and I saw this Q in my textbook: $$ min : -x -y \\ S.T. : x + 2y \le 3, 2x +y \le 3, x \ge 0, y \ge 0 $$ It is easy to see that the polygon created from these constraints ...
1
vote
1answer
376 views

Finding integrality gap for maximum weight independent set

One of the exercises I was given was to formulate Integer Linear Program (ILP) and relaxed version of it (LP) to solve the maximum weight independent set, and I need to find an integrality gap of my ...
0
votes
1answer
61 views

Objective function and constraint satisfaction over a set of multi-attributes elements

I'm looking for an approach to solve a problem consisting of maximizing an objective function over a set of discrete elements, while respecting a set of constraints. To illustrate my point, I'll try ...
1
vote
1answer
47 views

Simplex Algorithm: Why must the optimal value of the LP lie on the face or vertex of a polyhedron?

The feasible region of a Linear Program (LP) is $\{x \in {\bf R}^n: Ax \le b, x\ge 0 \}$. This is an intersection of halfspaces, a polyhedron. If the LP is bounded and feasible, its optimal value will ...
-1
votes
1answer
2k views

Expressing conditional in linear program [duplicate]

I have two variables $A$ and $B$, with $A$ being binary and $B$ is a real number where $B \ge 0$. My conditions are: if B > 0 A = 1 else A = 0 ...
0
votes
0answers
47 views

How to monitor and alter the value of decision variables using if then else

Assuming I have two 0-1 decision variables X[a,b] and Y[i,j,e,d] where : X[a,b] = 1 if a is in b 0 otherwise Y[i,j,e,d] = 1 if (i,j) is matched with (e,d) 0 otherwise. I need to ensure that if ...
2
votes
3answers
461 views

Max flow with priorities

I'm studying a simple max flow problem: Each type of object $a_1, a_2...$ can be stored in some of several stores $b_1,b_2...$. This is described by this graph: There are $|a_i|$ objects of the type ...
1
vote
1answer
538 views

Is 0-1 integer linear programming with only equality constraints NP-Hard?

We know that 0-1 integer linear programming is NP-Hard. What about 0-1 integer linear programming with only equality constraints? If so, how to prove it $$\min c^T x \text{ s.t. } Ax = b \quad x_i \...
4
votes
1answer
375 views

Linear programming restricted to rational coefficients

I'm reading the appendix A of Williamson's "the design of approximation algorithms" about linear programming. In the definition of a linear programming it restricted the coefficients of cost function ...
2
votes
0answers
147 views

How to setup a model for a guillotine cutting stock problem?

Backgroud. I'm reading papers about cutting stock problem (CSP). Said Ben Messaoud, Chengbin Chu, Marie-Laure Espinouse (2008) Characterization and modelling of guillotine constraints. European ...
2
votes
1answer
353 views

Aggregate planning with inventory

I am lost in formulating a mathematical model for my linear integer program. My problem is; how to include inventory and backlogging. The following is given: 1100 units can be produced each month ...
1
vote
2answers
190 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 ...
1
vote
0answers
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 ...
5
votes
2answers
358 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 ...
2
votes
1answer
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 ...
0
votes
1answer
80 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 ...
3
votes
2answers
227 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.
0
votes
1answer
304 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$ ...
1
vote
1answer
99 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 ...
0
votes
0answers
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, ...
3
votes
0answers
133 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
229 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 ...
1
vote
1answer
3k 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
61 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
199 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
54 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
102 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
65 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
129 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
165 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
458 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
134 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
285 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
186 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
58 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
47 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
101 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
79 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
1k 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
736 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
274 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
172 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
431 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
610 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
138 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
5k 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
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,...