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 ...