# Questions tagged [linear-programming]

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

292 questions
Filter by
Sorted by
Tagged with
636 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.
47 views

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

### Converting nested absolute value into linear programming

I am having trouble writing the following optimization problem as a linear program (LP) $$\min_{x \in \mathbb R^2} \big| | x_{1} - a_{1} | - | x_{2} - a_{2} | \big|$$ where $a \in \mathbb Z^2$ is ...
35 views

### Example of $c^Tx' = c^Tx$ where x is the optimal solution for the linear relaxation (LP) of x' (ILP)

I am looking for an example where the optimal solution for the LP problem is equal to the optimal solution of the ILP problem, but the solutions are different. All I managed to think of was the ...
13 views

### Relating indexes for parameters and variables

I am trying to solve a referee assignment problem, but I simply can't think of a way to relate my variable to one of the parameters, and I hope that someone in here can help. I have the following ...
177 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} \...
100 views

### Can LP for matroid polytopes be solved using the greedy algorithm?

For general linear programming (LP), i.e. optimization of a linear objective over a general polyhedron, to the best of my knowledge/recollection one can use the simplex algorithm (or hypothetically, ...