Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
47 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 ...
-2
votes
0answers
16 views

Find a letter in a sequence using algorithms

Let us consider the following searching problem Input: A sequence of n numbers A:[a1, a2, .... an] and a value $v$. Output: An index i such that $v$=A[i] or the special value NIL if v does not. ...
7
votes
1answer
269 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
888 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
45 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
27 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
86 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
28 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
25 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\}$. ...
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
98 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
25 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
42 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
69 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
165 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
52 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
53 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
74 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
1answer
355 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 ...
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 ...
11
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,...
0
votes
1answer
111 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 ...
1
vote
0answers
17 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
37 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
248 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
18 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
vote
0answers
62 views

Can this graph-ordering problem be solved with LP?

I have a modelling problem that I am trying to solve with LP. (More specifically, in Python using PuLP or Pyomo). I am not terribly knowledgeable in this area and have been struggling to find the ...
2
votes
0answers
36 views

Finding a non negative combination of integers that adds up to a certain number [duplicate]

I have a set of positive numbers: ${n_1,n_2,...n_k}$ s.t. $n_1>n_2>\dots >n_k$. I want to find an array of non-negative integers $c_1,c_2,\dots,c_k$ such that $$n_1c_1 + n_2c_2 + \dots + ...
2
votes
1answer
105 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 vertices of the graph, that is, a partition of the ...
1
vote
1answer
127 views

If-Then with disjunctions (OR) in Integer Linear Programming (ILP)

I have the following constraints I'm trying to model in Linear Integer Programming. I will try out diverse solvers for this later, but first I need to model the problem. Given the integer variables: ...
0
votes
0answers
25 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
1answer
66 views

How to model equality in Integer Linear Programming

How to implement v=(a==b) using Linear Programming? $$ v= \begin{cases} True, a=b\\ False, a≠b\\ \end{cases} $$ Until now I tried the big M-Method. To show a≤b: $$a-b+Mv≤M$$ $$-a+b-Mv≤-1$$ To show ...
3
votes
2answers
56 views

On the hardness of satisfying K number of linear constraints

Background: Normally in linear programing we have some objective function $$\text{maximize}\sum_{i = 1}^n a_i x_i $$ $$\text{subject to} \sum_{i =1}^n b_{ji}x_i \leq c_j \text{ for all } 1 \leq j \leq ...
1
vote
0answers
37 views

About Steiner tree problem in graphs

In the paper (p. 3) and the slides presents the formulation of the Steiner problem on graphs via so called Steiner cuts. But according to the definition, the number of Steiner cuts and so the ...
1
vote
0answers
20 views

Minimal subset of rows that generate smaller polyhedron

Given a matrix $[A|B]$ I want to find a minimal matrix $[A'|B'] \subseteq [A|B]$ (i.e. the rows in $[A'|B']$ are also in $[A|B]$) such that $A'x < B' \Rightarrow Ax < B$. Geometrically, I want ...
0
votes
0answers
10 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_{...
1
vote
1answer
48 views

Can an optimization algorithm be “universal”?

I am wondering if a Bayesian Optimization framework (e.g. Google's Vizier) can be used in lieu of a traditional solver like Gurobi or CPLEX. In trying to answer this question, I realized that I don'...
10
votes
5answers
14k views

Are all Integer Linear Programming problems NP-Hard?

As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming ...
3
votes
1answer
88 views

Linear programs with strict inequalities and supremum objectives

Linear programming can solve only problems with weak inequalities, such as "maximize $c x$ such that $A x \leq b$". This makes sense, since problems with strict inequality often do not have a solution....
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
1answer
68 views

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

I found this related question, but that's not quite it Is it possible to model this with integer programming: $$A = \begin{cases} 1 & \text{if } B \geq C \geq D \\ 0 & \text{otherwise}\end{...
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 ...
1
vote
1answer
76 views

(M)ILP overlap of two intervals

I got an ILP Model where $c_i$ represents the starting time for a visit$_i$. $c_i$ is already constraint by a number of constraints, one is $c_i > 0$. I have now outside of my model 0 or multiple ...
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 (...
10
votes
1answer
4k views

Short and slick proof of the strong duality theorem for linear programming

Consider the linear programs \begin{array}{|ccc|} \hline Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} & \max \vec{c}^T\vec{x} \\ \hline \end{array} \begin{array}{|ccc|} \hline Dual: & \...
1
vote
1answer
44 views

What is the most efficient way to test whether a set $X \subset \{0, 1\}^n$ and its complement $\{0, 1\}^n \setminus X$ are linearly separable?

I am interested in algorithms that have optimal running time, and ideally which are also very easy to implement. If you can also give some tips on how to implement the algorithm(s) you mention in the ...
0
votes
0answers
20 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 ...
1
vote
1answer
30 views

Relaxation of the knapsack constraints

A set $\mathcal{A}$ is the relaxation of another set $\mathcal{B}$, if $\mathcal{B} \subseteq \mathcal{A}$. I have a set of points defined as the knapsack constraint $$ \mathcal{X} = \{x \in \...

1
2 3 4 5 6