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
1
vote
0answers
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 ...
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
0answers
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 ...
1
vote
0answers
39 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
0answers
270 views

Assign $m$ tasks to $n$ workers, with $m \geq n$

There are $n$ students that share the same apartment. At each evening, one of them must prepare dinner for everyone. There are $m$ evenings to schedule, with $m \geq n$, and you have to assign any ...
1
vote
0answers
123 views

Multidimensional 0-1 knapsack as the solution to 0-1 goal programming problem

I am trying to find the algorithm for the 0-1 goal programming problem. Actually I don't have any recent references for explicit algorithms, all the recent articles are about the modelling and not ...
0
votes
0answers
23 views

Minimum Clique Cover - Mixed Integer Programming

I have a general (undirected) graph with a set of nodes, a set of edges, and a weight for each edge. I want to find a minimum clique cover of the graph, that is, a partition of the graph into the ...
0
votes
0answers
19 views

Knapsack Problem Via Column Generation

If I were to solve the linear relaxation of a knapsack problem via column generation how could I model the master problem and pricing subproblem? Given a set $N$ of items with value $v_{i}$ and weight ...
0
votes
0answers
7 views

Linear Programming with constrained sum of rows and sum of columns

Is there a structure to the solution of the following linear program? $\min_{x_{ij} } \sum_{i,j} x_{ij} \mu_{ij}$ $s.t. \forall j, \sum_{i} x_{ij} = \beta_j,$ row sum $\forall i, \sum_{j} x_{ij} D_{...
0
votes
0answers
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:
0
votes
0answers
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 ...
0
votes
0answers
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 (...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
19 views

Linear Programming Formulation for Weighted Max-Cut

I am wondering if this Integer Linear Programming model I came up with as an exercise for my algorithms class is correct. The Problem Given a graph $G=(V, E)$, with a set of weights $W = \{w_{ij} \...
0
votes
0answers
27 views

Handling $AND$ and $OR$ cases in MILP?

Suppose I want to have an integer program for handling the cases $x_1>1\wedge x_2>1\wedge x_3>1\wedge\dots\wedge x_n>1\iff\delta=1$ $x_1>1\vee x_2>1\vee x_3>1\vee\dots\vee x_n&...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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....
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
66 views

How to model an ''affinity constraint'' in assignment problem

Working on an optimization problem formulated using the well known assignment problem. My decision variable is defined as follows : $$\alpha _{x}^{r,u} = 1\begin{cases} & \text{ 1 if } \mathbf{...
0
votes
0answers
23 views

Problem with formulating LP problem using binary variables

I have a problem with a task shown below. I have I am supposed to use big M method, but I don't know how to estimate/compute the minimal value of it and how to implement it into the equations. Any ...
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 ...
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, ...
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$ ...
0
votes
0answers
174 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 \...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
445 views

Max Flow / Linear Programming Reduction Variant

While studying max flow / LP, I came across a couple of reduction problems that gave me a bit of pause: Here are two variants of the standard Maximum Flow problem. Show that both of them can be ...
-1
votes
1answer
2k views

How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n

How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n ? for example : for n=10 1 2 3 4 10 20 30 40 100 200 the sub-sequence of length ...