# 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
3k views

Karp's 21 NP-complete problems show that 0-1 integer linear programming is NP-hard. That is, an integer linear program with binary variables. If we set the $c^T$ vector of the objective $\text {... 1answer 44 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 ... 3answers 472 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 ... 1answer 130 views ### What is the right term/theory for prediction of Binary Variables based upon their continuous value? I am working with a linear programming problem in which we have around 3500 binary variables. Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best ... 1answer 83 views ### Maximize the number of edges in subgraph We are given a graph$G=(V,E)$and we want an algorithm to find a set of vertices$U$to maximize the following quantity :$\frac{|E(U)|}{|U|}$where$E(U)$denotes the number of edges in the subgraph ... 1answer 4k views ### Converting if-then-else condition to integer linear programming with equality constraints I have an if-then-else condition with three binary variables$A$,$B$and$C$: if A = 1 then B = 1 else B = C How do I express this as an ... 2answers 346 views ### Casting to boolean in integer linear programming I have variables$x \in \{0,1,\dots,5\}$and$y \in \{0,1\}$, where $$y = \begin{cases} 0 & \text{if } x = 5\\ 1 & \text{if } x \neq 5\end{cases}$$ My problem is to maximize$y$. How can I ... 1answer 57 views ### Solution to a Np-hard problem and its relevance to a dual LP From The design of APX algorithms book by David P. Williamson and David B. Shmoys, at the bottom of page 21 I saw the following statement (it is about the set cover LP and its dual): Let$y^*$be ... 1answer 2k views ### Advantage of MTZ problem formulation of TSP In class, we saw the Miller-Tucker-Zemlin formulation of the Travelling Salesmen Problem (TSP). MTZ is a way of formulating the TSP as an integer linear programming instance. I understand how MTZ ... 2answers 49 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 ... 1answer 126 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 ... 1answer 53 views ### Logic of multiple variables in ILP Is there a better way to represent an AND of$n$variables together other than creating$O(n)$new variables and constraints? 1answer 164 views ### Approximation algorithm for weighted set cover, using multiplicative weights It is known that the problem of fractional set cover can be rephrased as a linear programming problem and be approximated using the multiplicative weights method, for instance this lecture note shows ... 1answer 190 views ### Boolean variable that captures whether an inequality holds I have an integer linear program with variables$x_1,\dots,x_n$. I have an inequality$a_1 x_1 + \dots + a_n x_n \ge b$that I care about; it may or may or not hold. I want to introduce a boolean ... 1answer 47 views ### How to efficiently specify a MILP constraint with nested AND and ORs Let's say I want to set x1=1 if (x2=1 AND x3=1 AND x4=1) or (x5=1 and x6=1) or (x7=1) else x1=0 All of the xs are binary ... 1answer 330 views ### Using LP to prove the max matching - min cover theorem Konig's theorem says that, in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This theorem has several proofs; I would like to know if the following ... 1answer 29 views ### Positioning items to maximize separation Say we want to place n items on the real line. Let us denote the position of item i by$p_i$. We have interval constraints on the position$p_i$, i.e. we are given$l_i, r_i$such that$l_i \le p_i \...
734 views

Doing exam papers now and I came across two questions which I cannot get my head around sadly. Both are regarding Amdahl's law and Parallel Computing but they seem rather simple and frustratingly ...
41 views

### Choose N pairs of (job, time slot) with a constraint on the number of different jobs

I am making a solver to choose the best assignment to a set of people for an event, given their availability (chosen in a set $T$ of time slots), jobs preferences (among $J$ possible jobs) and some of ...
436 views

### Comparing dual of a canonical primal program - Directly and by dual of the standard program

I have it as a homework question to compare dual programs in the following way: Take a canonical program and write its dual Take the same canonical program, write it as a standard program, take the ...
329 views

### Efficient formulation for binary integer linear programming

Problem: There are two types of balls, big (B) and small (S), which need to packed into boxes. One box can contain either: nothing, or 1 S, or 1 B, or 2 S, or 2 B, or 1 B and 2 S We are given the ...
43 views

### Find value of b

The following system of restrictions is given: $$y_1+ 2 y_2 \leq 4 \\ 2y_1+y_2 \leq 2 \\ y_1+b y_2 \leq 3 \\ y_1, y_2 \geq 0$$ For which values of b is there a degenarate basic feasible solution? ...
76 views

### Does there exist a problem that is hard to do in parallel? [closed]

I am looking for a workload which is hard to paralellise/distribute between multiple machines. For example, integer factorization does not go 10 times faster if you have 10 machines to split the ...
206 views

### Introduction to Linear Optimization: Driving the artificial variables out of the basis (case: no entries in the $j$-row are nonzero)

Reading the book Introduction to Linear Optimization by Bertsimas and Tsiklisis, I've come across the following subject: Driving the artificial variables out of the basis. The description is as ...
170 views

### Why does absence of strongly polynomial time algorithm for LP imply restriction to rational instances?

From Bernhard Korte, Jens Vygen, Combinatorial Optimization, Instances of LINEAR PROGRAMMING are vectors and matrices. Since no strongly polynomial-time algorithm for LINEAR PROGRAMMING is known ...
34 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 ...
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?)},$$ ...