Questions tagged [linear-programming]

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

98 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
0answers
77 views

Big M method for continuous variables

Is there any way to model the big M method for continuous variables? Something similar to this but $B, C \in \mathbb{R}_{\geq 0}$ and $A\in\{0,1\}$. Due to the precision problem, when the $B$ and $C$ ...
1
vote
0answers
292 views

maximizing absolute value in linear programming

I know that similar questions have been answered several times, and based on the answers, I attempted a solution to my problem. But I simply do not get the right results. The problem is as follows. I ...
1
vote
0answers
22 views

Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$

Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...
1
vote
0answers
132 views

How to solve this optimization problem with logarithmic objective function?

I have this optimization problem I have no idea how to solve it. Is Lagrange suitable for this problem? Thank you
1
vote
0answers
944 views

Restriction for greater than constraint in linear programming

I have a model that considers real values and that uses a binary variable $x$. In this model, the following conditions should apply: \begin{equation} x= \begin{cases} 0, & \text{if}\...
1
vote
0answers
178 views

LP realaxation for multicut problem with polynomial number of constraints

The integer linear programming formulation for the multicut problem for the given graph $G = (V,E)$ and distinguished source-sink pairs of vertices $(s_1,t_1),...,(s_k,t_k)$ is: \begin{alignat}{3} \...
1
vote
0answers
37 views

Time complexity bounds for the approximation of optimal values of bounded linear programs

Assume we are given a LP maximization problem defined by a linear functional $c^Tx$ and a non-empty feasible region $\{x:Ax\leq b\}$ that is known to be bounded by a hypercube of side $R>0$, say $[...
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 ...
1
vote
0answers
87 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 ...
1
vote
0answers
67 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
382 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
32 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
75 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
46 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
291 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
128 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
29 views

more than one min cut in a net flow

I know the answer to the question, but I still can't understand. I have the max flow and I need to determine whether there is more than one min-cut. I know that I need to run BFS from s in the ...
0
votes
0answers
28 views

Looking for fast LP solver algorithm for my Special case

I am interested to know what is the fastest algorithm (complexity wise) known to us to solve the following linear program. Due to its simplicity, I hope for a very fast algorithm. Your help is greatly ...
0
votes
0answers
22 views

Stable matching with dynamic preference lists

I have a set $F$ of $n_1$ families, a set $C$ of $n_2$ children ($n_1<n_2$) and a set $M$ of feasible one-to-one matchings of the families with the children. All the children have the same ...
0
votes
0answers
46 views

Special case of stable marriage

I have an instance of the stable marriage problem in which the first side $S_1$ has $n_1$ agents and the second side $S_2$ has $n_2$ agents with $n_2$ is very big in comparison to $n_1$. In addition, ...
0
votes
0answers
13 views

Why are basic feasible solutions the same as vertices geometrically?

The first line on the Wikipedia page for basic feasible solutions reads, ...
0
votes
0answers
32 views

Scheduling jobs on a single machine - minimising the weighted sum of completion times

Consider the following problem: there are $n$ jobs $\{1,...,n\}$, each has a processing time, $p_i$, a weight $w_i$, and an arriving time $r_i$. The goal is to minimise the weighted sum of completion ...
0
votes
1answer
63 views

Integer Linear programming formulation if then condition

I want to create constraints such that I can implement the following condition: Let A be an integer variable >= 0 with an upper bound of 12 I want to introduce the following variable B also an ...
0
votes
1answer
30 views

Writing a linear program to model balanced bin packing

Say we want to write a (MI)LP to model the following problem: Find a parking plan for a set of cars $K=\{1, ..., k\}$ with lengths $\lambda_i$. Parking is organised in lanes $P=\{1, ..., p\}$. ...
0
votes
0answers
75 views

Computing an optimal integer assignment given an optimal LP-solution

I modeled an ILP where I have a set of outfits and a set of friends with , all these friends should take one outfit with the lowest effort , considering the fact that these outfits differ in size, ...
0
votes
0answers
19 views

Formulate the mathematical model to find the optimal solution

A, B, C and D are standing on the east bank of a river and wish to cross to the west side using a boat. The boat can hold at most two people at a time. A, being the most athletic, can row across the ...
0
votes
0answers
28 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
15 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
8 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
24 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
59 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
42 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
1answer
378 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
125 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
88 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
15 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
67 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
208 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
47 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
185 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
82 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
635 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 ...
0
votes
1answer
38 views

How to write an OR constraint in MILP?

I want to write a constraint with ORs in a MILP. In particular, the following: $$x \ge c \lor x \le -c \lor x=0,$$ where $c$ is just a real number. Can anyone give me some hints?
-1
votes
1answer
678 views

On if then condition in linear programming?

I have variables $a,b\in\mathbb R$ and if $a>1$ I want $b=1$ or else $b=0$. Can this be encoded by linear programming (no integer variables)? Even $b<0.5$ and $b>0.5$ is ok.
-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 ...

1
2