# Questions tagged [linear-programming]

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

315 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
80 views

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. ...
6k views

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: ...
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 ...
64 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 \...
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 ...
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 ...
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 ...
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 ...
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 ...
### 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 ...