Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
2k views

Maximum matching using linear programming

In a bipartite graph $G = (V,E)$, there is a neat algorithm for finding a maximum matching (or even a maximum-weight matching) using linear programming. It is explained here. The first step is to ...
4
votes
1answer
65 views

Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?

My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a ...
4
votes
1answer
526 views

Linear programming restricted to rational coefficients

I'm reading the appendix A of Williamson's "the design of approximation algorithms" about linear programming. In the definition of a linear programming it restricted the coefficients of cost function ...
4
votes
3answers
215 views

Help wrapping my head around a combinatorial optimization problem

Here's the problem I'm trying to solve: I have a bunch of widgets, whose weights vary over a small range. I would like to find the optimal grouping of them such that each group meets a minimum weight ...
4
votes
1answer
186 views

Formulating a linear program s.t. only extreme point solutions are found

If there are many solutions to a linear program s.t. the objective function is minimized/maximized (= optimal solutions are on an edge of the polytope), how can I force an LP solver to find only an ...
4
votes
3answers
80 views

Need help optimizing the loading of passengers on small airplanes

I work for a small non-profit that provides transportation for people who need medical treatment. We connect volunteer private pilots who fly people in their own (small) aircraft, typically 3-5 seats. ...
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 \...
4
votes
2answers
435 views

Dynamic Shortest Path with Linear Programming

Consider a grid with $x=5$ columns, $y=5$ rows, and $T$ timesteps. There are $N=2$ agents in this grid, which can move vertically or horizontally. The positions of each agent $x$ at timestep $t$ is ...
4
votes
1answer
479 views

Minimum spanning tree formulation as integer program

The minimum spanning tree problem can be solved in polynomial time via Kruskal's or Prim's algorithm. However, every integer program I have seen that corresponds to the MST problem require a ...
4
votes
0answers
206 views

Intuitive self-contained proof of Farkas' Lemma

I've been studying the proof of Farkas' Lemma, and given my rather fuzzy memory of Linear Algebra, am having some trouble with it. One version of Farkas' lemma states: For any convex cone generated ...
4
votes
0answers
121 views

Showing a linear program is infeasible or finding a feasible solution

I'm aware that for any given maximize/minimize LP problem, if its dual is unbounded then the primary is infeasible and vice versa. But what if there is no maximize/minimize objective function? For ...
4
votes
0answers
243 views

Algorithm to optimize polling frequency between producer and consumer

I am trying to optimize what we call AJAX request polling frequency in the domain of web design. Here's a general version of the problem in simple lingo: Problem Statement: Suppose there are 3 ...
3
votes
2answers
118 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 ...
3
votes
2answers
397 views

How to check if a specific ILP problem can be solved in polynomial time or not?

How can we know that a specific ILP problem is solvable in polynomial time or not given the constraints?
3
votes
3answers
263 views

Need Help Understanding MST Cutset Formulation

I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation). This is the definition: An ...
3
votes
1answer
1k views

Converting If-else condition to Linear Programming

I have a constraint in a linear programming formulation with two variables: $X \ge Y$ To which I want to apply the following if-else conditions: ...
3
votes
1answer
517 views

Efficient bandwidth algorithm

Recently I sort of stumbled on a problem of finding an efficient topology given a weighted directed graph. Consider the following scenario: Node 1 is connected to 2,3,4 at 50 Mbps. Node 1 has 100 ...
3
votes
1answer
565 views

Time complexity of linear program? [closed]

I have built a heuristic algorithm for approximately solving an NP complete graph problem by recursive linear relaxations. In each recursion, the algorithm returns a reduced graph, with number of ...
3
votes
1answer
103 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....
3
votes
1answer
125 views

Performance gain by implementing streamlined simplex

I have to solve linear transportation problems for a research project. Ideally, I should design an application that will recieve the problem data as an input and then show some results. The size of ...
3
votes
1answer
202 views

A little confusion with the Knapsack problem (a worked example)

I'm going through a worked example on the Knapsack problem: My problem is that I don't understand quite follow the last bulletpoint. Where does the $x_4 = 4/5$ comes from? I know $x_4$ has to be a ...
3
votes
1answer
128 views

Given an optimal solution to the LP, show how it can be used to construct a directed cycle with minimal directed cycle mean cost

Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle. Define the directed cycle mean cost to be $\frac {\{\text {sum ...
3
votes
1answer
634 views

Boat riddle as a combinatorial optimization problem?

I remember a riddle about a bunch of people on a river bank, and a boat with limited capacity (lets say the boat can transport 2 people at a time). There are various relations between the people like: ...
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 ...
3
votes
2answers
64 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 ...
3
votes
1answer
2k views

Express a “complex” IF-Statement to Linear Programming

In our current project we need to model the following if-statement in linear programming: If T1 < b < T2 then z = s else z = 0 where T1 and T2 are two ...
3
votes
1answer
1k views

Linear programming formulation for the single-source shortest path problem

In this course lecture; section 5.1, single-source shortest path (SSSP) is formulated as the following linear program (LP): \begin{align} \max &\sum d_u \\ \text{subject to} & \\ d_v &\le ...
3
votes
1answer
133 views

An integer linear program

I have the following problem: Given positive integers $a, b, c, d, n$, compute the maximum possible value (which is garuanteed to be less than $10^9$) of the function $$f(x,y) = cx + dy$$ where ...
3
votes
1answer
104 views

Express product in ILP

Suppose I have a mixed integer-linear program (MILP) with variables $x,y,z$, where $y$ is a 0-or-1 variable, and I want to impose the constraint $z=xy$. This is not expressible in a MILP directly. ...
3
votes
1answer
666 views

Linear programming formulation of cheapest k-edge path between two nodes

Given a directed graph $G = (V,E)$ with positive edge weights, find the minimum cost path between $s$ and $t$ that traverses exactly $k$ edges. Here is my attempt using a flow network: \begin{align} \...
3
votes
1answer
904 views

Dual problem of a maximization primal problem $P$?

Suppose we have a primal problem $P$ which is stated as a maximization problem $\max c^{T} x$. The dual problem is defined (Introduction to Linear Optimization by Dimitris Bertsimas) only for a ...
3
votes
1answer
2k views

Why is integer programming more difficult than (real) linear programming? [duplicate]

Why is integer programming (IP) more difficult than (real) linear programming (LP)? I searched a lot on the web, but I didn't find an answer.
3
votes
2answers
279 views

Model disjunction in a $\{0,1\}$ integer linear program

How can I model logical OR as an integer linear program? $$(y_3 + y_4 + y_5 + y_6 = 2) \lor (y_2 = 1)$$ where $y_i \in \{0, 1\}$, $1$ = True and $0$ = False.
3
votes
1answer
1k views

How to solve an ILP problem with conditions in an objective function?

I have came accross this link. I have an integer linear programming (ILP) problem $$\max_{(x_1, x_2,\ldots, x_n)}\sum_{i=1}^n x_i\cdot f(x_i),$$ $$\text{subject to } \begin{cases} ..., &(1)\\ L≤...
3
votes
0answers
411 views

Minimum clique cover

How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time? Having an undirected graph, I am trying to partition all its ...
3
votes
0answers
158 views

2-approximation edge-cover algorithm using primal-dual method

The problem Given an undirected graph $G=\left(V, E\right)$ and positive edge weights $w_e$, design a 2-approximation algorithm based on the primal-dual principle. So far I managed to represent the ...
3
votes
0answers
66 views

Computing the line equations of two crossing tangents in a point set separated by a vertical line?

I have provided a picture as an example. We have two point sets, P and Q. P is to the left of this vertical line (named x = x0), and Q is to the right of it. The goal is to compute the line equations ...
3
votes
0answers
182 views

Enumeration of corner points of a polytope [closed]

Given a linear program, is there any library or available code to enumerate all the corner points of a polytope ?. PS: Simplex method finds one corner point depending on the objective, but I need to ...
3
votes
0answers
53 views

Heuristic for making set of indexes in an array/matrix with generating functions/patterns

I am trying to find a lead on how to solve or find a heuristic the following kind of problem: Given an array/matrix with entries of only 1s and 0s, using a set of looping functions/patterns of a ...
3
votes
0answers
30 views

What is the most efficient algorithm for finding the bounding inequalities of a cone given the extremal rays?

Say that I am given a cone, as specified by the extremal rays whose facets form its convex hull, what is the most efficient algorithm that finds the linear-rank inequalities whose intersection defines ...
3
votes
0answers
97 views

Start simplex method from feasible internal point

I have one algorithm that generates a feasible solution to a linear programming problem. However, it is very likely that this is not a corner point. This makes it not suitable for direct use as an ...
3
votes
0answers
48 views

A variant of the assignment problem (?) [duplicate]

Possible Duplicate: A variant of the Assignment Problem (Not a comp.scientist, but have the basic research. Please excuse me if I've overlooked anything obvious.) In my variant of the problem I ...
2
votes
1answer
393 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
3answers
174 views

Integer linear programming formulation of formula in DNF

I have multiple sets, e.g., $$\{1, 2\}, \{2, 3, 4\}, \{1, 4\}$$ Each variable $1, 2, 3, 4$ is binary. I need to represent the following condition without additional variables $$(1 \land 2) \lor (2 \...
2
votes
1answer
224 views

How can the max-flow and min-cut problems, if dual to one another, both have unbounded optimal value?

The max-flow min-cut theorem states that the value of the maximum flow is equal to the minimum cut capacity. It is possible that the max-flow and min-cut is equal to $\infty$. However, reading ...
2
votes
2answers
3k views

Partition of a set of integer into 3 subsets of approximately equal sum

I'm having a very hard time trying to figure out how to solve this problem efficiently. Let me describe how it goes: "A hard working mom bought several fruits with different nutritional values for ...
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 ...
2
votes
3answers
612 views

Closest arithmetic progression to an array

Given an array of $N$ integers, having the option to increase or decrease its elements, the problem is to find the closest integer arithmetic progression. That corresponds to the smallest difference ...
2
votes
1answer
51 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 ...
2
votes
1answer
172 views

Modeling $(x > 0 \wedge y > 0) \Leftrightarrow z > 0$ in a linear program: impossible?

In this question, we see how to model boolean logic in $0 - 1$ ILPs. Moving to a relaxation, modelling $(x > 0 \vee y > 0) \Leftrightarrow z > 0$ with $x,y,z \in [0,1]$ with linear ...

1
2
3 4 5
7