Search results for "Linear programming"

A comparison of two different formulations for Arc Routing Problems on Mixed graphs

2006

[EN] Arc routing problems on mixed graphs have been modelled in the literature either using just one variable per edge or associating to each edge two variables, each one representing its traversal in the corresponding direction. In this paper, and using the mixed general routing problem as an example, we compare theoretical and computationally both formulations as well as the lower bounds obtained from them using Linear Programming based methods. Extensive computational experiments, including some big and newly generated random instances, are presented.

Solving type-2 Assembly Line Balancing Problem with Fuzzy Binary Linear Programming

2013

The Linear Ordering Polytope

2010

So far we developed a general integer programming approach for solving the LOP. It was based on the canonical IP formulation with equations and 3-dicycle inequalities which was then strengthened by generating mod-k-inequalities as cutting planes. In this chapter we will add further ingredients by looking for problem- specific inequalities. To this end we will study the convex hull of feasible solutions of the LOP: the so-called linear ordering polytope.

Packing a Trunk

2003

We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to pack as many identical boxes of size 4 × 2 × 1 units as possible into the interior of the trunk. This measure is important for car manufacturers, because it is a standard in the European Union.

V I G — A Visual and Dynamic Decision Support System for Multiple Objective Linear Programming

1989

In this paper we describe the principles of VIG (Visual Interactive Goal Programming), a Multiple Criteria Decision Support System, recently developed by Korhonen. PARETO RACE is a corner-stone of this system, which is designed to support both the modelling and solving of a multiple objective linear programming problem. The interface is based on one main menu, spreadsheets, and interactive use of computer graphics. VIG provides the decision-maker with the possibility to approach his/her decision problem by using an “evolutionary approach”. This means that the decision-maker does not have to specify the model precisely prior to solving the problem. In fact, the model evolves progressively. W…

Energy efficient optimisation for large‐scale multiple‐antenna system with WPT

2018

In this study, an energy-efficient optimisation scheme for a large-scale multiple-antenna system with wireless power transfer (WPT) is presented. In the considered system, the user is charged by a base station with a large number of antennas via downlink WPT and then utilises the received power to carry out uplink data transmission. Novel antenna selection, time allocation and power allocation schemes are presented to optimise the energy efficiency of the overall system. In addition, the authors also consider channel state information cannot be perfectly obtained when designing the resource allocation schemes. The non-linear fractional programming-based algorithm is utilised to address the …

An optimality test for semi-infinite linear programming

1992

In this paper we present a test to characterize the optimal solutions for the continuous semi-infinite linear programming problem. This optimality characterization is a condition of Kuhn–Tucker type. The resolution of a linear program permits to check the optimality of a feasible point,to detect the unboundedness of the problem and to find descent directions. We give some illustrative examples. We show that the local Mangasarian–Fromovitz constraint qualification is almost equivalent to Slater qualification for this problem. Furthermore, it follows from our study that this optimality condition is always necessary for a wide class of semi-infinite linear programming problems

Solution isolation strategies for the Bernstein polytopes-based solver

2013

The Bernstein polytopes-based solver is a new method developed to solve systems of nonlinear equations, which often occur in Geometric Constraint Solving Problems. The principle of this solver is to linearize nonlinear monomials and then to solve the resulting linear programming problems, through linear programming. However, without any strategy for the isolation of the many solutions of multiple-solution systems, this solver is slow in practice. To overcome this problem, we propose in this work, a study of several strategies for solution isolation, through the split of solution boxes into several subboxes, according to three main steps answering the questions: when, where, and how to perfo…

Optimal switches in multi-inventory systems

2007

Given a switched multi-inventory system we wish to find the optimal schedule of the resets to maintain the system in a safe operating interval, while minimizing a function related to the cost of the resets. We discuss a family of instances that can be solved in polynomial time by linear programming. We do this by introducing a set-covering formulation with a totally unimodular constraint matrix.

Strict quasi-concavity and the differential barrier property of gauges in linear programming

2014

Concave gauge functions were introduced to give an analytical representation of cones. In particular, they give a simple and a practical representation of the positive orthant. There is a wide choice of concave gauge functions with interesting properties, representing the same cone. Besides the fact that a concave gauge cannot be identically zero on a cone(), it may be continuous, differentiable and even on its interior. The purpose of the present paper is to present another approach to penalizing the positivity constraints of a linear programme using an arbitrary strictly quasi-concave gauge representation. Throughout the paper, we generalize the concept of the central path and the analyti…