# 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
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$ ...
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 ...
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 ...
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
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}\...
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} \...
37 views

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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
13 views

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 ...
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 ...
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\}$. ...
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, ...
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 ...
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 ...