# Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

158 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
200 views

### Ill-conditioned LP in Benders decomposition

I have implemented a Benders decomposition for a constrained network flow but the LP solver (Gurobi) warns me of the ill-conditioning of the subproblem dual LP. As you can see below, the coefficients ...
148 views

### Is this a valid strong polynomial algorithm for deciding LP feasibility?

Let $$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
• 507
151 views

### Modeling traffic in a city

I am trying to model traffic in a city, $(i,j)$ represents a road in a city. There are $H$ vehicles in a city they have some prescheduled set of destinations to visit, $A_{j,h}$ denotes arrival time ...
• 1,589
92 views

### Building the Scheurman's Model II constraints for a multi period linear program

Scheurman's paper discusses Model I and model II Formulation to solve harvesting and scheduling problems. It is a specific implementation to solve multi period linear programs. Both models are also ...
• 153
81 views

### Modelling a simple ordering problem to have balanced delivery days

Assuming that I should buy 50 items from 25 different vendors with pre-known delivery duration between 2-7 day for each, which day of a week should I place each order so that the delivery days be even ...
• 159
84 views

### Robust Linear Optimization for avoiding diminishing returns

My engineering problem can be formulated as an LP as shown below \begin{align} \max_{\mathbf{x}}~~&\mathbf{a}^T\mathbf{x} \\ \mbox{s.t.}~~~&\mathbf{b}^T\mathbf{x} \leq B~~,~~\mathbf{1}^T\...
• 251
108 views

### Dual instability, degeneracy, tailing off effect - Which are the causes and which are the effects?

Dual instability, degeneracy, and the tailing off effect are often mentioned together in papers. However, I cannot seem to find a clear explanation on which of these cause the other and vice versa? ...
• 666
225 views

### Airline revenue management re-solving problem

I am considering a bid prices (shadow price of the capacity constraint) problem (from Chen, L. and Homem-de Mello, T. (2009)., page 14) where the acceptable classes for booking requests for ...
• 165
100 views

### Estimating multistop routing costs

In many OR problems, it is sometimes a good idea (or necessary) to relax routing constraints. An example of this occurs in the classical facility location problem, where a warehouse can send out a ...
• 13.4k
224 views

### Provide basic solution to CLP

I'm using Pyomo to formulate an LP with approx 500,000 constraints and 200,000 decision variables. The LP is solved using CLP. Some instances fail to return even a feasible solution after many ...
95 views

### Proof that the leaving variable cannot be selected as the entering one in the next round

Using the Dantzig's pivoting rule, can it be proven that the leaving variable of one round cannot be selected as the entering variable in the next round?
182 views

• 483
171 views

### Publishing paper that uses LP solver to solve equation

I was reading this paper by Cerna et al. (2018)1. In the paper there are only CPLEX-solvable equations given by the authors and the results. How valuable is this paper, and what is its quality? Can ...
• 1,589
242 views

107 views

### Projected Gradient Ascent for linear programming

I need to find a reasonable maximum for a linear programming problem, for which standard solvers for linear programming are just too slow. I was thinking of using projected gradient ascent, but do not ...
• 213
114 views

### Does a linear program always attains its (finite) infimum?

Consider the following (Lp). \begin{align}\min&\quad\mathbf{c} \cdot \mathbf{x}\\ \text{s.t. }&\quad A\mathbf{x} \geq \mathbf{b} \\ &\quad\mathbf{x} \geq \mathbf{0}\end{align} If $S$ is ...
66 views

### Dual of the alternative solutions

Suppose we have two alternative solutions for a linear program. Are their corresponding dual solutions the same? (in terms of the values for each dual variable)
• 400
89 views

### Function approximation of a complex objective function

I would like to approximate the following objective function using a simpler function that can use be defined in gurobi. \min_{I_{i,v}} \ \sum^{N_v}_{v}\sum^{TT_v}_{i} \ C_{loss,...
136 views

### Are there hybrid metaheuristic-solvers to solve combinatorial optimization problems?

I have a problem which is formulating a linear program. To solve large instances I implement a metaheuristic to solve my problem. In my problem, I have two objective functions. With my linear program, ...
• 335
108 views

### Polynomial Time Solution For a Mixed-Integer Linear Programming Specific Case

Consider the following mixed-integer linear programming (MILP): \begin{equation*} \begin{array}{ll@{}ll} \text{maximize} & 1 & \\ \text{subject to}& x_{i} \geq 0, &i=1 ,\dots, m\\ ...
139 views

### Harvest planning problem

I need to model the following problem: For a planning horizon of $P$ equal periods, one has $N$ harvesting locations and $K$ contractors who can harvest at those locations ($K < N$). Each ...
I've seen the claim (in the title) several places, but can't quite understand why it's true. From what I understand so far, the revised simplex method solves an LP in standard computational form, $$\... 3 votes 0 answers 184 views ### How to linearize a max min objective function? Let us suppose that I have a \max \min objective function that only depends on one set of variables: \underset{x}\max \underset{y}\min dy Associated with the linear set of constraints and right ... • 679 3 votes 0 answers 269 views ### Two binding constraints - Linear Programming I'm having some troubles to continue solving my system, I'm used to solve such systems but with "one" binding constraint, if someone could give me some helpful hints so I can solve it I will ... 3 votes 0 answers 87 views ### PuLP Python: How to linearize an inequality involving an integer variable I am working on a Copper payables problem where the objective function is to maximise the sum of copper payable over a time period, T. The total amount of payable tonnes i.e. what the customer will ... • 327 3 votes 0 answers 83 views ### Where I can study some job shop scheduling by course (video )? I am seeking the help to know where I can study the job shop scheduling Heuristics or using solver by some course/video as I see some of books and papers hard to understand . It is hoped that the ... • 31 3 votes 0 answers 832 views ### How can I see the engine log when solving a LP using pulp (python)? I wonder which command should I use to see how the steps the pulp solver is doing when solving a linear program. • 39 3 votes 0 answers 150 views ### Simplex method on graphs: How do I find a basic solution using the Ford-Fulkerson algorithm? I'm tasked with solving a minimal cost flow problem. I'm asked to first use the Ford-Fulkerson algorithm on my graph to find a basic solution that will then be used to do the simplex method on that ... • 181 3 votes 0 answers 50 views ### High-mix manufacturing capacity I'm not an expert in OR but I would like to determine what is the maximum manufacturing capacity of a plant (or how much a plant can produce of mix products). Each person in the plant has a known set ... 3 votes 0 answers 77 views ### Public available MPS files with semi-continuous variables Is there some MPS files with semi-continuous variables public available anywhere? To me it seems MIPLIB does not contain any. • 3,166 3 votes 0 answers 422 views ### On solving the Restricted Master Problem in Column Generation technique I am working on developing a column generation (CG) based optimization framework for a large-scale airline crew pairing problem (a set-covering problem). First, I generate an initial feasible solution ... 3 votes 0 answers 101 views ### Constraint equivalence in PuLP I'm working on an optimization problem in PuLP and I have to enforce a daily minimum of shifts and a daily maximum of assigned shifts. I have the following constraints to ensure each day has a minimum ... • 101 3 votes 1 answer 148 views ### Big LP program to be submitted to NEOS Server (union-closed sets conjecture) I have a big LP program with around 91,000 variables and 2,900,000 constraints. They are all binary variables, but I want to try also relaxing the problem putting 0 \le x \le 1 bounds. I am not ... 2 votes 0 answers 86 views ### Re-formulating an LP where a subset of constraints can be loosened? I have an LP of the structure below (omitting some constraints that are not directly applicable for this question).$$\text{min } c'xAx + By \geq d$$for a given A \in R^{m \times a}_{>0}, B \... • 515 2 votes 0 answers 51 views ### Implement a rolling horizon approach into a schedulig problem I have just come across the topic of 'Rolling Horizon' in my literature research and would now like to apply it myself, but unfortunately I don't know where to start. This is my model, which is ... 2 votes 0 answers 36 views ### Addressing Variable Multiplication in Constrained Infinity-Norm Maximization with Hypercube & Polyhedron Constraints I am reaching out to this knowledgeable community for assistance with a complex optimization problem that I have been investigating. Here is the formulation of the problem I'm addressing:$$\tag{1} \...
Following is the section 7.3 of Operation Research An Introduction by Hamdy A. Taha, Define the upper-bounded LP model as, $$\max z=\{CX|(A,I)X=b,0\leq X\leq U\}$$ The bounded algorithm uses only the ...