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.

86 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
275 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 ...
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 ...
70 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 ...
39 views

14 views

### Given a primal LP p, and another LP d, how can i formally prove that d is the dual problem of p?

Given a primal LP p, and another LP d, how can i formally prove that d is the dual problem of p? Specifically, i'm talking about the shortest s-t path: where: And the dual LP:
7 views

### How to input random values (constraints) of any variables in case of formulating Linear Programming Problem?

Suppose, Min 2x+3y Subject to, x=2,x=5,x=7 y=5, y=9 is a linear program. Where x holds the values 2 or 5 or 7 and y holds the values 5 or 9. Then what should the correct ...
19 views

### How is ellipsoid method a polynomial-time algorithm for LP?

I have always thought that the ellipsoid algorithm is an algorithm which can be used to solve LP in polynomial-time. However, what confuses me is the dependence on the ratio of volumes of the balls (...
19 views

### Creating a waste-optimizing algortihm for cutting a 1d block

I have a one-dimensional block of material. I run an analysis that divides the material into usable and unusable regions. In a manufacturing process, said material is cut and the unusable regions ...
23 views

### How can I quickly find the dual of a linear program?

In linear programming, the standard maximum form of a program (which we will call the "primal") is max $c^{tr}x$ subject to $Ax \le b$, $x \ge 0$ and the standard minimum form, the dual, is ...
38 views

### Traveling Salesman Problem with profit and time limit as ILP formulation

How to formulate the following problem? The salesman gains a profit $p_{i}$ when visiting a city i, trip between city i and city j costs $c_{ij}$ and takes $t_{ij}$ time. The trip must not exceed a ...
19 views

19 views

### When does total unimodularity implies integrality of solutions?

In Gartner & Matousek's book on linear programming, they prove the following lemma (Lemma 8.2.4, page 145): Let us consider a linear program with $n$ nonnegative variables and $m$ inequalities ...
36 views

### Branch and bound Dual Gap

Let's suppose we want to solve the knapsack problem using the Branch and Bound algorithm. I know that the algorithm ends when the optimality gap is = 0. However i have not understood how the dual ...
16 views

### How to formulate initial costs in linear programming?

Consider this example problem: Suppose the cost for setting up a factory to generate a pencil is 1000 and to generate a pen is 2000. The profit for each pencil is 10 and the profit for each pen is 12....
20 views

### Reducing weighted linear threshold gate to unweighted one

Reading "On the power of threshold circuits with small weights" by Siu and Bruck I have faced several problems understanding how unweighted linear threshold element can be built efficiently from the ...
17 views

### How to understand the separation phrase for generalized subtour constraints?

Suppose the constraints of our integer programming model consist of two parts: the polynomial-size formulations, that have a size (number of variables and constraints) which is polynomial w.r.t. the ...
195 views

### How to write an if then logical constraint given part of the input related to a decision variable?

I am trying to solve an assignment problem-like from a bi-objective persepctive where I have a marketplace of vendors proposing different machines with different types and specs. The goal is to select ...
90 views

### Conditional milp formulation

I have two binaries, $\alpha_{ts,it}$ and $\alpha_{ts,gshp} \in \{0,1\}$, and two reals $T_{it}$ and $T_{ts}$ which have upper and lower bounds. How can I model $\alpha_{ts,it}=1$ if the following ...
66 views

45 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 ...
178 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 ...
191 views

### Reducibility of finding Eulerian Path to Linear Programming

Consider any arbitrary directed, acyclic graph; how can we formulate the problem of finding a particular Eulerian path as a linear programming problem? It seems like there should be a relatively ...
67 views

### Writing linear programming constraint in a canonical form

I have a particular research problem that I'm formulating as a linear program. It's more or less an instance of the transportation problem, except there is one additional constraint that is proving ...