Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
1
vote
3answers
46 views

Linear Programming Problem - what is feasible size for solution on a PC

I need to get feeling for the feasible size of a LPP, that can be solved on a PC. Say, its a good one (8 cores @ 3+GHz, 64GB RAM). We also assume that number of variables is close to the number of ...
0
votes
1answer
37 views

In a LP problem Ax = b, how to solve for A instead of x?

I have a multi-objective linear programming problem of the form Ax = b, where A is a matrix and x and b are vectors. x is known, and I'm looking to minimise each row of b by solving for A. Constraints ...
1
vote
1answer
36 views

Converting If-else integer equation to Linear Programming

I have an if-then-else condition with three binary variables A, B and C: if A + B = 1 then C = 0 How do I express this as an integer linear program with equality ...
1
vote
1answer
33 views

Gaussian Elimination: Check an assignment

This question is similar to Check if a row is in the span of a matrix Suppose I have a matrix $M$ over $GF(2)$ with rows that represent a system of linear equations: A xor B xor C = 1 A xor B xor ...
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
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
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 ...
1
vote
0answers
14 views

Integrality gap in Online Problems and adaptation to competitive ratio

As we all know, in offline problems it is common practice to calculate the integrality gap to get some bound on the approximation ratio of the integral solution. Now this gap ($IG:=\frac{OPT_{frac}}{...
1
vote
0answers
28 views

Gaussian Elimination, find all rows equal to zero

I have a system of integer linear equalities modulo P a large prime. Using GE, I place the matrix in row echelon form to check if there are solutions. After that, I want to check if there is any ...
2
votes
1answer
33 views

Constrain traveling salesman: visit a given city within a given distance from start

I would like to add an additional constraint to the traveling salesman problem: that a given city is visited within a given distance (say 100) from start. Is there ...
2
votes
2answers
48 views

Is there a dynamic programming solution to the student allocation problem?

The student project allocation problem I am trying to solve goes as follows. There is a set $S$ of students and $P$ of projects such that $|S| \leq |P|$. Each student makes a top $3$ of their ...
1
vote
1answer
39 views

Check if a row is in the span of a matrix

Suppose I have a matrix $M$ over $GF(2)$ with rows that represent a system of linear equations: A xor B xor C = 1 A xor B xor D = 1 X xor A xor Z = 0 etc... For a new external row, I want the ...
1
vote
1answer
32 views

Finding all rows of 2 variables using Gaussian Elimination

Suppose I have a system of linear equations. Using Gaussian elimination, I can determine whether a solution exists, and even find a valid solution. During the elimination, I can combine rows together,...
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?
3
votes
2answers
117 views

Complexity of linear programming

I have a basic question, if I can model a problem $(P)$ by a linear program, can we say that $(P)$ is polynomial? Linear programs can be solved using simplex, and it was proved that simplex run in ...
63
votes
3answers
40k views

Express boolean logic operations in zero-one integer linear programming (ILP)

I have an integer linear program (ILP) with some variables $x_i$ that are intended to represent boolean values. The $x_i$'s are constrained to be integers and to hold either 0 or 1 ($0 \le x_i \le 1$)...
2
votes
1answer
42 views

Labeled points in $\{0,1\}^n$ such that every linear separator requires exponential weights

I want to find labeled samples in $\{0,1\}^n$ such that the Perceptron algorithm takes $2^{\Omega(n)}$ steps to converge. One way to do this would be to find a sequence of labeled examples that are ...
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
1answer
32 views

Why is a Knapsack problem not an LP problem?

We know that LP can solve optimization problems that have linear constraints and linear objective functions. A knapsack problem can be formulated into a linear objective function (because it is just ...
0
votes
1answer
377 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
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, ...
2
votes
0answers
37 views

Half-integral linear programs

What are some of the known properties of half-integral linear programs? That is, linear programs for which the solution vector always takes its values in the set $\{0, \frac{1}{2}, 1\}^n$. I'm asking ...
8
votes
3answers
10k views

Linear programming with absolute values

I know that sometimes we can use absolute values into the objective functions or constraints. Is it always possible to use them, anywhere ? Example of use of absolute values: ...
0
votes
0answers
13 views
2
votes
1answer
391 views

Some Questions related to Linear programming

I have some question related to the Linear Programming problem: If we have an objective function that needs to be maximized and let the feasible region be unbounded such that there is no finite ...
2
votes
1answer
48 views

Linear programming over a finite field

I have a system of equations $Ax = b$ over some finite field $\mathbb{Z}_p$ and want to find a feasible solution. I'm sure this problem is NP-hard, but I'm struggling to find any literature on the ...
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
1answer
54 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 ...
7
votes
1answer
275 views

Can the solution to a POMDP be found using linear programming?

It is known that Markov decision processes (MDPs) can be solved using linear programming (see page 24 of Carlos Guestrin's PhD dissertation). The linear program is: $$min_{V(x)} \sum_x \alpha(x)V(x)\\...
6
votes
4answers
926 views

Maximum set packing and minimum set cover duality

I read that the maximum set packing and the minimum set cover problems are dual of each other when formulated as linear programming problems. By the strong duality theorem, the optimal solution to the ...
1
vote
1answer
66 views

Can the KenKen puzzle be solved using the same ideas as for Sudoku?

There are many ways of solving Sudoku puzzles, however two good approaches are the Algorithm X and solving using Linear programming. Is it possible to solve the KenKen puzzle using Algorithm X (...
0
votes
1answer
31 views

Standard ILP Formulation of Travelling salesman problem: Purpose of subtour elimination constraints?

Consider the Traveling Salesman Problem: Input: $n$ cities, distances $c_{ij}$ for each ordered pair $(i,j)$ of them. Output: Find a shortest round tour visiting every city exactly once. I came ...
2
votes
0answers
93 views

PTAS for Multiple Knapsack with Uniform Capacities, fixed number of Knapsacks

Consider the following problem: We are given a collection of $n$ items $I = \{1,...n\}$, each item has a size $0 < s_i \le 1 $ and a profit $ p_i > 0 $. There are $m$ (a fixed number) of unit-...
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 ...
4
votes
3answers
6k views

“Greater than” condition in integer linear program with a binary variable

How can one model the following condition in an integer linear program? $$A = \begin{cases} 1 & \text{if } B > C\\ 0 & \text{otherwise}\end{cases}$$ where $A \in \{0,1\}$ and $B, C \in \...
6
votes
0answers
104 views

Time complexity of linear programming with small number of variables

I have a linear program with $n$ variables, $m$ constraints and $O(nm)$ bit total length (the constraint matrix contains only zeros and ones). I am interested in finding a polynomial time algorithm ...
0
votes
1answer
21 views

Bin Packing variant

I am currently struggling with a bin packing variant, where we have fuel and compartments of a tank truck. Some industry constraints apply, but the whole picture is that you must fit the total volume ...
2
votes
0answers
28 views

LP - Dual variable is zero implies primal constraint unnecessary?

Say I have a primal program P with n variables and c constraints. Let's say that I have an optimal solution for the dual program D, in which the y1, the variable related to the first constraint in P, ...
0
votes
2answers
43 views

LP - given m constraints for 2 variables find maximal radius of circle

Given $m$ constraints for 2 variables $x_1,x_2$ : $d_ix_1 + e_ix_2 \leq b_i$ for $i = 1,...m$ need to create a linear program that finds the maximal radius of a circle such that all the points ...
2
votes
1answer
77 views

Integrality gap and LP-rounding

I have a doubt about integrality gap. If I know that there is no integrality gap for a given problem, i.e.: $$\frac{\mathrm{OPT}(\mathrm{ILP})}{\mathrm{OPT}(\mathrm{LP})} = 1 \text{ (right?)},$$ ...
3
votes
2answers
172 views

Examples of Analysis of Branch and Bound Method

I am solving a graph problem, which can be formulated as an integer programme. Based on computer experiments, it seems that the branch and bound method works well. I would like to analyse the running ...
2
votes
0answers
65 views

Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks

I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
2
votes
2answers
54 views

Linear programming: reduce a contstraint that includes minimun

I have an almost linear programme. However one of the constraints has a form $z = min(x,y)$ (all the other things are linear in the model). Is there a way to substitute this with something (or ...
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, ...
8
votes
3answers
2k views

Finding all solutions to an integer linear programming (ILP) problem

My problem is to find all integer solutions to an ILP. As an example, I'm using an ILP with two variables, but I may have more than two variables. I describe the method I currently use to solve this ...
13
votes
3answers
2k views

Cast to boolean, for integer linear programming

I want to express the following constraint, in an integer linear program: $$y = \begin{cases} 0 &\text{if } x=0\\ 1 &\text{if } x\ne 0. \end{cases}$$ I already have the integer variables $x,...
1
vote
0answers
18 views

Why maximum-matching algorithm falls into the category of fill-reducing algorithms?

My understanding is that "maximum matching" (or "maximum transversal") are algorithms to pre-order matrix to increase the numerical stability. In Timothy Davis' book Direct Methods for Sparse Linear ...
2
votes
1answer
41 views

Determine aproximation factor in a greedy algorithm

Suppose we have n food dishes associated to a cost c, and we have i guests such that each one of them has a certain number of preferences. We want to choose a menu such that we minimize the cost and ...
2
votes
3answers
434 views

Linear programming maximizes the minimum distance problem

I have a problem with creating an equation for linear programming solver. Company wants to open stores in k cities. For the purpose of even coverage of the entire ...
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 ...

1
2 3 4 5
7